Description

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.

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[-].

Solution

跟max tree相同的思路。expression tree的特点是数字都是叶子，节点都是符号，乘除的权重比较重在下面，加减的权重比较轻在上面，括号不在树里面，但是括号会增加括号内字符的权重。
故首先给每个要放进tree里的string一个权重，总权重=base+self weight，遇到正括号base+10，遇到反括号base-10.数字作为叶子self weight无限大，加减self weight为1，乘除self weight为2
root是整个expression权重最小的点，root.left是root左边权重最小的点，root.right是root右边权重最小的点。那么维护一个递增stack就能保证任一点在stack中左边的点就是该点左边expression中权重最小的点。

/**
 * Definition of ExpressionTreeNode:
 * public class ExpressionTreeNode {
 *     public String symbol;
 *     public ExpressionTreeNode left, right;
 *     public ExpressionTreeNode(String symbol) {
 *         this.symbol = symbol;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param expression: A string array
     * @return: The root of expression tree
     */

    public class Node {
        ExpressionTreeNode treeNode;
        int weight;
        public Node(ExpressionTreeNode treeNode, int weight) {
            this.treeNode = treeNode;
            this.weight = weight;
        }
    }

    public ExpressionTreeNode build(String[] expression) {
        // write your code here
        if (expression == null || expression.length == 0) {
            return null;
        }

        Stack<Node> stack = new Stack<Node>();
        int base = 0;
        for (int i = 0; i <= expression.length; i++) {
            String s = i == expression.length ? null : expression[i];
            if (s != null && (s.equals("(") || s.equals(")"))) {
                base = s.equals("(") ? base + 10 : base - 10;
                continue;
            }

            int weight = this.getWeight(s, base);
            Node cur = new Node(new ExpressionTreeNode(s), weight);
            if (stack.isEmpty() || stack.peek().weight < cur.weight) {
                stack.push(cur);
            } else {
                ExpressionTreeNode prev = null;
                while (!stack.isEmpty() && stack.peek().weight >= cur.weight) {
                    ExpressionTreeNode ans = stack.pop().treeNode;
                    ans.right = prev;
                    prev = ans;
                }

                cur.treeNode.left = prev;
                stack.push(cur);
            }
        }

        return stack.pop().treeNode.left;
    }

    private int getWeight(String s, int base) {
        if (s == null) {
            return Integer.MIN_VALUE;
        }

        if (s.equals("+") || s.equals("-")) {
            return base + 1;
        }

        if (s.equals("*") || s.equals("/")) {
            return base + 2;
        }

        return Integer.MAX_VALUE;
    }
}