Problem 150

(Last updated: )

Question statement

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.

Solution

Main idea:

Create a stack. Scan the tokens array. Push tokens[i] into the stack if it is a number. If it is an operation, instead, pop the last two elements from the stack, perform the operation, and then push the result into the stack. Continue this way until the stack is exhausted.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def calculator(self,a, b, op):
    if(op=='+'):
        return a+b
    if(op=='-'):
        return a-b
    if(op=='*'):
        return a*b
    if(op=='/'):
        return int(a/b)

def evalRPN(self, tokens: List[str]) -> int:
    num_stack = []
    operations = set(["+", "-", "*", "/"])
    for i in tokens:
        if(i in operations):
            a = num_stack.pop(-2)
            b = num_stack.pop(-1) 
            num_stack.append(self.calculator(a, b, i))
        else:
            num_stack.append(int(i))
    return num_stack[-1]

Comments:

Time complexity: O(n)

At the time of submission, the above solution passes leetcode submission cases in 63ms, beats 82.29% of users. It uses 17.10MB of memory, beating 71.20% of users.