Postfix Expression Evaluation

Algorithm/Insights

Reverse Polish notation (RPN) is a mathematical notation in which every operator is placed after its operands. For example, x + y (in infix notation) is expressed in RPN as x y +
It is also known as postfix notation.

The expression can be evaluated using a stack as described below:
1. If the array has only 1 element, then return the element.
2. Traverse the string array for elements i = 0 to length of array:
   a. If the element at index i is an operand, then parse it to get the value.
   b. Else, pop two elements from the stack (say x and y) and perform the operation specified by the operator (for example, +) on the 2 elements in the below order and store it as the value:
            y = s.pop()
            x = s.pop()
            value = x + y
   c. We will get a value from steps a OR b, push the value on to the stack.
3. Finally, only 1 integer element is left on the stack, return it.


Example:
String Array:    5    1    2    +    4    *    +    3    -

1. Initialize empty stack.


2. Since 5 is an operand, add it to the stack.


3. 1 and 2 are also operands, so add these to the stack too.


4. Next we have + operator,


5. Push the value onto the stack.


6. Next we have 4, which is an operand, so push it to the stack


7. Next we have * operator,


8. Push the value onto the stack


9. Next we have + operator,


10. Push the value 17 onto the stack


11. Next element is an operand 3, push it to the stack


12. Last, we have - operator,


Finally, all the array elements are processed, and we have 14 as the result.

Code Snippet

			
package com.ideserve.questions.saurabh;

import java.util.Stack;

/**
 * <b>IDeserve <br>
 * <a href="https://www.youtube.com/c/IDeserve">https://www.youtube.com/c/IDeserve</a>
 * Given an array of Strings, every string being either an operand or an operator,
 * in Reverse Polish Notation, find out the value of the expression.
 *
 * @author Saurabh
 */
public class PostfixExpressionEvaluation {
    public static int evalPostfixExpression(String[] op) {
        
        if(op.length == 1) {
            return Integer.parseInt(op[0]);
        }
        
        Stack<Integer> s = new Stack<Integer>();
        for(String exp : op) {
            
            Integer value = null;
            String operator = null;
            if((exp.charAt(0) >= '0' && exp.charAt(0) <= '9') ||
               (exp.charAt(0) == '-' && exp.length() > 1)) {
                value = Integer.parseInt(exp);
            } else {
                operator = exp;
            }
            
            if(operator != null) {
                Integer y = s.pop();
                Integer x = s.pop();
                
                switch(operator) {
                    case "+" : value = x + y; break;
                    case "-" : value = x - y; break;
                    case "*" : value = x * y; break;
                    case "/" : value = x / y; break;
                }
            }
            s.push(value);
        }
        return s.pop();
    }

    public static void main(String[] args) {
        String[] op = {"5", "1", "2", "+", "4", "*", "+", "3", "-"};
        System.out.println("Value of the expression is " + evalPostfixExpression(op));
    }
}
		

Order of the Algorithm

Time Complexity is O(n)
Space Complexity is O(n)