Expression Tree Build

Question

The structure of Expression Tree is a binary tree to evaluate certain expressions. All leaves of the Expression Tree have an number string value. All non-leaves of the Expression Tree have an operator string value.

Now, given an expression array, build the expression tree of this expression, return the root of this expression tree.

Have you met this question in a real interview? Yes Example For the expression (2*6-(23+7)/(1+2)) (which can be represented by ["2" "*" "6" "-" "(" "23" "+" "7" ")" "/" "(" "1" "+" "2" ")"]). The expression tree will be like

                 [ - ]
             /          \
        [ * ]              [ / ]
      /     \           /         \
    [ 2 ]  [ 6 ]      [ + ]        [ + ]
                     /    \       /      \
                   [ 23 ][ 7 ] [ 1 ]   [ 2 ] .

After building the tree, you just need to return root node [-].

Thoughts

对每个操作符，数字，赋予一定的priority来比较，每个都有一个base 遇到( 就将目前的base加10, 遇到)就将目前的base减10

priorities:

• +, - base + 1
• *, / base + 2
• number maxint

叶子节点都是number, 优先级越高的越在下面

对于这个expression array采用Min Tree的方法来建立， 具体做法与max tree那一题条件改一下即可

注意：

• 不要把括号(, )加入到tree里面，它们只改变优先级

Solution

"""
Definition of ExpressionTreeNode:
class ExpressionTreeNode:
    def __init__(self, symbol):
        self.symbol = symbol
        self.left, self.right = None, None
"""


class MyNode():
    def __init__(self, val, s):
        self.left = None
        self.right = None
        self.val = val
        self.node = ExpressionTreeNode(s)

class Solution:
    # @param expression: A string list
    # @return: The root of expression tree
    def build(self, expression):
        # write your code here
        if not expression:
            return None
        root = self.buildTree(expression)
        return self.copyTree(root)

    def copyTree(self, root):
        if not root:
            return None
        root.node.left = self.copyTree(root.left)
        root.node.right = self.copyTree(root.right)
        return root.node

    def buildTree(self, expression):
        stack = []
        val = 0
        base = 0
        for i, s in enumerate(expression):
            #get priority
            if s == "(":
                base += 10
                #bracket doesn't add into stack, just continue
                continue
            elif s == ")":
                base -= 10
                continue
            val = self.getVal(s, base)
            curr = MyNode(val, s)
            while stack and val <= stack[-1].val:
                curr.left = stack.pop()
            if stack:
                stack[-1].right = curr
            stack.append(curr)
        if not stack:
            return None
        return stack[0]

    def getVal(self, s, base):
        if s == "+" or s == "-":
            return 1 + base
        elif s == "*" or s == "/":
            return 2 + base

        return sys.maxint