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

Clarification

See wiki:
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[-].

思路：

每一个元素是一个节点，如果我们定义优先级高的元素先进入树（靠近叶节点), 而优先级低的后进入树 （靠近根节点）

那么该问题就转化为了一个可以用单调栈解决的问题，找到一个元素左边和右边第一个小于自己的，然后给其中较小的做子树，如果两边一样，就给左边的做子树。（类似min tree/max tree 做法，从叶节点出发找根节点）

/**
 * 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;
 *     }
 * }
 */

// equavilent to find the first node on the left and right that's smaller than the current node
// give it priority level
class ReturnType {
    ExpressionTreeNode root;
    int priority;
    public ReturnType(ExpressionTreeNode root, int priority) {
        this.root = root;
        this.priority = priority;
    }
}
public class Solution {
    /*
     * @param expression: A string array
     * @return: The root of expression tree
     */
    private int PRIORITY_ADD = 1;
    private int PRIORITY_MUL = 2;
    private int PRIORITY_NUM = Integer.MAX_VALUE;
    public ExpressionTreeNode build(String[] expression) {
        // write your code here
        if (expression == null || expression.length == 0) {
            return null;
        }

        Stack<ReturnType> stack = new Stack<ReturnType>();
        ExpressionTreeNode ans = null;
        int base = 1;
        for (int i = 0; i <= expression.length; i++) {

            int priority = base;
            //System.out.println(base);
            ReturnType cur = null;
            if (i == expression.length) {
                priority = Integer.MIN_VALUE;
                cur = new ReturnType(null, priority);
            } else {
                if (expression[i].equals("+") || expression[i].equals("-")) {
                    priority += PRIORITY_ADD;
                } else if (expression[i].equals("*") || expression[i].equals("/")) {
                    priority += PRIORITY_MUL;
                } else if (expression[i].equals("(")) {
                    base *= 10;
                    continue;
                } else if (expression[i].equals(")")) {
                    base /= 10;
                    continue;
                } else {
                    priority = Integer.MAX_VALUE;
                }

                cur = new ReturnType(new ExpressionTreeNode(expression[i]), priority);
            }

            // System.out.print("priorty: " + priority);
            // System.out.print(" node: " + expression[i]);
            // System.out.println("");

            while (!stack.isEmpty() && stack.peek().priority >= cur.priority) {
                ReturnType prev = stack.pop();
                if (!stack.isEmpty() && stack.peek().priority < cur.priority) {
                    cur.root.left = prev.root;
                } else if (!stack.isEmpty() && stack.peek().priority >= cur.priority) {
                    stack.peek().root.right = prev.root;
                } else if (stack.isEmpty() && cur.priority == Integer.MIN_VALUE) {
                    ans = prev.root;
                } else {
                    cur.root.left = prev.root;
                }
            }

            // if (cur != null && cur.root != null && cur.root.left != null) {
            //     System.out.println(cur.root.left.symbol + "," + cur.root.symbol);
            // }

            stack.push(cur);
        }
        return ans;
    }
}