150. Evaluate Reverse Polish Notation

Problem Description

You are asked to evaluate an arithmetic expression provided as an array of strings, tokens, which uses Reverse Polish Notation (RPN). This notation places the operator after the operands. For example, the expression "3 4 +" in RPN is equivalent to "3 + 4" in standard notation. Your task is to calculate the result of the expression and return the resulting integer value.

Several points to consider for this problem are:

The expression only contains the operators +, -, *, and /.
Operands could be either integers or sub-expressions.
When performing division, the result is always truncated towards zero.
The expression does not contain any division by zero.
The expression given is always valid and can be evaluated without error.
The result of the evaluated expression and any intermediate operations will fit within a 32-bit integer.

Intuition

To solve this problem, we need to understand the nature of Reverse Polish Notation. In RPN, every time we encounter an operator, it applies to the last two operands that were seen. A stack is the perfect data structure for this evaluation because it allows us to keep track of the operands as they appear and then apply the operators in the correct order.

The intuition for the solution is as follows:

We iterate through each string (token) in the tokens array.
If the token is a number (single digit or multiple digits), we convert it to an integer and push it onto a stack.
If the token is an operator, we pop the last two numbers from the stack and apply this operator; these two numbers are the operands for the operator.
The result of the operation is then pushed back onto the stack.
After applying an operator, the stack should be in a state that is ready to process the next token.
When we've processed all the tokens, the stack will contain only one element, which is the final result of the expression.

Division in Python by default results in a floating-point number. Since the problem states that the division result should truncate toward zero, we explicitly convert the result to an int, which discards the decimal part.

The key here is to iterate through the tokens once and perform operations in order, ensuring the stack's top two elements are the operands for any operator we come across.

Learn more about Stack and Math patterns.

Solution Approach

The solution makes use of a very simple yet powerful algorithm that utilizes a stack data structure to process the given tokens one by one. Here are the steps it follows:

Initialize an empty list nums that will act as a stack to store the operands.
Iterate over each token in the tokens array.
- If the token is a numeric value (identified by either being a digit or having more than one character, which accounts for numbers like "-2"), we convert the token to an integer and push it onto the stack.
- If the token is an operator (+, -, *, /), we perform the following:
  - Pop the top two elements from the stack. Since the last element added is at the top of the stack, we'll refer to these as the second operand (at nums[-1]) and the first operand (at nums[-2]) in that order.
  - Apply the operator to these two operands. For addition, subtraction, and multiplication, this is straightforward.
  - For division, we apply integer division which is the same as dividing and then applying the int function to truncate towards zero. This is important as it handles the truncation towards zero for negative numbers correctly. The simple floor division operator // in Python truncates towards negative infinity, which can give incorrect results for negative quotients.
  - The result of the operation is then placed back into the stack at the position of the first operand (nums[-2]).
  - The second operand (nums[-1]), which has already been used, is removed from the stack.
After processing all the tokens, there should be a single element left in the nums stack. This element is the result of evaluating the expression.

The algorithm used here is particularly efficient because it has a linear time complexity, processing each token exactly once. The space complexity of this approach is also linear, as it depends on the number of tokens that are pushed into the stack. The use of the stack ensures that the operands for any operator are always readily available at the top of the stack.

Here is a snippet of how the arithmetic operations are processed:

Addition: nums[-2] += nums[-1]
Subtraction: nums[-2] -= nums[-1]
Multiplication: nums[-2] *= nums[-1]
Division: nums[-2] = int(nums[-2] / nums[-1])

Once finished, the program returns nums[0] as the result of the expression.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's use the following RPN expression as our example: "2 1 + 3 *" which, in standard notation, translates to (2 + 1) * 3.

By following the solution approach:

We initialize an empty list nums to serve as our stack: nums = [].
We iterate through the tokens: ["2", "1", "+", "3", "*"].

a. The first token is "2", which is a number. We push it onto the stack: nums = [2].

b. The second token is "1", which is also a number. We push it onto the stack: nums = [2, 1].

