Evaluate Reverse Polish Notation

Problem Statement

You are equipped with an array of strings, tokens, where each element symbolizes a component of an arithmetic expression written in Reverse Polish Notation (RPN). Your objective is to determine the integer result of this expression by correctly evaluating it according to the RPN rules. The array comprises both integers and operational symbols ('+', '-', '*', '/'). Notably, divisions between integers should round towards zero, and it's assured that the expression avoids division by zero. Every operation and operand should fit within a 32-bit integer's capacity. The overarching goal is to compute and return this integer value.

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

Constraints

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

Approach and Intuition

Reverse Polish Notation (RPN) offers a straightforward mechanism for evaluating expressions as it eliminates the need for parenthesis to dictate operational precedence. The procedure to evaluate an RPN expression is primarily based on a last-in, first-out (LIFO) methodology, utilizing a stack data structure:

1. Initialize an empty stack.
2. Traverse the elements in the tokens array sequentially:
   • If the element is a number, push it onto the stack.
   • If the element is an operator:
     1. Pop the top two numbers from the stack (second topmost first, then topmost).
     2. Apply the operator with these two numbers.
     3. Push the result back onto the stack.
3. After processing all elements in the array, the stack will contain one element, which is the result of the RPN expression.

Example Understanding:

• For tokens = ["2","1","+","3","*"]:
  • Process '2' and '1' — push to the stack.
  • Process '+' — pop '1' and '2', calculate 2 + 1 = 3, push '3' back.
  • Push '3' from the tokens.
  • Process '*' — pop '3' and '3', calculate 3 * 3 = 9, push '9' back.
  • The stack's final element '9' is the result.

This stack-based approach is efficient and direct due to the postulated structure of Reverse Polish Notation, ensuring that operands always precede their operator, thus making immediate calculation feasible as soon as an operator is encountered.

Solutions

class Solution {
public:
    int evaluateRPN(vector<string>& tokens) {
        unordered_map<string, function<int(int, int)>> ops = {
            {"+", [](int x, int y) { return x + y; }},
            {"-", [](int x, int y) { return x - y; }},
            {"/", [](int x, int y) { return x / y; }},
            {"*", [](int x, int y) { return x * y; }}};
        stack<int> values;
        for (string& token : tokens) {
            if (ops.find(token) == ops.end()) {
                values.push(stoi(token));
            } else {
                int second = values.top();
                values.pop();
                int first = values.top();
                values.pop();
                function<int(int, int)> operate = ops[token];
                int computed = operate(first, second);
                values.push(computed);
            }
        }
        return values.top();
    }
};