[Top Interview 150] 150. Evaluate Reverse Polish Notation

Solution)

 

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

        for tk in tokens:
            if tk == "+":
                stack.append(stack.pop() + stack.pop())
                
            elif tk == "*":
                stack.append(stack.pop() * stack.pop())

            # Careful with the order of operand
            elif tk == "-":
                stack.append(-stack.pop() + stack.pop())
            
            # Careful with the order of operand and floor division
            elif tk == "/":
                right, left = stack.pop(), stack.pop()
                stack.append(math.trunc(left / right))
            
            # If digit
            else:
                stack.append(int(tk))

        
        return stack[-1]

 
 
Problem: LeetCode
 
Time Complexity: O(n)
Space Complexity: O(n)
 
 

Explanation)

 
If we find digits, we'll append the digits to our stack.
If we find an operator, we'll pop two consecutive numbers from stack and do the operation. Append the result to the stack.
 
That's basically how Reverse Polish Notation works. Just be thoughtful of the orders of the operands when you pop two numbers.
 
 

Initialization)

 
We'll use a stack because whenever we find an operator, we need to get two numbers right before the operator. The easiest way to do that is to use the stack's property First-In-Last-Out. Using this property, we just need to pop twice!
 

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

 
 

+ and *)

 
Whenever the current tk is an operator, we know for sure that there will be at least two numbers in stack. So if tk is either "+" or "*", simply pop two numbers and add or multiply them. Order of the operands don't matter for these operators.
 
Append the result back to stack.
 

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

        for tk in tokens:
            if tk == "+":
                stack.append(stack.pop() + stack.pop())
                
            elif tk == "*":
                stack.append(stack.pop() * stack.pop())

 
 

- and /)

 
If tk is "-" or "/", we have to be careful because the order of operands DO MATTER. 
 
For "-", we can still do consecutive pops. However, keep in mind that the first pop is the right operand and the second pop is the left operand. Once you acknowledge that, you will know that you have to put (-) sign to the first pop and add the second pop.
 
For "/", things get more tricky due to Python's stupidness. To make the code more clean, let's save the operands to variables. The first pop will be saved in right, and the second pop will be saved in left.
 
Now you just need to divide left by right. BUT, the problem says we need to truncate the division toward zero. So we do that by using the func method from math library. Once we have the truncated division result, append that result to stack.
 

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

        for tk in tokens:
            if tk == "+":
                stack.append(stack.pop() + stack.pop())
                
            elif tk == "*":
                stack.append(stack.pop() * stack.pop())

            elif tk == "-":
                stack.append(-stack.pop() + stack.pop())
            
            elif tk == "/":
                right, left = stack.pop(), stack.pop()
                stack.append(math.trunc(left / right))

 
 

Lastly)

 
Now! After dealing with all the operators, let's deal with digits.
There's nothing much, just append the digit to stack after converting the string into int.
 
Once all the calculations are done, return the element in stack, which is the result of the entire Reverse Polish Notation. 
 

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

        for tk in tokens:
            if tk == "+":
                stack.append(stack.pop() + stack.pop())
                
            elif tk == "*":
                stack.append(stack.pop() * stack.pop())

            elif tk == "-":
                stack.append(-stack.pop() + stack.pop())
            
            elif tk == "/":
                right, left = stack.pop(), stack.pop()
                stack.append(math.trunc(left / right))
            
            else:
                stack.append(int(tk))

        
        return stack[-1]

 
 
 
This also was an easy problem if you knew how to use stack. All the stack problems were based off from very simple stack concepts, which made them good practices for me.