1# *************************************************************
2#
3#  Licensed to the Apache Software Foundation (ASF) under one
4#  or more contributor license agreements.  See the NOTICE file
5#  distributed with this work for additional information
6#  regarding copyright ownership.  The ASF licenses this file
7#  to you under the Apache License, Version 2.0 (the
8#  "License"); you may not use this file except in compliance
9#  with the License.  You may obtain a copy of the License at
10#
11#    http://www.apache.org/licenses/LICENSE-2.0
12#
13#  Unless required by applicable law or agreed to in writing,
14#  software distributed under the License is distributed on an
15#  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
16#  KIND, either express or implied.  See the License for the
17#  specific language governing permissions and limitations
18#  under the License.
19#
20# *************************************************************
21
22
23import sys
24import globals
25
26def toString (node):
27
28    if node == None:
29        return ''
30
31    chars = '('
32
33    if type(node.left) == type(0):
34        chars += "%d"%node.left
35    else:
36        chars += toString(node.left)
37
38    chars += node.op
39
40    if type(node.right) == type(0):
41        chars += "%d"%node.right
42    else:
43        chars += toString(node.right)
44
45    chars += ")"
46
47    return chars
48
49class Node(object):
50    def __init__ (self):
51        self.left = None
52        self.right = None
53        self.parent = None
54        self.op = None
55
56class ExpParser(object):
57
58    def __init__ (self, tokens):
59        self.tokens = tokens
60
61    def jumpToRoot (self):
62        while self.ptr.parent != None:
63            self.ptr = self.ptr.parent
64
65    def build (self):
66        self.ptr = Node()
67
68        for token in self.tokens:
69
70            if token in '+-':
71                if self.ptr.left == None:
72                    raise globals.ParseError ('')
73                if self.ptr.right == None:
74                    self.ptr.op = token
75                else:
76                    self.jumpToRoot()
77                    self.ptr.parent = Node()
78                    self.ptr.parent.left = self.ptr
79                    self.ptr = self.ptr.parent
80                    self.ptr.op = token
81
82            elif token in '*/':
83                if self.ptr.left == None:
84                    raise globals.ParseError ('')
85                elif self.ptr.right == None:
86                    self.ptr.op = token
87                else:
88                    num = self.ptr.right
89                    self.ptr.right = Node()
90                    self.ptr.right.parent = self.ptr
91                    self.ptr.right.left = num
92                    self.ptr.right.op = token
93                    self.ptr = self.ptr.right
94
95            elif token == '(':
96                if self.ptr.left == None:
97                    self.ptr.left = Node()
98                    self.ptr.left.parent = self.ptr
99                    self.ptr = self.ptr.left
100                elif self.ptr.right == None:
101                    self.ptr.right = Node()
102                    self.ptr.right.parent = self.ptr
103                    self.ptr = self.ptr.right
104                else:
105                    raise globals.ParseError ('')
106
107            elif token == ')':
108                if self.ptr.left == None:
109                    raise globals.ParseError ('')
110                elif self.ptr.right == None:
111                    raise globals.ParseError ('')
112                elif self.ptr.parent == None:
113                    pass
114                else:
115                    self.ptr = self.ptr.parent
116
117            else:
118                num = int(token)
119                if self.ptr.left == None:
120                    self.ptr.left = num
121                elif self.ptr.right == None:
122                    self.ptr.right = num
123                else:
124                    raise globals.ParseError ('')
125
126    def dumpTree (self):
127        self.jumpToRoot()
128        print toString(self.ptr)
129