# Reverse Polish Notation
[Reverse Polish notation | Wikipedia](https://wikipedia.org/wiki/Reverse_Polish_notation), aka the postfix notation.
## Reduce List in Place
Very straightforward solution. This solution runs in $O(n)$ time, since modifying a [[linked-list|list]] takes $O(n)$ time, and we're scanning the list from left to right, conducted $O(n)$ operations. The space complexity is nicely $O(1)$.
With a doubly-linked list, this algorithm can be reduced to $O(n)$ time, since we're traversing it.
```python
operations = {
"+": lambda a, b: a + b,
"-": lambda a, b: a - b,
"/": lambda a, b: int(a / b),
"*": lambda a, b: a * b,
}
i = 0
while len(tokens) > 1:
while tokens[i] not in operations:
i += 1
operator = tokens[i]
operand1 = int(tokens[i - 2])
operand2 = int(tokens[i - 1])
tokens[i] = operations[operator](operand1, operand2)
tokens.pop(i - 2)
tokens.pop(i - 2)
i -= 1 # move on to the next value
return int(tokens[0])
```
The dictionary of lambda functions can also be replaced with a `match` statement.
## Evaluate with Stack
```python
operations = {
"+": lambda a, b: a + b,
"-": lambda a, b: a - b,
"/": lambda a, b: int(a / b),
"*": lambda a, b: a * b,
}
operands = []
for token in tokens:
if token in operations:
operation = operations[token]
operand1 = operands.pop()
operand2 = operands.pop()
operands.append(operation[token](operand1, operand2))
else:
operands.append(int(token))
return operands.pop()
```