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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
|
from consts import *
class Node:
def __init__(self, node_type, value=None, subtype=None):
self.type = node_type
self.value = value
self.subtype = subtype
self.parent = None
self.right = None
self.left = None
def __eq__(self, other):
return self.type == other.type and self.value == other.value
def __repr__(self):
if self.type == LEFT_PARENTHESIS:
return "Node(LEFT_PARENTHESIS)"
if self.type == RIGHT_PARENTHESIS:
return "Node(RIGHT_PARENTHESIS)"
if self.type == NUMBER:
return f"Node({self.value})"
if self.type == OPERATOR:
return f"Node({self.subtype})"
if self.type == COMMA:
return f"Node(COMMA)"
if self.type == SYMBOL:
return f"Node(SYMBOL {self.value})"
if self.type == FUNCALL:
return f"Node(FUNCALL {self.value})"
__str__ = __repr__
def parse_parenthesis(tokens, start):
end = start
depth = 0
while True:
token = tokens[end]
if token.type == RIGHT_PARENTHESIS:
depth -= 1
if token.type == LEFT_PARENTHESIS:
depth += 1
if depth == 0 and token.type == RIGHT_PARENTHESIS:
break
end += 1
node = build_tree(tokens[start + 1: end])
return node, end
def parse_args(tokens, start):
end = start
depth = 0
while True:
token = tokens[end]
if token.type == RIGHT_PARENTHESIS:
depth -= 1
if token.type == LEFT_PARENTHESIS:
depth += 1
if depth == 0 and token.type == RIGHT_PARENTHESIS:
break
end += 1
args = []
arg = []
for token in tokens[start + 1: end]:
if token.type != COMMA:
arg.append(token)
else:
args.append(arg.copy())
arg.clear()
if len(arg) != 0:
args.append(arg)
return list(map(build_tree, args))
def build_tree(tokens):
state = STATE_NAME
i = 0
current_node = None
while i < len(tokens):
token = tokens[i]
if state == STATE_OPERATOR and token.type == LEFT_PARENTHESIS:
args = parse_args(tokens, i)
current_node.type = FUNCALL
current_node.value = (current_node.value, args)
elif token.type in [LEFT_PARENTHESIS, NUMBER, SYMBOL] or token.subtype == UNARY:
if token.type == LEFT_PARENTHESIS:
node, i = parse_parenthesis(tokens, i)
state = STATE_NAME
elif token.type == NUMBER:
node = Node(NUMBER, value=token.value)
state = STATE_OPERATOR
elif token.type == SYMBOL:
node = Node(SYMBOL, value=token.value)
state = STATE_OPERATOR
elif token.subtype == UNARY:
node = Node(OPERATOR, subtype=UNARY)
node.left = Node(OPERATOR, subtype=token.value)
state = STATE_NAME
if current_node is None:
current_node = node
elif current_node.type == NUMBER:
raise ValueError("Not a valid expression")
elif current_node.type == OPERATOR:
if current_node.left is None:
current_node.left = node
node.parent = current_node
elif current_node.right is None:
current_node.right = node
node.parent = current_node
current_node = node
else:
raise ValueError("Not a valid expression")
elif token.type == OPERATOR:
node = Node(token.type, subtype=token.subtype, value=token.value)
if current_node is None:
raise ValueError("Not a valid expression")
elif current_node.type in [NUMBER, OPERATOR, FUNCALL]:
while current_node.parent is not None:
if PRECEDENCE[current_node.parent.subtype] < PRECEDENCE[node.subtype]:
node.parent = current_node.parent
if node.parent is not None:
node.parent.right = node
break
current_node = current_node.parent
current_node.parent = node
node.left = current_node
current_node = node
else:
print(current_node, token)
raise ValueError("Not a valid expression")
state = STATE_NAME
i += 1
while current_node.parent is not None:
current_node = current_node.parent
return current_node
|
