-
Notifications
You must be signed in to change notification settings - Fork 3
/
163_JaneStreet_Evaluate_Reverse_Polish_Notation.py
executable file
·82 lines (65 loc) · 2.34 KB
/
163_JaneStreet_Evaluate_Reverse_Polish_Notation.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
"""
This problem was asked by Jane Street.
Given an arithmetic expression in Reverse Polish Notation, write a program to evaluate it.
The expression is given as a list of numbers and operands. For example: [5, 3, '+'] should return 5 + 3 = 8.
For example, [15, 7, 1, 1, '+', '-', '/', 3, '*', 2, 1, 1, '+', '+', '-']
should return 5, since it is equivalent to ((15 / (7 - (1 + 1))) * 3) - (2 + (1 + 1)) = 5.
You can assume the given expression is always valid.
"""
# keep a window of 3, start from the left of the array and perform th operation
# when the 3rd element of the window contains an arithmetic op
def eval_reverse_polish(exp:list):
start = 0
end = start+2
while isinstance(exp[end], (int, float, complex)) and not isinstance(exp[end], bool):
start = start+1
end = end+1
op = exp[end]
val = 0
if op == "+":
# add values
val = exp[start] + exp[start+1]
elif op == '-':
# subtract vals
val = exp[start] - exp[start+1]
elif op == '/':
# divide vals
val = exp[start] / exp[start+1]
elif op == '*':
# multiply vals
val = exp[start] * exp[start+1]
else:
raise Exception("Unknown arithmetic operation : {}".format(op))
exp[start:end+1] = [val]
if len(exp) == 1:
return exp[0]
else:
return eval_reverse_polish(exp)
# better implementation
# solve it with stack
PLUS = "+"
MINUS = "-"
MULTIPLY = "*"
DIVIDE = "/"
OPS = [PLUS, MINUS, MULTIPLY, DIVIDE]
def eval_reverse_polish_redux(exp:list):
stack = []
for symbol in exp:
if symbol in OPS:
# take out the most recent to values and apply the operation on them
val2, val1 = stack.pop(-1), stack.pop(-1)
if symbol == PLUS:
stack.append(val1 + val2)
elif symbol == MINUS:
stack.append(val1 - val2)
elif symbol == MULTIPLY:
stack.append(val1 * val2)
elif symbol == DIVIDE:
stack.append(val1 / val2)
else:
# add to the top of the stack
stack.append(symbol)
return stack[0]
if __name__ == '__main__':
print(eval_reverse_polish([15, 7, 1, 1, '+', '-', '/', 3, '*', 2, 1, 1, '+', '+', '-']))
print(eval_reverse_polish_redux([15, 7, 1, 1, '+', '-', '/', 3, '*', 2, 1, 1, '+', '+', '-']))