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