An array tokens is given, where each entry is either an integer value or one arithmetic operator among +, -, *, and /. The division operator performs integer division with truncation toward zero.
The valid expression is written in Reverse Polish Notation. Each operator uses the two most recent operands before the operator. Evaluate the full expression and return the final integer result.
Example 1
Input: tokens = ["2", "1", "+", "3", "*"]
Output: 9
Explanation: Values 2 and 1 are added first to get 3. Then 3 * 3 gives 9.
Example 2
Input: tokens = ["4", "13", "5", "/", "+"]
Output: 6
Explanation: Values 13 and 5 form 13 / 5, truncated toward zero to 2. Then 4 + 2 gives 6.
Brute Force Approach
Reverse Polish Notation is also called postfix notation because every operator comes after its two operands. For example, 3 4 + becomes 7 without changing the expression’s value.
Scan the token list from left to right and find the first operator. Use the two values before the operator, calculate the result, and replace all three tokens with that result. Repeat the process until only one value remains.
Algorithm
A working list is built from
tokensso reductions can be performed without changing the original input.Repeat the reduction while more than one entry remains because every pass collapses one complete postfix operation.
Scan the current working list from left to right and stop at the first operator because the first operator marks the next complete postfix operation.
Read the two entries immediately before the first operator as numbers because a valid reduced expression guarantees both operands are ready at the selected position.
Calculate the operation with left operand first and right operand second so subtraction and division preserve the required order.
Replace the two operands and operator with the calculated result so the reduced value can serve as one operand in a later operation.
The scan is restarted after every reduction because earlier positions may become part of a new reducible expression.
Return the last remaining entry as an integer because the only surviving value represents the full expression.
Dry Run
RPN Brute
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Evaluates RPN with repeated reductions. int evalRPN(vector<string>& tokens) { vector<string> work = tokens; // Reduce until one value represents the expression. while (work.size() > 1) { int index = 0; // The first operator follows two ready operands. while (!isOperator(work[index])) { index++; } int leftValue = stoi(work[index - 2]); int rightValue = stoi(work[index - 1]); int result = applyOperation(leftValue, rightValue, work[index]); work.erase(work.begin() + index - 2, work.begin() + index + 1); work.insert(work.begin() + index - 2, to_string(result)); } return stoi(work[0]); }private: // Checks for one of the four arithmetic operators. bool isOperator(string token) { // Only arithmetic symbols trigger a reduction. if (token == "+" || token == "-" || token == "*" || token == "/") { return true; } return false; } // Applies the selected operator to the two operands. int applyOperation(int leftValue, int rightValue, string op) { // Addition combines the two ready operands. if (op == "+") { return leftValue + rightValue; } // Subtraction must keep the older operand on the left side. if (op == "-") { return leftValue - rightValue; } // Multiplication combines the two ready operands. if (op == "*") { return leftValue * rightValue; } return leftValue / rightValue; }};// Driver codeint main() { vector<string> tokens = {"4", "13", "5", "/", "+"}; Solution obj; cout << obj.evalRPN(tokens); return 0;}Complexity Analysis
Time Complexity: O(N2), where N is the number of tokens. Each reduction may scan the working list and may shift many later entries after deletion and insertion.
Space Complexity: O(N), because the working list stores a copy of all N tokens during reduction.
Optimal Approach
In a postfix expression, the left operand appears first and the right operand appears second. When an operator is found, the right operand is the latest stored value, while the left operand is just below it.
A stack follows this required LIFO order. Push every number onto the stack. For each operator, pop the right operand first and the left operand second, calculate the result, and push the result back. After all tokens are processed, one final value remains.
Algorithm
Begin with an empty stack so unresolved operands and intermediate results remain available for upcoming operators.
Process every token from left to right because postfix notation places each operator after both required operands.
Number tokens are converted into integers and pushed onto the stack because future operators may need stored values.
Pop the right operand before the left operand for every operator because the right operand entered the stack later.
Apply the selected operation with left operand first and right operand second so subtraction and division keep the required order.
Division is evaluated with truncation toward zero so the required integer rule is satisfied.
The operation result is pushed back onto the stack because the result may become an operand for a later operator.
Return the only remaining stack value because a valid complete expression produces exactly one result.
Dry Run
RPN Optimal
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Evaluates a Reverse Polish Notation expression with a stack. int evalRPN(vector<string>& tokens) { stack<int> values; // Tokens are processed in postfix order from left to right. for (string token : tokens) { // Operators consume the two most recent operands. if (isOperator(token)) { int rightValue = values.top(); values.pop(); int leftValue = values.top(); values.pop(); // The calculated expression value becomes a future operand. int result = applyOperation(leftValue, rightValue, token); values.push(result); } else { values.push(stoi(token)); } } return values.top(); }private: // Checks for one of the four arithmetic operators. bool isOperator(string token) { // Only arithmetic symbols trigger stack reduction. if (token == "+" || token == "-" || token == "*" || token == "/") { return true; } return false; } // Applies the selected operator to the two operands. int applyOperation(int leftValue, int rightValue, string op) { // Addition combines the two latest operands. if (op == "+") { return leftValue + rightValue; } // Subtraction must keep the older operand on the left side. if (op == "-") { return leftValue - rightValue; } // Multiplication combines the two latest operands. if (op == "*") { return leftValue * rightValue; } return leftValue / rightValue; }};// Driver codeint main() { vector<string> tokens = {"4", "13", "5", "/", "+"}; Solution obj; cout << obj.evalRPN(tokens); return 0;}Complexity Analysis
Time Complexity: O(N), where N is the number of tokens. Each token is processed once, and each stack push or pop takes constant time.
Space Complexity: O(N), because a valid binary Reverse Polish Notation expression with N tokens contains (N + 1) / 2 operands and (N - 1) / 2 operators. All operands can appear before any operator, so the stack may hold (N + 1) / 2, or about N / 2, values at once. The bound O(N/2) simplifies to O(N) after constants are removed.
Interview follow-up Questions
Operators appear after operands, so evaluation order is already fixed by token position. Every operator consumes the latest two available operands, removing the need for precedence rules or parentheses.
Be the first to add a comment.