Leetcode 150. Evaluate Reverse Polish Notation

Problem

Leetcode 150 - Evaluate Reverse Polish Notation

Example:

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

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

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

Approach

We can use stack to add the elements as we iterate through the token list. There are 5 scenarios

• element is ‘+’, then we pop 2 elements from stack then add then push to stack
• element is ‘-‘, then we pop 2 elements from stack then minus then push to stack (we must b-a where b is 2nd last element, and a is 1st last element since stack is LIFO)
• element is ‘*’, then we pop 2 elements from stack then multiply then push to stack
• element is ‘/’, then we pop 2 elements from stack then divide then pus hto stack (we must b/a where b is 2nd last element, and a is 1st last element since stack is LIFO)
• element is digit, then we push the int to stack

Finally we can return the top of element

Visualization of the Approach:

tokens = ["2","1","+","3","*"]
stack = []

ch = '2'
stack = [2]

ch = '1'
stack = [2, 1]

ch = '+' Since ch == '+', start operation
a, b = 1, 2
stack = [3]

ch = '3'
stack = [3, 3]

ch = '*' Since ch == '*', start operation
a, b = 3, 3
stack = [9]

return stack[-1] = 9

Here is the Python code for the solution:

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []

        for ch in tokens:
            if ch == '+':
                a, b = stack.pop(), stack.pop()
                stack.append(a+b)
            elif ch == '-':
                a, b = stack.pop(), stack.pop()
                stack.append(b-a)
            elif ch == '*':
                a, b = stack.pop(), stack.pop()
                stack.append(a*b)
            elif ch == '/':
                a, b = stack.pop(), stack.pop()
                stack.append(int(b/a))
            else:
                stack.append(int(ch))
                
        return stack[-1]

Time Complexity and Space Complexity

Time Complexity: $O(n)$

Space Complexity: $O(n)$