Evaluate Reverse Polish Notation
Problem Statement
You are given an array of strings tokens
that represents a valid arithmetic expression in Reverse Polish Notation.
Return the integer that represents the evaluation of the expression.
- The operands may be integers or the results of other operations.
- The operators include
'+'
,'-'
,'*'
, and'/'
. - Assume that division between integers always truncates toward zero.
Example 1:
Input: tokens = ["1","2","+","3","*","4","-"]Output: 5Explanation: ((1 + 2) * 3) - 4 = 5
Constraints:
1 <= tokens.length <= 1000
.- tokens[i] is
"+"
,"-"
,"*"
, or"/"
, or a string representing an integer in the range[-100, 100]
.
You should aim for a solution with O(n)
time and O(n)
space, where n
is the size of the input array.
Recommended Time and Space Complexity
You should aim for a solution with O(n)
time and O(n)
space, where n
is the size of the input array.
Hint 1
A brute force solution would involve repeatedly finding an operator + - * /
in the array and modifying the array by computing the result for that operator and two operands to its left. This would be an O(n^2)
solution. Can you think of a better way? Maybe we can use a data structure to handle operations efficiently.
Hint 2
We can use a stack. We iterate through the array, and if we encounter a number, we push it onto the stack. If we encounter an operator, we pop two elements from the stack, treat them as operands, and solve the equation using the current operator. Then, we push the result back onto the stack. Why does this work?
Hint 3
As the array has postfix expression, stack helps us to maintain the correct order of operations by ensuring that we always use the most recent operands (those closest to the operator) when performing the operation. After the iteration, the final result is left in the stack.
Solution
Brute Force
def eval_rpn(tokens: list[str]) -> int: while len(tokens) > 1: for i in range(len(tokens)): if tokens[i] in "+-*/": a = int(tokens[i-2]) b = int(tokens[i-1]) if tokens[i] == '+': result = a + b elif tokens[i] == '-': result = a - b elif tokens[i] == '*': result = a * b elif tokens[i] == '/': result = int(a / b) tokens = tokens[:i-2] + [str(result)] + tokens[i+1:] break return int(tokens[0])
Time complexity: O(n^2)
Space complexity: O(n)
Doubly Linked List
class DoublyLinkedList: def __init__(self, val, next=None, prev=None): self.val = val self.next = next self.prev = prev
def eval_rpn(tokens: list[str]) -> int: head = DoublyLinkedList(tokens[0]) curr = head
for i in range(1, len(tokens)): curr.next = DoublyLinkedList(tokens[i], prev=curr) curr = curr.next
while head is not None: if head.val in "+-*/": l = int(head.prev.prev.val) r = int(head.prev.val) if head.val == '+': res = l + r elif head.val == '-': res = l - r elif head.val == '*': res = l * r else: res = int(l / r)
head.val = str(res) head.prev = head.prev.prev.prev if head.prev is not None: head.prev.next = head
ans = int(head.val) head = head.next
return ans
Time complexity: O(n)
Space complexity: O(n)
Recursion
def eval_rpn(tokens: list[str]) -> int: def dfs(): token = tokens.pop() if token not in "+-*/": return int(token)
right = dfs() left = dfs()
if token == '+': return left + right elif token == '-': return left - right elif token == '*': return left * right elif token == '/': return int(left / right)
return dfs()
Time complexity: O(n)
Space complexity: O(n)
Stack
def eval_rpn(tokens: list[str]) -> int: stack = [] for token in tokens: if token == "+": stack.append(stack.pop() + stack.pop()) elif token == "-": a, b = stack.pop(), stack.pop() stack.append(b - a) elif token == "*": stack.append(stack.pop() * stack.pop()) elif token == "/": a, b = stack.pop(), stack.pop() stack.append(int(float(b) / a)) else: stack.append(int(token)) return stack[0]
Time complexity: O(n)
Space complexity: O(n)