Descriptoin

Given an expression string array, return the final result of this expression

Notice

The expression contains onlyinteger,+,-,*,/,(,).

Example

For the expression2*6-(23+7)/(1+2),
input is

[
  "2", "*", "6", "-", "(",
  "23", "+", "7", ")", "/",
  (", "1", "+", "2", ")"
],

return 2

Solution

Expression Tree Build + BFS

public class Solution {
    /*
     * @param expression: a list of strings
     * @return: an integer
     */
    public class TreeNode {
        String symbol;
        int weight;
        TreeNode left;
        TreeNode right;
        public TreeNode(String s, int w) {
            this.symbol = s;
            this.weight = w;
            this.left = null;
            this.right = null;
        }
    }

    public int evaluateExpression(String[] expression) {
        // write your code here
        if (expression == null || expression.length == 0) {
            return 0;
        }

        TreeNode root = buildExpressionTree(expression);
        return bfs(root);
    }

    private int bfs(TreeNode root) {
        if (root == null) {
            return 0;
        }

        if (root.left == null && root.right == null) {
            return Integer.parseInt(root.symbol);
        }

        int left = bfs(root.left);
        int right = bfs(root.right);

        if (root.symbol.equals("+")) {
            return left + right;
        }

        if (root.symbol.equals("-")) {
            return left - right;
        }

        if (root.symbol.equals("*")) {
            return left * right;
        }

        if (root.symbol.equals("/")) {
            return left / right;
        }

        return 0;
    }

    private TreeNode buildExpressionTree(String[] expression) {
        if (expression == null || expression.length == 0) {
            return null;
        }

        Stack<TreeNode> stack = new Stack<TreeNode>();
        int base = 0;
        for (int i = 0; i <= expression.length; i++) {
            String symbol = i == expression.length ? "" : expression[i];
            if (symbol.equals("(")) {
                base += 10;
                continue;
            } 

            if (symbol.equals(")")) {
                base -= 10;
                continue;
            }

            int weight = i == expression.length ? Integer.MIN_VALUE : getWeight(symbol, base);
            TreeNode cur = new TreeNode(symbol, weight);
            TreeNode pre = null;
            while (!stack.isEmpty() && stack.peek().weight >= weight) {
                TreeNode ans = stack.pop();
                ans.right = pre;
                pre = ans;
            }
            cur.left = pre;
            stack.push(cur);
        }

        return stack.pop().left;
    }

    private int getWeight(String s, int base) {
        if (s.equals("*") || s.equals("/")) {
            return base + 2;
        }

        if (s.equals("+") || s.equals("-")) {
            return base + 1;
        }

        return Integer.MAX_VALUE;
    }
}