c. The third token is "+", which is an operator. We need to pop the top two numbers and apply the operator: - We pop the first operand: secondOperand = nums.pop(), which is 1. Now nums = [2]. - We pop the second operand: firstOperand = nums.pop(), which is 2. Now nums = []. - We add the two operands: stackResult = firstOperand + secondOperand, which equals 2 + 1 = 3. - We push the result onto the stack: nums = [3].

d. The fourth token is "3", a number. We push it onto the stack: nums = [3, 3].

e. The fifth token is "*", an operator: - We pop the second operand, secondOperand = nums.pop(), which is 3, leaving nums = [3]. - We pop the first operand, firstOperand = nums.pop(), which is 3, leaving nums = []. - We multiply the two operands: stackResult = firstOperand * secondOperand, which equals 3 * 3 = 9. - We push the result onto the stack: nums = [9].
After processing all the tokens, we are left with a single element in our stack nums = [9], which is our result.

So, the given RPN expression "2 1 + 3 *" evaluates to 9. Thus, the function would return 9 as the result of the expression.

Solution Implementation

1from typing import List
2
3class Solution:
4    def evalRPN(self, tokens: List[str]) -> int:
5        # Stack for storing numbers
6        number_stack = []
7      
8        # Loop over each token in the input list
9        for token in tokens:
10            # If the token represents a number (accounting for negative numbers)
11            if len(token) > 1 or token.isdigit():
12                # Convert the token to an integer and push it onto the stack
13                number_stack.append(int(token))
14            else:
15                # Perform the operation based on the operator
16                if token == "+":
17                    # Pop the last two numbers, add them, and push the result back
18                    number_stack[-2] += number_stack[-1]
19                elif token == "-":
20                    # Pop the last two numbers, subtract the second from the first, and push back
21                    number_stack[-2] -= number_stack[-1]
22                elif token == "*":
23                    # Pop the last two numbers, multiply, and push the result back
24                    number_stack[-2] *= number_stack[-1]
25                else: # Division
26                    # Ensure integer division for negative numbers too
27                    number_stack[-2] = int(float(number_stack[-2]) / number_stack[-1])
28                # Pop the last number (second operand) from the stack as it's been used
29                number_stack.pop()
30      
31        # Return the result which is the only number left in the stack
32        return number_stack[0]
33

1class Solution {
2    public int evalRPN(String[] tokens) {
3        Deque<Integer> stack = new ArrayDeque<>(); // Create a stack to hold integer values
4      
5        // Iterate over each token in the input array
6        for (String token : tokens) {
7            // Check if the token is a number (either single digit or multi-digit)
8            if (token.length() > 1 || Character.isDigit(token.charAt(0))) {
9                // Push the number onto the stack
10                stack.push(Integer.parseInt(token));
11            } else {
12                // Pop the top two elements for the operator
13                int secondOperand = stack.pop();
14                int firstOperand = stack.pop();
15              
16                // Apply the operator on the two operands based on the token
17                switch (token) {
18                    case "+":
19                        stack.push(firstOperand + secondOperand); // Add and push the result
20                        break;
21                    case "-":
22                        stack.push(firstOperand - secondOperand); // Subtract and push the result
23                        break;
24                    case "*":
25                        stack.push(firstOperand * secondOperand); // Multiply and push the result
26                        break;
27                    case "/":
28                        stack.push(firstOperand / secondOperand); // Divide and push the result
29                        break;
30                }
31            }
32        }
33      
34        // The final result is the only element in the stack, return it
35        return stack.pop();
36    }
37}
38

