150. Evaluate Reverse Polish Notation¶
Each operator requires the two most recent operands, and this requirement naturally chains as we combine unprocessed numbers with intermediate results. For example:
The above sequence shows a last-in, first-out (LIFO) access pattern. Because of this, the problem can be solved using a stack while processing tokens from left to right. The stack stores both integer operands and intermediate results.
- Operand: If the current token is a number, push it onto the stack.
- Operator: If the token is an operator (+, -, *, /), pop the top two values from the stack, apply the operation in the correct order (second operand operator first operand), and push the result back onto the stack.
Final Result: After all tokens are processed, the top of the stack contains the evaluated result.
Runtime Complexity
Time: \(O(n)\), single pass over \(tokens\) array
Space: \(O(n)\), \(stk\) can grow upto size of \(tokens\) array
class Solution:
def evalRPN(self, tokens: list[str]) -> int:
stk = []
op = {"+", "-", "*", "/"}
for token in tokens:
if token not in op:
stk.append(int(token))
else:
b= stk.pop()
a = stk.pop()
if token == "+":
stk.append(a+b)
elif token == "-":
stk.append(a-b)
elif token == "*":
stk.append(a*b)
elif token == "/":
stk.append(int(a/b))
return stk.pop()
func evalRPN(tokens []string) int {
var stk []int
op := map[string]struct{}{
"+": struct{}{},
"-": struct{}{},
"*": struct{}{},
"/": struct{}{},
}
for _, token := range tokens {
if _, ok := op[token]; !ok {
token, _ := strconv.Atoi(token)
stk = append(stk, token)
} else {
t2, t1 := stk[len(stk)-1], stk[len(stk)-2]
var eval int
if token == "+" {
eval = t1 + t2
} else if token == "-" {
eval = t1 - t2
} else if token == "*" {
eval = t1 * t2
} else if token == "/" {
eval = t1 / t2
}
stk = append(stk[:len(stk)-2], eval)
}
}
return stk[len(stk)-1]
}