# *************************************************************
#  
#  Licensed to the Apache Software Foundation (ASF) under one
#  or more contributor license agreements.  See the NOTICE file
#  distributed with this work for additional information
#  regarding copyright ownership.  The ASF licenses this file
#  to you under the Apache License, Version 2.0 (the
#  "License"); you may not use this file except in compliance
#  with the License.  You may obtain a copy of the License at
#  
#    http://www.apache.org/licenses/LICENSE-2.0
#  
#  Unless required by applicable law or agreed to in writing,
#  software distributed under the License is distributed on an
#  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
#  KIND, either express or implied.  See the License for the
#  specific language governing permissions and limitations
#  under the License.
#  
# *************************************************************


import sys
import globals

def toString (node):

    if node == None:
        return ''

    chars = '('

    if type(node.left) == type(0):
        chars += "%d"%node.left
    else:
        chars += toString(node.left)

    chars += node.op

    if type(node.right) == type(0):
        chars += "%d"%node.right
    else:
        chars += toString(node.right)

    chars += ")"

    return chars

class Node(object):
    def __init__ (self):
        self.left = None
        self.right = None
        self.parent = None
        self.op = None

class ExpParser(object):

    def __init__ (self, tokens):
        self.tokens = tokens

    def jumpToRoot (self):
        while self.ptr.parent != None:
            self.ptr = self.ptr.parent

    def build (self):
        self.ptr = Node()

        for token in self.tokens:

            if token in '+-':
                if self.ptr.left == None:
                    raise globals.ParseError ('')
                if self.ptr.right == None:
                    self.ptr.op = token
                else:
                    self.jumpToRoot()
                    self.ptr.parent = Node()
                    self.ptr.parent.left = self.ptr
                    self.ptr = self.ptr.parent
                    self.ptr.op = token

            elif token in '*/':
                if self.ptr.left == None:
                    raise globals.ParseError ('')
                elif self.ptr.right == None:
                    self.ptr.op = token
                else:
                    num = self.ptr.right
                    self.ptr.right = Node()
                    self.ptr.right.parent = self.ptr
                    self.ptr.right.left = num
                    self.ptr.right.op = token
                    self.ptr = self.ptr.right

            elif token == '(':
                if self.ptr.left == None:
                    self.ptr.left = Node()
                    self.ptr.left.parent = self.ptr
                    self.ptr = self.ptr.left
                elif self.ptr.right == None:
                    self.ptr.right = Node()
                    self.ptr.right.parent = self.ptr
                    self.ptr = self.ptr.right
                else:
                    raise globals.ParseError ('')

            elif token == ')':
                if self.ptr.left == None:
                    raise globals.ParseError ('')
                elif self.ptr.right == None:
                    raise globals.ParseError ('')
                elif self.ptr.parent == None:
                    pass
                else:
                    self.ptr = self.ptr.parent

            else:
                num = int(token)
                if self.ptr.left == None:
                    self.ptr.left = num
                elif self.ptr.right == None:
                    self.ptr.right = num
                else:
                    raise globals.ParseError ('')

    def dumpTree (self):
        self.jumpToRoot()
        print toString(self.ptr)