Evaluate Reverse Polish Notation Problem

Problem

You are given an array of strings tokens that represents an arithmetic expression in a Reverse Polish Notation.

Evaluate the expression. Return an integer that represents the value of the expression.

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, and /. Each operand may be an integer or another expression.

Note that:

The valid operators are '+', '-', '*', and '/'.
Each operand may be an integer or another expression.
The division between two integers always truncates toward zero.
There will not be any division by zero.
The input represents a valid arithmetic expression in a reverse polish notation.
The answer and all the intermediate calculations can be represented in a 32-bit integer.

Examples

Example 1:

Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

Example 2:

Input: tokens = ["4","13","5","/","+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6

Example 3:

Input: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
Output: 22
Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

Note that division between two integers should truncate toward zero.

It is guaranteed that the given RPN expression is always valid. That means the expression would always evaluate to a result, and there will not be any division by zero operation.

We have seen the conversion of infix to postfix expression here. Now lets see how to evaluate it.

Solution

Method 1 - Stack

To evaluate a Reverse Polish Notation (RPN) expression, we can make use of a stack:

Scan the input expression from left to right:
- If the scanned element is an operand, push it onto the stack.
- If the scanned element is an operator, pop the top two values from the stack, perform the operation, and push the result back onto the stack.
Repeat the above steps until all tokens have been processed.
The single remaining element in the stack is the result of the expression.

Note that here we are having operand stack, but while conversion to postfix from infix, we had operator stack.

Code

Java

public class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> operandStack = new Stack<>();

        for (String token : tokens) {
            if (token.matches("-?\\d+")) {
                operandStack.push(Integer.parseInt(token));
            } else {
                int operand2 = operandStack.pop();
                int operand1 = operandStack.pop();
                int result = 0;
                switch (token) {
                    case "+":
                        result = operand1 + operand2;
                        break;
                    case "-":
                        result = operand1 - operand2;
                        break;
                    case "*":
                        result = operand1 * operand2;
                        break;
                    case "/":
                        result = operand1 / operand2;
                        break;
                }
                operandStack.push(result);
            }
        }
        return operandStack.pop();
    }
}

Python

 class Solution:
     def evalRPN(self, tokens: List[str]) -> int:
         operand_stack: List[int] = []
 
         for token in tokens:
             if token.lstrip('-').isdigit():
                 operand_stack.append(int(token))
             else:
                 operand2 = operand_stack.pop()
                 operand1 = operand_stack.pop()
                 if token == '+':
                     result = operand1 + operand2
                 elif token == '-':
                     result = operand1 - operand2
                 elif token == '*':
                     result = operand1 * operand2
                 elif token == '/':
                     result = int(operand1 / operand2)  # Truncate towards zero
                 operand_stack.append(result)
         
         return operand_stack.pop()

Complexity

⏰ Time complexity: O(n) where n is the number of tokens.
🧺 Space complexity: O(n) because of the stack to store operands.

Dry Running the Algo

Lets start with infix expression - 2 * (3 + 5) - 6 On post fix conversion - 2 3 5 + * 6 - Here is how we will proceed


Input token	Operation	Stack contents (top on the right)	Details
2	Push	2
3	Push	2, 3
4	Push	2, 3, 5
+	Add	2, 8	Pop two values: 3 and 5 and push the result 8.
`*`	Multiply	16	Pop two values: 2 and 8 and push the result 16.
6	Push	14, 6
-	Subtract	8	Pop two values: 14 and 6 and push result 8
(End of tokens)	Finish	8	Pop the only value 8 and return it

Problem#

Examples#

Solution#

Method 1 - Stack#

Code#

Java#

Python#

Complexity#

Dry Running the Algo#