150. Evaluate Reverse Polish Notation — LeetCode(Python)

I got you!

Problem:

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:

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

Constraints:

• 1 <= tokens.length <= 104
• tokens[i] is either an operator: "+", "-", "*", or "/", or an integer in the range [-200, 200].

Solution:

operators = ['+', '-', '*', '/']
stack = []
for t in tokens:
    if t not in operators:
        stack += [t]
    else:
        b = int(stack.pop())
        a = int(stack.pop())
        if t == '+':
            exp = a + b
        elif t == '-':
            exp = a - b
        elif t == '*':
            exp = a * b
        else:
            exp = int(a / b)
        stack.append(exp)
                
return stack[0]

Explanation —

We use a stack to solve this problem.

We keep pushing elements onto the stack if they are not operators, which means they are numbers.

When we encounter an operator, we pop two elements from the stack and perform the required operation.

The evaluation of our operation is pushed back into the stack.

Finally, we return the first element in the stack which holds the answer to the given expression.

Note: we are given that the expression will always be valid, so there will be only one element remaining in the stack in the end, which is going to be the evaluation of the final operation that we perform.

Time and Space Complexity —

Since we are iterating over all elements in the list, we require a linear amount of time to perform the given task.

Also, the stack could hold all elements in the list in the worst case, so we require a linear amount of space as well.

Thus, if n is the number of elements in the list tokens,

Time Complexity: O(n)

Space Complexity: O(n)

Feel free to ask any related questions in the comment section or the links provided down below.

I don’t have friends:

Let’s be friends!

Connect with me on:

LinkedIn

GitHub

Instagram (I know. Very professional)

Jai Shri Ram 🙏