Question

LeetCode Link | 150. Evaluate Reverse Polish Notation | Medium

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.

Note that:

  • The valid operators are '+', '-', '*', and '/'.
  • Each operand may be an integer or another expression.
  • The division between two integers always truncates toward zero.
  • There will not be any division by zero.
  • The input represents a valid arithmetic expression in a reverse polish notation.
  • The answer and all the intermediate calculations can be represented in a 32-bit integer.

Constrains

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

Examples

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

Solution Approach

Method: Stack

Constrains

  • None

This method does not have any limitations.

Concept Explanation

In fact, Reverse Polish Notation (RPN) is equivalent to post-order traversal in a binary tree. You can think of operators as intermediate nodes and draw a binary tree following the rules of post-order traversal.

However, it is not necessary to solve this problem from the perspective of a binary tree. It’s sufficient to understand that RPN serializes a binary tree using post-order traversal.

Looking further, in this problem, each sub-expression must yield a result, and then this result is used for further calculations. This process is essentially akin to eliminating adjacent strings, much like the “match-and-remove” in problem 1047. Remove All Adjacent Duplicates In String.

However, in this problem, instead of eliminating adjacent elements, we perform operator calculations!

Code

  • Time complexity: O(n)
  • Space complexity: O(n)

TypeScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function evalRPN(tokens: string[]): number {
    const stack: number[] = [];
    const operatorMap: Map<string, (a: number, b: number) => number> = new Map([
        ['+', (a, b) => a + b],
        ['-', (a, b) => a - b],
        ['/', (a, b) => Math.trunc(a / b)],
        ['*', (a, b) => a * b],
    ]);
    let a: number, b: number;
    for (let t of tokens) {
        if (operatorMap.has(t)) {
            b = stack.pop()!;
            a = stack.pop()!;
            stack.push(operatorMap.get(t)!(a, b));
        } else {
            stack.push(Number(t));
        }
    }
    return stack.pop()!;
};

Conclusion

We are accustomed to infix expressions because they align with our habitual way of thinking, but infix expressions are not very friendly to computers.

For example, in the infix expression 4 + 13 / 5, a computer scanning from left to right would encounter 13 and need to determine what operator follows it, compare priorities, then compute 13 with the subsequent 5. After completing the operation, it has to backtrack to the position of 4 to continue with the addition. Quite cumbersome, isn’t it?

When converting an infix expression to postfix notation, such as [“4”, “13”, “5”, “/“, “+”], it’s different. The computer can use a stack to process sequentially without considering priority or backtracking, making postfix expressions very friendly to computers.

This problem not only serves as a good exercise but also demonstrates the computer’s way of processing.

In the 1970s and 1980s, Hewlett-Packard used RPN (postfix notation) in all its desktop and handheld calculators, and it continued to be used in some models into the 2020s.