Leetcode 150. Evaluate Reverse Polish Notation

Problem Explanation:

The problem is about evaluating Reverse Polish Notation (RPN), also known as postfix notation, which is a mathematical notation where every operator follows all of its operands. It is devoid of parentheses as long as the operators have fixed arity.

In this problem, operands and operators are given as strings in an array. Operators are plus (+), minus (-), multiplication (*) and division (/). Division has to truncate towards zero, which means it needs to return the largest integer less than or equal to the exact division. The RPN expression is always valid, meaning there would never be a divide by zero operation and it does not contain invalid characters or operations.

Walkthrough of an Example:

Let's consider Example 1:

["2", "1", "+", "3", "*"]

In postfix notation, we wait until we reach an operator to perform an operation. Here, 2 and 1 are followed by '+'. So add 2 and 1 to get 3. The resulting array looks like: "3", "3", "*"

Next, 3 is multiplied by 3. So, the output is 9.

Approach for Solution:

We can utilize a stack data structure to evaluate the RPN. We would traverse the input array and do the following:

1. If the current element is a number, we push it into the stack.
2. If we encounter an operator, we pop the top two numbers from the stack, apply the operator to them, and push the result back onto the stack.

At the end, the stack should contain a single element representing the final result.

Python Solution:

1
2python
3import operator
4class Solution:
5    def evalRPN(self, tokens: List[str]) -> int:
6        ops = { '+': operator.add, '-': operator.sub, '*': operator.mul, '/': operator.truediv }
7        stack = []
8        for token in tokens:
9            if token in ops:
10                b = stack.pop()
11                a = stack.pop()
12                res = ops[token](a, b)
13                if token == '/': res = int(res)
14                stack.append(res)
15            else:
16                stack.append(int(token))
17        return stack.pop()

Java Solution:

1
2java
3public class Solution {
4    public int evalRPN(String[] tokens) {
5        Stack<Integer> stack = new Stack<Integer>();
6        for (String token : tokens) {
7            if (!"+-*/".contains(token)) {
8                stack.push(Integer.valueOf(token));
9                continue;
10            }
11            int num2 = stack.pop();
12            int num1 = stack.pop();
13            switch (token) {
14                case "+":
15                    stack.push(num1 + num2);
16                    break;
17                case "-":
18                    stack.push(num1 - num2);
19                    break;
20                case "*":
21                    stack.push(num1 * num2);
22                    break;
23                case "/":
24                    stack.push(num1 / num2);
25                    break;
26            }
27        }
28        return stack.pop();
29    }
30}

JavaScript Solution:

1
2javascript
3var evalRPN = function(tokens) {
4    let stack = [];
5    for (let token of tokens) {
6        if (isNaN(token)) {
7            let num2 = stack.pop();
8            let num1 = stack.pop();
9            switch (token) {
10                case '+':
11                    stack.push(num1 + num2);
12                    break;
13                case '-':
14                    stack.push(num1 - num2);
15                    break;
16                case '*':
17                    stack.push(num1 * num2);
18                    break;
19                case '/':
20                    stack.push(num1 / num2 | 0);
21                    break;
22            }
23        } else {
24            stack.push(+token);
25        }
26    }
27    return stack[0];
28};

C++ Solution:

1
2c++
3class Solution {
4public:
5    int evalRPN(vector<string>& tokens) {
6        stack<int> stack;
7        for (auto& token : tokens) {
8            if (isOperator(token)) {
9                int op2 = stack.top();
10                stack.pop();
11                int op1 = stack.top();
12                stack.pop();
13                switch (token[0]) {
14                    case '+': stack.push(op1 + op2); break;
15                    case '-': stack.push(op1 - op2); break;
16                    case '*': stack.push(op1 * op2); break;
17                    case '/': stack.push(op1 / op2); break;
18                }
19            } else {
20                stack.push(stoi(token));
21            }
22        }
23        return stack.top();
24    }
25
26private:
27    bool isOperator(const string &op) {
28        return op.size() == 1 && string("+-*/").find(op) != string::npos;
29    }
30};

C# Solution:

1
2csharp
3public class Solution {
4    private readonly string[] Operators = { "+", "-", "*", "/" };
5    public int EvalRPN(string[] tokens) {
6        var stack = new Stack<int>();
7        foreach (var token in tokens) {
8            if (Operators.Contains(token)) {
9                var op2 = stack.Pop();
10                var op1 = stack.Pop();
11                switch (token) {
12                    case "+": stack.Push(op1 + op2); break;
13                    case "-": stack.Push(op1 - op2); break;
14                    case "*": stack.Push(op1 * op2); break;
15                    case "/": stack.Push(op1 / op2); break;
16                }
17            } else {
18                stack.Push(int.Parse(token));
19            }
20        }
21        return stack.Pop();
22    }
23}

They each contain a switch (or switch like) statement to check which operator is currently being considered, and then perform the operation on the two removed elements, and push the result back onto the stack. Finally, the last element in the stack is the result of the expression.Conclusion:

The Reverse Polish Notation is a mathematical notation that depends on the order of operands and operators, and doesn't require parentheses. It's useful in computer science fields like compilers and calculators.

These solutions make use of a stack data structure to solve the problem. When we encounter a number in the tokens, we push it on the stack, and when we encounter an operator, we pop two numbers from the stack, perform the operation, and push the result back on the stack. This approach, of using a stack, is efficient and straightforward, handling this unary operator problem with a time complexity of O(n).

Since the RPN evaluation algorithm can be used on a variety of common data structures, it has been implemented in numerous programming languages including Python, Java, JavaScript, C++ and C#. The implementations usually involve a stack for storing intermediate results, and a loop or recursive function to process the input. The general strategy is to push operands onto the stack until an operator is encountered, at which point the necessary number of operands are popped from the stack, the operation is carried out, and the result is pushed back onto the stack. This continues until all inputs have been processed, leaving the final result on the stack.

Thus, the process of evaluating Reverse Polish Notations works universally in all the discussed programming languages using the stack data structure. The basic operations like push, pop, and peek on stack data structure allow us to successfully calculate the value of the given RPN expression.

Note: Since the division operator (/) needs to truncate results towards zero, the implementation of division operation in these languages is done carefully, for example using the integer division operator, to handle this specific scenario.