Initial Solution
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
stack = []
op = ['+', '-', '*', '/']
for t in tokens:
# print(stack)
if t in op:
num2 = stack[-1]
stack.pop()
num1 = stack[-1]
stack.pop()
if t == "+":
stack.append(num1 + num2)
elif t == "-":
stack.append(num1 - num2)
elif t == "*":
stack.append(num1 * num2)
elif t == "/":
stack.append(int(num1 / num2))
else:
stack.append(int(t))
return stack[-1]
Python
복사
Time complexity and Space Complexity
Time Complexity: O(n), where n is the number of tokens. We iterate through each token once, and stack operations (push/pop) are O(1).
Space Complexity: O(n) in the worst case, where all tokens are operands and get pushed onto the stack before any operations are performed.
Other Better Solutions
Solution Using Dictionary for Operations
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
stack = []
operations = {
'+': lambda a, b: a + b,
'-': lambda a, b: a - b,
'*': lambda a, b: a * b,
'/': lambda a, b: int(a / b)
}
for token in tokens:
if token in operations:
b = stack.pop()
a = stack.pop()
stack.append(operations[token](a, b))
else:
stack.append(int(token))
return stack[-1]
Python
복사
This solution uses a dictionary to map operators to lambda functions, making the code more concise and eliminating the need for multiple if-elif statements. The time and space complexity remain the same as the initial solution.