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

Anaylysis:

The build process is similar like converting the expression into Reverse Polish Notation (Postfix Notation). Put Operator and Operand into two stack and use operator priority to guide when to build the treeNode.

Solution:

 public class ExpressionTreeNode {
 *     public String symbol;
 *     public ExpressionTreeNode left, right;
 *     public ExpressionTreeNode(String symbol) {
 *         this.symbol = symbol;
 *         this.left = this.right = null;
 *     }
 * }

 public ExpressionTreeNode build(String[] expression) {
        if(expression==null||expression.length==0) return null;
        if(expression.length==1) return new ExpressionTreeNode(expression[0]);
        // write your code here
        Map<String,Integer> level=new HashMap<>();
        level.put("-",0);
        level.put("+",0);
        level.put("*",1);
        level.put("/",1);
        LinkedList<ExpressionTreeNode> node=new LinkedList<>();
        LinkedList<String> operator=new LinkedList<>();
        for(String a:expression){
            if(level.containsKey(a)){
                while(!operator.isEmpty()&&level.containsKey(operator.peek())&&level.get(a)<=level.get(operator.peek())){
                ExpressionTreeNode root=new ExpressionTreeNode(operator.pop());
                root.right=node.pop();
                root.left=node.pop();
                node.push(root);
                }
                operator.push(a);
            }else if(a.equals("(")){
                operator.push(a);
            }else if(a.equals(")")){
                while(!operator.peek().equals("(")){
                    ExpressionTreeNode root=new ExpressionTreeNode(operator.pop());
                root.right=node.pop();
                root.left=node.pop();
                node.push(root);
                }
                operator.pop();
            }else node.push(new ExpressionTreeNode(a));
        }
        while(!operator.isEmpty()){
            ExpressionTreeNode root=new ExpressionTreeNode(operator.pop());
            root.right=node.pop();
            root.left=node.pop();
            node.push(root);
        }
        return node.isEmpty()?null:node.pop();
    }

Convert Expression to RPN

Example:

 "(","3","+","6","*","5",")","*","4","-","6","/","18"
 converted to
 "3","6","5","*","+","4","*","6","18","/","-"

 public ArrayList<String> convertToRPN(String[] expression) {
        // write your code here
        HashMap<String,Integer> level=new HashMap<String,Integer>();
        level.put("+",1);
        level.put("-",1);
        level.put("*",2);
        level.put("/",2);
        ArrayList<String> RPN=new ArrayList<>();
        LinkedList<String> operator=new LinkedList<>();
        for(String a : expression){
            if(a.equals("(")) {operator.push(a); continue;}
            if(a.equals(")")) {
                while(!operator.peek().equals("(")) RPN.add(operator.pop());
                operator.pop();
                continue;
            }
            if(level.containsKey(a)){
                int levelOfA=level.get(a);
                while(!operator.isEmpty() && !operator.peek().equals("(") && 
                        level.get(operator.peek())>=levelOfA)
                    RPN.add(operator.pop());
                operator.push(a);
            }else RPN.add(a);
        }
        while(!operator.isEmpty()) RPN.add(operator.pop());
        return RPN;
    }