Expression Tree Build

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

Clarification

See wiki: Expression Tree

public class Solution {
    /**
     * @param expression: A string array
     * @return: The root of expression tree
     */
    public ExpressionTreeNode build(String[] expression) {
        // write your code here
        int base = 0;
        int val = 0;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        for(int i = 0; i <= expression.length; i++){
            if(i != expression.length){
                if(expression[i].equals("(")){
                    base += 10;
                    continue;
                }
                if(expression[i].equals(")")){
                    base -= 10;
                    continue;
                }
                val = getValue(base, expression[i]);
            }
            TreeNode right = i == expression.length ? new TreeNode(Integer.MIN_VALUE, "") : new TreeNode(val, expression[i]);
            while(!stack.isEmpty()){
                if(right.val <= stack.peek().val){
                    TreeNode cur = stack.pop();
                    if(stack.isEmpty()){
                        right.root.left = cur.root;
                    } else{
                        TreeNode left = stack.peek();
                        if(left.val < right.val){ // operator compare
                            right.root.left = cur.root;
                        } else{
                            left.root.right = cur.root;
                        }
                    }
                   
                } else break;
            }
            stack.push(right);
        }
        return stack.peek().root.left;
    }
   
    private int getValue(int base, String s){
        if(s.equals("+") || s.equals("-")){
            return 1+base;
        }
       
        if(s.equals("/") || s.equals("*")){
            return 2+base;
        }
        return Integer.MAX_VALUE;
    }
   
    class TreeNode{
        public int val;
        public String s;
        public ExpressionTreeNode root;
        public TreeNode left, right;
        public TreeNode(int val, String s){
            this.val = val;
            this.root = new ExpressionTreeNode(s);
        }
       
    }
}