DSA
Evaluate Reverse Polish Notation
Stacks & Queues. Time O(n), Space O(1).
Approach: Stack-Based Evaluation#
Reverse Polish Notation (postfix) places operators after their operands, which eliminates the need for parentheses and operator precedence rules. A stack is the natural data structure: scan tokens left to right, pushing numbers onto the stack. When an operator is encountered, pop the top two operands, apply the operator, and push the result back. The order of popping matters — the first pop gives the right operand (num2) and the second gives the left operand (num1), since the left operand was pushed first. After processing all tokens, the single value remaining on the stack is the final result.
cpp
class Solution {
public:
int evaluate(int num1, int num2, string op){
if(op == "+") return num1 + num2;
if(op == "-") return num1 - num2;
if(op == "*") return num1 * num2;
if(op == "/") return num1 / num2;
return -1;
}
int evalRPN(vector<string>& tokens) {
int t = tokens.size();
if(t==1)
return stoi(tokens[0]);
stack<int> stk;
int ans = 0;
for(int i=0;i<t;i++){
if(tokens[i] != "+" && tokens[i] != "-" && tokens[i] != "*" && tokens[i] != "/"){
stk.push(stoi(tokens[i]));
}
else{
int num2 = stk.top();
stk.pop();
int num1 = stk.top();
stk.pop();
ans = evaluate(num1, num2, tokens[i]);
stk.push(ans);
}
}
return ans;
}
};
Time Complexity: O(n)
Space Complexity: O(1)