1#include <vector>
2#include <stack>
3#include <string>
4
5class Solution {
6public:
7    int evalRPN(vector<string>& tokens) {
8        // Create a stack to keep track of integers for evaluation
9        stack<int> numbers;
10
11        // Iterate over each token in the Reverse Polish Notation expression
12        for (const string& token : tokens) {
13            // If the token represents a number (can be multiple digits or negative)
14            if (token.size() > 1 || isdigit(token[0])) {
15                // Convert the string token to an integer and push onto the stack
16                numbers.push(stoi(token));
17            } else { // If the token is an operator
18                // Pop the second operand from the stack
19                int operand2 = numbers.top();
20                numbers.pop();
21
22                // Pop the first operand from the stack
23                int operand1 = numbers.top();
24                numbers.pop();
25
26                // Perform the operation based on the type of operator
27                switch (token[0]) {
28                    case '+': // Addition
29                        numbers.push(operand1 + operand2);
30                        break;
31                    case '-': // Subtraction
32                        numbers.push(operand1 - operand2);
33                        break;
34                    case '*': // Multiplication
35                        numbers.push(operand1 * operand2);
36                        break;
37                    case '/': // Division
38                        numbers.push(operand1 / operand2);
39                        break;
40                }                
41            }
42        }
43
44        // The final result is the only number remaining on the stack
45        return numbers.top();
46    }
47};
48

1// Evaluates the value of an arithmetic expression in Reverse Polish Notation.
2// Input is an array of tokens, where each token is either an operator or an operand.
3// Valid operators are: '+', '-', '*', and '/'.
4// Assumes the RPN expression is valid.
5function evalRPN(tokens: string[]): number {
6    // Stack to hold the operands for evaluation.
7    const stack: number[] = [];
8
9    // Helper function to check if a string is a numeric value.
10    function isNumeric(token: string): boolean {
11        return !isNaN(parseFloat(token)) && isFinite(Number(token));
12    }
13
14    // Process each token in the RPN expression.
15    for (const token of tokens) {
16        // If the token is a number, push it onto the stack.
17        if (isNumeric(token)) {
18            stack.push(Number(token));
19        } else {
20            // Since we know the token is an operator, pop two operands from the stack.
21            const secondOperand = stack.pop();
22            const firstOperand = stack.pop();
23
24            // Safety check: Ensure operands are valid numbers to avoid runtime errors.
25            if (typeof firstOperand === 'undefined' || typeof secondOperand === 'undefined') {
26                throw new Error("Invalid Expression: Insufficient operands for the operator.");
27            }
28
29            // Perform the operation according to the current token and push the result onto the stack.
30            switch (token) {
31                case '+':
32                    stack.push(firstOperand + secondOperand);
33                    break;
34                case '-':
35                    stack.push(firstOperand - secondOperand);
36                    break;
37                case '*':
38                    stack.push(firstOperand * secondOperand);
39                    break;
40                case '/':
41                    // Use truncation to conform to the requirements of integer division in RPN.
42                    // The '~~' is a double bitwise NOT operator, used here as a substitute for Math.trunc
43                    // which is to conform to the behavior specified in the problem statement.
44                    stack.push(~~(firstOperand / secondOperand));
45                    break;
46                default:
47                    throw new Error("Invalid token: Encountered an unknown operator.");
48            }
49        }
50    }
51
52    // The result of the expression is the last element of the stack.
53    // Safety check: there should only be one element left in the stack.
54    if (stack.length !== 1) {
55        throw new Error("Invalid Expression: The final stack should only contain one element.");
56    }
57
58    return stack[0];
59}
60

Time and Space Complexity

The given Python function evalRPN evaluates Reverse Polish Notation (RPN) expressions. The time complexity and space complexity analysis are as follows:

Time Complexity

The time complexity of this function is O(n), where n is the number of tokens in the input list tokens. This is because the function iterates through each token exactly once. Each operation within the loop, including arithmetic operations and stack operations (append and pop), can be considered to have constant time complexity, O(1).

Space Complexity

The space complexity of the code is O(n) in the worst case, where n is the number of tokens in the list. This worst-case scenario occurs when all tokens are numbers and are thus pushed onto the stack. In the best-case scenario, where the input is balanced with numbers and operators, the space complexity could be better than O(n), but the upper bound remains O(n). The auxiliary space required is for the nums stack used to perform the calculations. There are no other data structures that use significant memory.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: