Question

Write a Reverse Polish Calculator, RPN

We discussed in class a general implementation of RPN using a stack to keep track of the numbers. Each time an operand is encountered, two values are popped from this stack, the given operation is performed, and the result is pushed back onto the stack. Utilize Java generic Stack Class to implement this algorithm with four arithmetic operations: +, *, -, /.

It is suggested that you implement a class RPN with a single static method evaluate. This method should have the following signature:

public static String evaluate(String expression)

It should split the passed expression into (a string array of) tokens by invoking splitmethod of String class. This array can then be processed one element at a time (perhaps another method): each time a number is found – it is pushed on a stack. Each time an operation is found – two numbers are popped from the stack, the given operation is performed, and the result is pushed back on the stack. If the passed expression was a properly formed RPN, the last element on the stack represents the result. It should be returned as a string. If the given expression is not valid, evaluate should return a string denoting a syntax error.Your main should continually ask the user to input a potential RPN string which would be passed to the evaluate method. In order to terminate the procedure, the user would input an empty string (carriage return)

Answer 1

// RPN.java

import java.util.Scanner;
import java.util.Stack;

public class RPN {

   // method to evaluate an input string representing a postfix expression consisting only of numbers
   // and operators (+, - , * and /) and returns the result of the expression, if valid
   // else returns "syntax error" if invalid
   public static String evaluate(String expression)
   {
       // split the input expression into array of strings using space as the delimiter
       String[] tokens = expression.split(" ");
       // create an empty stack of double
       Stack<Double> stack = new Stack<Double>();
      
       // loop over the tokens
       for(int i=0;i<tokens.length;i++)
       {
           // operator
           if(tokens[i].equals("+") || tokens[i].equals("-") || tokens[i].equals("*") || tokens[i].equals("/"))
           {
               // invalid expression
               if(stack.isEmpty())
                   return "syntax error";
               double op2 = stack.pop(); // get the top number of stack
               if(stack.isEmpty()) // invalid expression
                   return "syntax error";
               double op1 = stack.pop(); // get the second top number of stack
              
               // based on operator perform the operation and push the result back to stack
               if(tokens[i].equals("+"))
                   stack.push(op1 + op2);
               else if(tokens[i].equals("-"))
                   stack.push(op1 - op2);
               else if(tokens[i].equals("*"))
                   stack.push(op1 * op2);
               else
               {
                   if(op2 == 0) // divide by zero error
                       return "syntax error";
                   else
                       stack.push(op1 / op2);
               }
           }else // number i.e operand, insert it on top of stack
           {
               stack.push(Double.parseDouble(tokens[i]));
           }
       }
      
       // after evaluation get the top element of stack
       String result = stack.pop() + "";
       if(!stack.isEmpty()) // stack is not empty, syntax error
           result = "syntax error";
       return result;
   }
  
   public static void main(String[] args) {

       String expression;
       Scanner scan = new Scanner(System.in);
       // loop that continues until the user exits
       do
       {
           // input the expression
           System.out.println("Enter RPN string(operands and operators separated by spaces), blank to exit: ");
           expression = scan.nextLine();
           // check if user wants to exit
           if(expression.length() > 0)
               System.out.println(evaluate(expression)); // evaluate and display the result
       }while(expression.length() > 0);
   }

}

//end of RPN.java

Output: