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

Notice

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

Have you met this question in a real interview?

Yes

Example

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

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

return2

建一棵expression tree然后分治法求解

class TreeNode {
    int val;
    String symbol;
    TreeNode left, right;
    public TreeNode (int val, String symbol) {
        this.val = val;
        this.symbol = symbol;
        this.left = this.right = null;
    }
}
public class Solution {
    /*
     * @param expression: a list of strings
     * @return: an integer
     */
    private int ADD_SUB = 1;
    private int MUL_DIV = 2;
    public int evaluateExpression(String[] expression) {
        // write your code here
        int ans = 0;
        if (expression == null || expression.length == 0) {
            return ans;
        }

        Stack<TreeNode> stack = new Stack<TreeNode>();
        int base = 1;
        TreeNode root = null;
        for (int i = 0; i <= expression.length; i++) {
            int val = base;
            TreeNode cur = null;
            if (i == expression.length) {
                val = Integer.MIN_VALUE;
                cur = new TreeNode(val, "");
            } else {
                if (expression[i].equals("*") || expression[i].equals("/")) {
                    val += MUL_DIV;
                } else if (expression[i].equals("+") || expression[i].equals("-")) {
                    val += ADD_SUB;
                } else if (expression[i].equals("(")) {
                    base *= 10;
                    continue;
                } else if (expression[i].equals(")")) {
                    base /= 10;
                    continue;
                } else {
                    val = Integer.MAX_VALUE;
                }
                cur = new TreeNode(val, expression[i]);
            }

            while (!stack.isEmpty() && stack.peek().val >= cur.val) {
                TreeNode prev = stack.pop();
                if (stack.isEmpty()) {
                    if (cur.val == Integer.MIN_VALUE) {
                        root = prev;
                    } else {
                        cur.left = prev;
                    }
                } else {
                    if (stack.peek().val < cur.val) {
                        cur.left = prev;
                    } else {
                        stack.peek().right = prev;
                    }
                }
            }
            stack.push(cur);
        }

        if (root == null) {
            return 0;
        }
        return divideConquer(root);
    }

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

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

        if (root.symbol.equals("+")) {
            return left + right;
        } else if (root.symbol.equals("-")) {
            return left - right;
        } else if (root.symbol.equals("*")) {
            return left * right;
        } else {
            return left / right;
        }

    }
}