Postfix Expression Evaluation

Evaluate the value of a Postfix expression, also known as expression in Reverse Polish Notation.
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.

Assumptions: The given postfix expression will be a valid expression.
1. String operands will be valid Integers (positive or negative)
2. Operators will be valid operators in: + - / *
3. 0 will not be passed as a divisor for division operation.

Example:
Input:
20    30    +
Output:
50

Input:
5    1    2    +    4    *    +    3    -
Output:
14

Note: Input is an array of strings to allow numbers with multiple digits as operands.
For example "20", "45" etc.


Video coming soon!



Subscribe for more updates


Preparing for interviews? IDeserve team is here to help.




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.


Hone your coding skills!




AngryNerds Practice platform »

Algorithm Visualization




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)


Contribution

  • Sincere thanks from IDeserve community to Saurabh Kumar for compiling current post.

    Saurabh Kumar

    Ninja Programmer