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

See wiki:
Expression Tree

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

class TreeNode {
    public int val;
    public String s;
    public ExpressionTreeNode root; 
    public TreeNode(int val, String ss) {
        this.val = val;
        this.root = new ExpressionTreeNode(ss);
    }
}

public class Solution {
    int get(String a, Integer base) {
        if (a.equals("+") || a.equals("-"))
            return 1 + base;
        if (a.equals("*") || a.equals("/"))
            return 2 + base;

        return Integer.MAX_VALUE;
    }
    public ExpressionTreeNode build(String[] expression) {
        // write your code here
        Stack stack = new Stack();
        TreeNode root = null;
        int val = 0;
        Integer base = 0;
        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 = get(expression[i], base);
            }
            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 nodeNow = stack.pop();
                    if (stack.isEmpty()) {
                        right.root.left = nodeNow.root;
                    } else {
                        TreeNode left = stack.peek();
                        if (left.val < right.val) {
                            right.root.left = nodeNow.root;
                        } else {
                            left.root.right = nodeNow.root;
                        }
                    }
                } else {
                    break;
                }
            }
            stack.push(right);
        }        
        return stack.peek().root.left;
    }
};

class Solution {
public:
    /**
     * @param expression: A string array
     * @return: The root of expression tree
     */
    int getLevel(string opt) {
        if (opt == "(")
            return 0;
        if (opt == "+" || opt == "-")
            return 1;
        if (opt == "*" || opt == "/")
            return 2;
        return 3;
    }
    bool isOperator(string c) {
        return (c == "+" || c == "-" || c == "*" || c == "/");
    }
    
    vector convertToRPN(vector &expression) {
        stack st;
        vector RPN;
        int len = expression.size();
        for (int i = 0; i < len; ++i) {
            string c = expression[i];
            if (c == "(")
                st.push(c);
            else if (c == ")") {
                while (st.top() != "(") {
                    RPN.push_back(st.top());
                    st.pop();
                }
                st.pop();
            } else {
                if (!isOperator(c))
                    st.push(c);
                else {
                    while (!st.empty() && getLevel(st.top()) >= getLevel(c)) {
                            RPN.push_back(st.top());
                            st.pop();
                    }
                    st.push(c);
                }
            }
        }
        while (! st.empty()) {
            RPN.push_back(st.top());
            st.pop();
        }
        return RPN;
    }
    
    ExpressionTreeNode* build(vector &expression) {
        // write your code here
        vector RPN = convertToRPN(expression);
        int len = RPN.size();
        stack nodeStack;
        for (int i = 0; i < len; ++i) {
            string s = RPN[i];
            ExpressionTreeNode *pNode = new ExpressionTreeNode(s);
                if (s == "+" || s == "-" || s == "*" || s == "/") {
                    ExpressionTreeNode *pRight = nodeStack.top();
                    nodeStack.pop();
                    ExpressionTreeNode *pLeft = nodeStack.top();
                    nodeStack.pop();

                    pNode->right = pRight;
                    pNode->left = pLeft;
                    nodeStack.push(pNode);
            } else
                nodeStack.push(pNode);
        }       
        if (nodeStack.empty())
            return NULL;
        else
            return nodeStack.top(); 
    }
};

public class Solution {
    public boolean isOperator(String s) {
        return s == "+" || s == "-" || s == "*" || s == "/";
    }
    public int getLevel(String s) {
        if (s == "(") return 0;
        if (s == "+" || s == "-") return 1;
        if (s == "*" || s == "/") return 2;
        return 3;
    }
    public ArrayList convert(String[] expression) {
        Stack stack = new Stack<>();
        ArrayList deq = new ArrayList<>();
        int len = expression.length;
        for (int i = 0; i < len; ++i) {
            String s = expression[i];
            if (s == "(") stack.push(s);
            else if (s == ")") {
                while (stack.peek() != "(") {
                    deq.add(stack.peek());
                    stack.pop();
                }
                stack.pop();//delete "("
            }
            else {
                if (!isOperator(s)) {
                    stack.push(s);
                }
                else {
                    while (!stack.isEmpty() && getLevel(stack.peek()) >= getLevel(s)) {
                        deq.add(stack.peek());
                        stack.pop();
                    }
                    stack.push(s);
                }
            }
        }
        while (!stack.isEmpty()) {
            deq.add(stack.peek());
            stack.pop();
        }
        return deq;
    }
    public ExpressionTreeNode build(String[] expression) {
        ArrayList deq = convert(expression);
        System.out.println(deq);
        int len = deq.size();
        Stack stack = new Stack<>();
        for (int i = 0; i < len; ++i) {
            String s = deq.get(i);
            ExpressionTreeNode node = new ExpressionTreeNode(s);
            if (s == "+" || s == "-" || s == "*" || s == "/") {
                ExpressionTreeNode nodeRight = stack.peek();
                stack.pop();
                ExpressionTreeNode nodeLeft = stack.peek();
                stack.pop();
                node.right = nodeRight;
                node.left = nodeLeft;
                stack.push(node);
            }
            else stack.push(node);
        }
        if (stack.isEmpty()) return null;
        else return stack.peek();
    }
}

import java.util.*;

public class Solution {
    public ExpressionTreeNode build(String[] expression) {
        Stack op   = new Stack();
        Stack data = new Stack();
        for(int i=0;i="0")){
                //System.out.println("get op "+ tmp);
                switch(firstc){
                    case "(":
                        ExpressionTreeNode node = new ExpressionTreeNode(tmp);
                        op.push(node);
                        break;
                    case "+":
                    case "-":
                        while(!op.isEmpty()&&op.peek().symbol.charAt(0)!="("){
                            ExpressionTreeNode opnode = op.pop();
                            ExpressionTreeNode data1 = data.pop();
                            ExpressionTreeNode data2 = data.pop();
                            opnode.left = data2;
                            opnode.right = data1;
                            data.push(opnode);
                        }
                        ExpressionTreeNode node2 = new ExpressionTreeNode(tmp);
                        op.push(node2);
                        break;
                    case "*":
                    case "/":
                        while(!op.isEmpty()&&(op.peek().symbol.charAt(0)=="*"||op.peek().symbol.charAt(0)=="/")){
                            ExpressionTreeNode opnode = op.pop();
                            ExpressionTreeNode data1 = data.pop();
                            ExpressionTreeNode data2 = data.pop();
                            opnode.left = data2;
                            opnode.right = data1;
                            data.push(opnode);
                        }
                        ExpressionTreeNode node3 = new ExpressionTreeNode(tmp);
                        op.push(node3);
                        break;
                    case ")":
                        while(op.peek().symbol.charAt(0)!="("){
                            ExpressionTreeNode opnode = op.pop();
                            ExpressionTreeNode data1 = data.pop();
                            ExpressionTreeNode data2 = data.pop();
                            opnode.left = data2;
                            opnode.right = data1;
                            data.push(opnode);
                        }
                        op.pop();
                }
            }else{
                //System.out.println("add data "+tmp);
                ExpressionTreeNode data1 = new ExpressionTreeNode(tmp);
                data.push(data1);
            }
        }
        while(!op.isEmpty()){
            ExpressionTreeNode opnode = op.pop();
            ExpressionTreeNode data1 = data.pop();
            ExpressionTreeNode data2 = data.pop();
            opnode.left = data2;
            opnode.right = data1;
            data.push(opnode);
        }
        if(data.isEmpty()) return null;
        return data.pop();
    }
}