🎨Now live: Try our Free AI Image Generation Feature

Intuition
Reverse Polish Notation (RPN) is a mathematical notation in which every operator follows all of its operands. It is also known as postfix notation. To evaluate an expression in RPN, a stack is used to store operands, and operators are applied to the operands in the correct order. This approach naturally fits the stack data structure, as it allows easy management of operands and operators.
Approach
- Initialization: - Use a stack to keep track of the operands as we iterate through the tokens.
- Iteration:
- For each token in the input
tokens
: - If the token is an operand (a number), push it onto the stack. - If the token is an operator (+
,-
,*
,/
), pop the top two operands from the stack, apply the operator, and push the result back onto the stack. - Operations:
- When an operator is encountered, pop the top two elements from the stack. Let
val2
be the first popped element andval1
be the second. - Apply the operator toval1
andval2
: - For+
, pushval1 + val2
. - For-
, pushval1 - val2
. - For*
, pushval1 * val2
. - For/
, pushint(val1 / val2)
to ensure truncation towards zero. - Final Result: - After processing all tokens, the stack will contain a single element, which is the result of the RPN expression.
Complexity
Time Complexity:
- The time complexity is O(n), where n is the number of tokens. Each token is processed exactly once.
Space Complexity:
- The space complexity is O(n) in the worst case, where n is the number of tokens. The stack size can grow up to n/2 in the case of alternating operands and operators.
Code
C++
class Solution {
public:
int evalRPN(vector& tokens) {
stack stack;
for (const string& token : tokens) {
if (isdigit(token.back())) {
stack.push(stoi(token));
} else {
int val2 = stack.top();
stack.pop();
int val1 = stack.top();
stack.pop();
int result;
switch (token[0]) {
case '*':
result = val1 * val2;
break;
case '+':
result = val1 + val2;
break;
case '-':
result = val1 - val2;
break;
case '/':
result = val1 / val2;
break;
}
stack.push(result);
}
}
return stack.top();
}
};
Python
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
stack = []
for token in tokens:
if token.lstrip('-').isdigit():
stack.append(int(token))
else:
val2 = stack.pop()
val1 = stack.pop()
if token == '*':
stack.append(val1 * val2)
elif token == '+':
stack.append(val1 + val2)
elif token == '-':
stack.append(val1 - val2)
elif token == '/':
stack.append(int(val1 / val2))
return stack.pop()
Java
class Solution {
public int evalRPN(String[] tokens) {
Stack stack = new Stack<>();
for (String token : tokens) {
if (isNumeric(token)) {
stack.push(Integer.parseInt(token));
} else {
int val2 = stack.pop();
int val1 = stack.pop();
int result;
switch (token) {
case "*":
result = val1 * val2;
break;
case "+":
result = val1 + val2;
break;
case "-":
result = val1 - val2;
break;
case "/":
result = val1 / val2;
break;
default:
throw new IllegalArgumentException("Invalid operator: " + token);
}
stack.push(result);
}
}
return stack.pop();
}
private boolean isNumeric(String str) {
try {
Integer.parseInt(str);
return true;
} catch (NumberFormatException e) {
return false;
}
}
}
JavaScript
var evalRPN = function (tokens) {
let stack = [];
for (let i = 0; i < tokens.length; i++)
{
let val = Number(tokens[i]);
if (!isNaN(val)) {
stack.push(val)
} else {
let val = stack.pop();
let val1 = stack.pop();
switch (tokens[i]) {
case '*':
out = val1 * val
break;
case '+':
out = val1 + val
break;
case '-':
out = val1 - val
break;
case '/':
out = Math.trunc(val1 / val)
break;
}
stack.push(out)
}
}
return stack.pop()
};