Expression Evaluation

Given an expression string array, return the final result of this expression. The expression contains only integer, +, -, *, /, (, ).

Example:

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

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

return.

Solution:

This is purely based on Stack. Details to check following links

• Infix to Postfix Conversion

• Postfix Evaluation

Code:

public class Solution {
    /**
     * @param expression: an array of strings;
     * @return: an integer
     */
    public int evaluateExpression(String[] expression) {
        if (expression == null || expression.length == 0) {
            return 0;
        }
        Stack<String> postfix = infixToPostfix(expression);
        return evaluation(postfix);
    }

    private int evaluation(Stack<String> postfix) {
        Stack<String> temp = new Stack<>();
        while (postfix.size() > 1) {
            while (isNum(postfix.peek())) {
                temp.push(postfix.pop());
            }
            int res = 0;
            int right = Integer.parseInt(temp.pop());
            int left = Integer.parseInt(temp.pop());
            char c = postfix.pop().charAt(0);
            switch (c) {
                case '*': res = left * right; break;
                case '/': res = left / right; break;
                case '+': res = left + right; break;
                case '-': res = left - right; break;
                default : res = 0;
            }
            postfix.push(Integer.toString(res));
            while (!temp.empty()) {
                postfix.push(temp.pop());
            }
        }
        int res = 0;
        if (postfix.size() == 1) {
            res = Integer.parseInt(postfix.pop());
        }
        return res;
    }

    private Stack<String> infixToPostfix(String[] strs) {
        Stack<String> postfix = new Stack<>();
        Stack<String> opstack = new Stack<>();
        for (String s : strs) {
            if ('0' <= s.charAt(0) && s.charAt(0) <= '9') {
                postfix.push(s);
            } else {
                if (!opstack.empty()) {
                    if (s.equals("(")) {
                        opstack.push(s);
                    } else if (s.equals(")")) {
                        while (!opstack.empty() && !opstack.peek().equals("(")) {
                            postfix.push(opstack.pop());
                        }
                        if (opstack.peek().equals("(")) {
                            opstack.pop();
                        }
                    } else {
                        while (!opstack.empty() && order(opstack.peek()) >= order(s)) {
                            postfix.push(opstack.pop());
                        }
                        opstack.push(s);
                    }
                } else {
                    opstack.push(s);
                }
            }
        }
        while (!opstack.empty()) {
            postfix.push(opstack.pop());
        }
        while (!postfix.empty()) {
            opstack.push(postfix.pop());
        }
        return opstack;
    }

    private boolean isNum(String s) {
        char c = s.charAt(0);
        if ('0' <= c && c <= '9') {
            return true;
        }
        return false;
    }

    private int order(String s) {
        if (s.equals("*") || s.equals("/")) {
            return 2;
        } else if (s.equals("+") || s.equals("-")) {
            return 1;
        }
        return 0;
    }
}