1 files changed, 139 insertions, 0 deletions
diff --git a/parser.py b/parser.py
new file mode 100644
index 0000000..1cad137
--- /dev/null
+++ b/parser.py
@@ -0,0 +1,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