🔢150. Evaluate Reverse Polish Notation

Medium | Grind 75

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 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.

Example 1

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

Example 2

Example 3

As soon as I got this question, I tried to visualized it with what data structures to use, how to be efficient in terms of space and time and all that jazz. This made the problem way more complicated than it has to be.

If you take a step back and look at how you would solve this question manually in your brain, the algorithm goes something like this.

1. Read the input starting at left.

2. Keep reading the input until you get an operator character.

3. when you get an operator, you take the last two numbers, calculate and then store that result.

4. replace those last two numbers you calculated on with the result.

5. REPEAT step 2 - 4 until you have read all the characters.

6. AT THE END YOU ARE LEFT WITH ONE NUMBER AND THAT IS YOUR FINAL RESULT

SOLUTION

We first initialize a dictionary with the operator signs as lambda functions. I originally had a helper function with if else statement to do the calculation but this is a neat and better(less code, better eadibility/) way to do it. Saw this in the discussion forum for this question.

line 11 : we have a digits list which will function as our stack. Basically we will put numeric digits from our token in here and pop them needed.

line 12 : iterate over the characters in the token. Read one character at a time.

line 13 -14 : check if the character is a key in our operation dictionary. if it is not, meaning the character is a number rather than an operation sign, we append/put the character in our digits list.

line 16 : character we are looking at currently in token is a operation sign

line 17 - 18 : we pop the latest two digits in our digits stack and store them in a and b variable respectively.

line 19 : call the anonymous function based on the operation sign. you always have to pass two arguments. the lambda /anonymous function will calculate on the two numbers and return their result.

line 20 : put the result in the digits stack.

line 22: at the end, when you have finished going through all the characters in the tokens list, you will be left with one number in digits stack. This is your final answer.

class Solution:
    def __init__(self): 
        self.operation = {
            '+': lambda a,b: a+b,
            '-': lambda a,b: b-a,
            '*': lambda a,b: a*b,
            '/': lambda a,b: b/a
        }
        
    def evalRPN(self, tokens: List[str]) -> int:
        digits = []
        for char in tokens: 
            if char not in self.operation: 
                digits.append(int(char))
            
            else: 
                a = digits.pop()
                b = digits.pop()
                result = self.operation[char](a,b)
                digits.append(int(result))
        
        return digits[0]

TIME AND SPACE COMPLEXITY

TIME COMPLEXITY: Given that we are iterating over the enitre length(N) of token list, our time complexity is O(N).

SPACE COMPLEXITY: the operations dictionary is constant. The only variable with variable space size is our digits list. If you look at the token input, the the number of operations signs is always 1 less than number of digits. If the length of our token is N, then there will be at most, N/2 + 1 digits. The number given this, the digits array size will never exceed (N). So O(N)