1
2import sys
3import globals
4
5def toString (node):
6
7    if node == None:
8        return ''
9
10    chars = '('
11
12    if type(node.left) == type(0):
13        chars += "%d"%node.left
14    else:
15        chars += toString(node.left)
16
17    chars += node.op
18
19    if type(node.right) == type(0):
20        chars += "%d"%node.right
21    else:
22        chars += toString(node.right)
23
24    chars += ")"
25
26    return chars
27
28class Node(object):
29    def __init__ (self):
30        self.left = None
31        self.right = None
32        self.parent = None
33        self.op = None
34
35class ExpParser(object):
36
37    def __init__ (self, tokens):
38        self.tokens = tokens
39
40    def jumpToRoot (self):
41        while self.ptr.parent != None:
42            self.ptr = self.ptr.parent
43
44    def build (self):
45        self.ptr = Node()
46
47        for token in self.tokens:
48
49            if token in '+-':
50                if self.ptr.left == None:
51                    raise globals.ParseError ('')
52                if self.ptr.right == None:
53                    self.ptr.op = token
54                else:
55                    self.jumpToRoot()
56                    self.ptr.parent = Node()
57                    self.ptr.parent.left = self.ptr
58                    self.ptr = self.ptr.parent
59                    self.ptr.op = token
60
61            elif token in '*/':
62                if self.ptr.left == None:
63                    raise globals.ParseError ('')
64                elif self.ptr.right == None:
65                    self.ptr.op = token
66                else:
67                    num = self.ptr.right
68                    self.ptr.right = Node()
69                    self.ptr.right.parent = self.ptr
70                    self.ptr.right.left = num
71                    self.ptr.right.op = token
72                    self.ptr = self.ptr.right
73
74            elif token == '(':
75                if self.ptr.left == None:
76                    self.ptr.left = Node()
77                    self.ptr.left.parent = self.ptr
78                    self.ptr = self.ptr.left
79                elif self.ptr.right == None:
80                    self.ptr.right = Node()
81                    self.ptr.right.parent = self.ptr
82                    self.ptr = self.ptr.right
83                else:
84                    raise globals.ParseError ('')
85
86            elif token == ')':
87                if self.ptr.left == None:
88                    raise globals.ParseError ('')
89                elif self.ptr.right == None:
90                    raise globals.ParseError ('')
91                elif self.ptr.parent == None:
92                    pass
93                else:
94                    self.ptr = self.ptr.parent
95
96            else:
97                num = int(token)
98                if self.ptr.left == None:
99                    self.ptr.left = num
100                elif self.ptr.right == None:
101                    self.ptr.right = num
102                else:
103                    raise globals.ParseError ('')
104
105    def dumpTree (self):
106        self.jumpToRoot()
107        print toString(self.ptr)
108
109
110
111
112