Expression Tree Build

Java

public class Solution {
    /*
     * @param expression: A string array
     * @return: The root of expression tree
     */
    class TreeNode {
        int priority;
        ExpressionTreeNode eNode;
        TreeNode left, right;
        TreeNode(int priority, ExpressionTreeNode eNode) {
            this.priority = priority;
            this.eNode = eNode;
        }
    }
    public ExpressionTreeNode build(String[] expression) {
        // write your code here
        Stack<TreeNode> stack = new Stack<>(); // monotone stack
        int base = 0;
        for (String e : expression) {
            if (e.equals("(")) {
                base += 3;
                continue;
            } else if (e.equals(")")) {
                base -= 3;
                continue;
            }
            int priority = getPriority(base, e);
            ExpressionTreeNode eNode = new ExpressionTreeNode(e);
            TreeNode node = new TreeNode(priority, eNode);
            while (!stack.isEmpty() && stack.peek().priority >= priority) {
                node.left = stack.pop();
            }
            if (!stack.isEmpty()) {
                stack.peek().right = node;
                stack.peek().eNode.right = node.eNode;
            }
            if (node.left != null) {
                node.eNode.left = node.left.eNode;
            }
            stack.push(node);
        }
        ExpressionTreeNode result = null;
        while (!stack.isEmpty()) {
            result = stack.pop().eNode;
        }
        return result;
    }
    private int getPriority(int base, String e) {
        if (e.equals("+") || e.equals("-")) {
            return base + 1;
        } else if (e.equals("*") || e.equals("/")) {
            return base + 2;
        }
        // number
        return Integer.MAX_VALUE;
    }
}




//the following up of the evaluation method 
public class Solution {
    
    class ExpressionTreeNode {
        public String symbol;
        public ExpressionTreeNode left, right;
        public ExpressionTreeNode(String symbol) {
            this.symbol = symbol;
            this.left = this.right = null;
        }
    }
    
    /**
     * @param expression: a list of strings
     * @return: an integer
     */
    public int evaluateExpression(String[] expression) {
        // write your code here
        if (expression == null || expression.length == 0) {
            return 0;
        }
        ExpressionTreeNode root = build(expression);
        List<String> reversedPolishNotation = new ArrayList<>();
        postOrder(reversedPolishNotation, root);
        return evalRPN(reversedPolishNotation);
    }
    
    private void postOrder(List<String> list, ExpressionTreeNode root) {
        if (root == null) {
            return;
        }
        postOrder(list, root.left);
        postOrder(list, root.right);
        list.add(root.symbol);
    }
    
    class TreeNode {
        int priority;
        ExpressionTreeNode eNode;
        TreeNode left, right;
        TreeNode(int priority, ExpressionTreeNode eNode) {
            this.priority = priority;
            this.eNode = eNode;
        }
    }
    public ExpressionTreeNode build(String[] expression) {
        // write your code here
        Stack<TreeNode> stack = new Stack<>();
        int base = 0;
        for (String e : expression) {
            if (e.equals("(")) {
                base += 3;
                continue;
            } else if (e.equals(")")) {
                base -= 3;
                continue;
            }
            int priority = getPriority(base, e);
            ExpressionTreeNode eNode = new ExpressionTreeNode(e);
            TreeNode node = new TreeNode(priority, eNode);
            while (!stack.isEmpty() && stack.peek().priority >= priority) {
                node.left = stack.pop();
            }
            if (!stack.isEmpty()) {
                stack.peek().right = node;
                stack.peek().eNode.right = node.eNode;
            }
            if (node.left != null) {
                node.eNode.left = node.left.eNode;
            }
            stack.push(node);
        }
        ExpressionTreeNode result = null;
        while (!stack.isEmpty()) {
            result = stack.pop().eNode;
        }
        return result;
    }
    private int getPriority(int base, String e) {
        if (e.equals("+") || e.equals("-")) {
            return base + 1;
        } else if (e.equals("*") || e.equals("/")) {
            return base + 2;
        }
        // number
        return Integer.MAX_VALUE;
    }
    
    public int evalRPN(List<String> tokens) {
        // write your code here
        Stack<Integer> stack = new Stack<>();
        for (String t : tokens) {
            if (t.equals("+")) {
                stack.push(stack.pop() + stack.pop());
            } else if (t.equals("-")) {
                stack.push(-stack.pop() + stack.pop());
            } else if (t.equals("*")) {
                stack.push(stack.pop() * stack.pop());
            } else if (t.equals("/")) {
                int b = stack.pop(), a = stack.pop();
                stack.push(a / b);
            } else {
                stack.push(Integer.valueOf(t));
            }
        }
        return stack.isEmpty() ? 0 : stack.pop();
    }
}