Lintcode 367. 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.

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

Code (Java)

/**
 * 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 ExpressionTreeNode build(String[] expression) {
        if (expression == null || expression.length == 0) {
            return null;
        }
        
        Stack<String> opStack = new Stack<>();
        Stack<ExpressionTreeNode> nodeStack = new Stack<>();
        
        int i = 0;
        for (String s : expression) {
            if (isNumeric(s)) {
                ExpressionTreeNode node = new ExpressionTreeNode(s);
                nodeStack.push(node);
            } else if (opStack.isEmpty() || s.equals("(")) {
                opStack.push(s);
            } else if (s.equals("+") || s.equals("-")) {
                if (opStack.peek().equals("(")) {
                    opStack.push(s);
                } else {
                    compute(opStack, nodeStack);
                    opStack.push(s);
                }
            } else if (s.equals("*") || s.equals("/")) {
                String top = opStack.peek();
                if (top.equals("(")) {
                    opStack.push(s);
                } else if (top.equals("*") || top.equals("/")) {
                    compute(opStack, nodeStack);
                    opStack.push(s);
                } else {
                    opStack.push(s);
                }
            } else {
                while (!opStack.isEmpty() && !opStack.peek().equals("(")) {
                    compute(opStack, nodeStack);
                }
                opStack.pop(); // pop out the '('
            }
        }
        
        while (!opStack.isEmpty()) {
            compute(opStack, nodeStack);
        }
        
        return nodeStack.isEmpty() ? null : nodeStack.pop();
    }
    
    private void compute(Stack<String> opStack, Stack<ExpressionTreeNode> nodeStack) {
        ExpressionTreeNode node2 = nodeStack.pop();
        ExpressionTreeNode node1 = nodeStack.pop();
        
        String op = opStack.pop();
        
        ExpressionTreeNode root = new ExpressionTreeNode(op);
        root.left = node1;
        root.right = node2;
        
        nodeStack.push(root);
    }
    
    private boolean isNumeric(String s) {
        for (char c : s.toCharArray()) {
            if (!Character.isDigit(c)) {
                return false;
            }
        }
        
        return true;
    }
}