Question

Programming Assignment 2 – RPN Calculator –

Infix to Postfix Conversion and The Evaluations of the Postfix Expression.

You are to design and implement and algorithm in Java, to input an Infix expression , convert to a postfix expression and finally evaluate the postfix expression… Follow the examples done during class lectures…

1. We are used to infix notation - ”3 + 4” - where the operator is between the operands. There is also prefix notation, where the operand comes before the operands. A Reverse Polish Notation calculator uses postfix notation, and was one of the first handheld calculators built. At first, it seems confusing, but is very logical once you think about it. Instead of doing ”2 + 3 + 4”, you may do ”2 [enter] 3 [enter] 4 [enter] + +”.
2. You will be implementing a conversion from infix to RPN and then perform an RPN calculator for this assignment.

3. How does an RPN calculator work? It is quite simple in principle. The calculator keeps a stack - a list of numbers. When you type a number and hit ”enter”, it pushes, or appends the number to the stack. So you build up a stack of numbers. Whenever you click an operand, it applies the operator to the top of the stack. In the previous example, it builds a stack like [2, 3, 4]. When you hit the first ”+”, it pops off the top/most recent two elements off the list and ”pluses” them. Lastly, it pushes the result back on the stack, so it looks like [2, 7]. When you hit plus again, it pops off the two elements (so the stack is temporarily empty), adds them, and pushes it back on the stack, so you get [9] .

3 What you need to do

For the first part of this assignment, think about what classes you need. Java has a Stack class for you, but write your own ( do nt use the Java Stack class). Use encapsulation, think about what methods it should have, and call it something like CalculatorStack. Add an option to ”roll” the stack; shift it left or right by one (and the end number rollls) to the other end). Other classes may include Controller, Handler, or SpecialOperationsHandler.

4 Why?

              • It’s one of the better assignments I can think of as a teaching tool

• RPN calculators are awesome - they’re far more logical than infix calculators once you get used to them

• You should learn RPN calculators; besides the historical importance, it forces you to think differently. Several example done during class lectures.

The following code below is a sample on how to evaluate the RPN expression …

Answer 1

import java.io.IOException;
import java.util.Scanner;
import java.util.Stack;

public class InfixToPostfix {
   Stack<Character> stack;
   String infix;
   private String postfix = "";

   public InfixToPostfix() {
       stack = new Stack();
   }

   public String Convert() {
       for (int j = 0; j < infix.length(); j++) {
           char ch = infix.charAt(j);
           switch (ch) {
           case '+':
           case '-':
               Precdence(ch, 1);
               break;
           case '*':
           case '/':
               Precdence(ch, 2);
               break;
           case '(':
               stack.push(ch);
               break;
           case ')':
               gotParen(ch);
               break;
           default:
               postfix = postfix + ch;
               break;
           }
       }
       while (!stack.isEmpty()) {
           postfix = postfix + stack.pop();
       }
       return postfix;
   }

   public void Precdence(char opThis, int prec1) {
       while (!stack.isEmpty()) {
           char opTop = stack.pop();
           if (opTop == '(') {
               stack.push(opTop);
               break;
           } else {
               int prec2;
               if (opTop == '+' || opTop == '-')
                   prec2 = 1;
               else
                   prec2 = 2;
               if (prec2 < prec1) {
                   stack.push(opTop);
                   break;
               } else
                   postfix = postfix + opTop;
           }
       }
       stack.push(opThis);
   }

   public void gotParen(char ch) {
       while (!stack.isEmpty()) {
           char chx = stack.pop();
           if (chx == '(')
               break;
           else
               postfix = postfix + chx;
       }
   }
   static String checkInvalid(String str)
{
       char ch[] = str.toCharArray();
       Stack<Character> st = new Stack<Character>();
for(int i=0;i<ch.length;i++)
{
if ( ch[i] == '(')
st.push(ch[i]);
if ( ch[i] == ')')
{

if (st.isEmpty())
{
return "There is no matching open parenthesis.";
}
st.pop();
  
}

}


if (!st.isEmpty())
return "There is no matching close parenthesis.";
   return null;
  
}

  
   public static int calculation(String s) {
       //Stack<Integer> postfix = new Stack<Integer>();
       Stack<Integer> postfix = new Stack<Integer>();
       for (int i = 0; i < s.length(); i++) {
           char c = s.charAt(i);

           if (Character.isDigit(c))
               postfix.push((c - '0'));
           else {
               int val1 = postfix.peek();
               postfix.pop();
               int val2 = postfix.peek();
               postfix.pop();

               switch (c) {
               case '+':
                   postfix.push(val2 + val1);
                   break;

               case '-':
                   postfix.push(val2 - val1);
                   break;

               case '/':
                   postfix.push(val2 / val1);
                   break;

               case '*':
                   postfix.push(val2 * val1);
                   break;
               }
           }
       }
       return postfix.peek();
   }
   public static void main(String[] args) throws IOException {

       Scanner sc = new Scanner(System.in);
       System.out.println("Enter Infix Expression:");
       String input = sc.nextLine();
       String ret = checkInvalid(input);
       if(ret!=null){
           System.out.println("Invalid Expression: ");
           System.exit(0);
       }
          
      
       String output;
       InfixToPostfix infixToPostfix = new InfixToPostfix();
       infixToPostfix.infix = input;
       output = infixToPostfix.Convert();
       System.out.println("Postfix expression is: " + output + '\n');
      
       System.out.println("Evaluate: " + calculation(output));
      

   }

}

==============================================
See OUTPUT

13 14e 15 16 17 18 19 20 21 public String ConvertO i for (int j 0; j < infix.lengthO; j+ char chinfix.charAtj); switch (ch) case + case-': Precdence(ch, 1); break; case* case /' 23 24 25 26 27 28 29 30 31 32 Precdence(ch, 2); break; case': stack.push(ch); break; case ' gotParen(ch); break; default: postfix-postfix + ch; break; 34 35 2A E Console 3 <terminated> InfixToPostfix [Java Application] /Library/Java/JavaVirtualMachines/jdk1.8.0_202.jdk/Contents, Enter Infix Expression: ostfix expression is: 12+ Evaluate: 3


Thanks, PLEASE COMMENT if there is any concern.