Expression Evaluation

Expression Evaluation

1. Question

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", ")"
],

return2

2. Implementation

public class Solution {
    /**
     * @param expression: an array of strings;
     * @return: an integer
     */
    public int evaluateExpression(String[] expression) {
        // write your code here
        Stack<Integer> nums = new Stack<>();
        Stack<String> operators = new Stack<>();

        for (int i = 0; i < expression.length; i++) {
            String c = expression[i];

            if (isOperator(c)) {
                if (c.equals("(")) {
                    operators.push(c);
                }
                else if (c.equals(")")) {
                    while (!operators.isEmpty() && !operators.peek().equals("(")) {
                        nums.push(calculate(nums.pop(), nums.pop(), operators.pop()));
                    }
                    operators.pop(); // remove "("
                }
                else {
                    while (!operators.isEmpty() && hasPrecedence(c, operators.peek())) {
                        nums.push(calculate(nums.pop(), nums.pop(), operators.pop()));
                    }
                    operators.push(c);
                }
            }
            else {
                nums.push(Integer.valueOf(c));
            }
        }

        while (!operators.isEmpty()) {
            nums.push(calculate(nums.pop(), nums.pop(), operators.pop()));
        }
        return nums.isEmpty() ? 0 : nums.pop();
    }

    public boolean isOperator(String c) {
        return  c.equals("*") || c.equals("/") || c.equals("+") || c.equals("-") 
                || c.equals("(") || c.equals(")");
    }

    public int calculate(int num1, int num2, String op) {
        int value = 0;
        switch(op) {
            case "+":
                value = num1 + num2;
                break;
            case "-":
                value = num2 - num1;
                break;
            case "*":
                value = num1 * num2;
                break;
            case "/":
                value = num2 / num1;
                break;
        }
        return value;
    }

    // Check if op2 has a higher precedence
    public boolean hasPrecedence(String op1, String op2) {
        if (op2.equals("*") || op2.equals("/")) {
            return true;
        }
        else if (op2.equals("+") || op2.equals("-")) {
            if (op1.equals("*") || op1.equals("/")) {
                 return false;
            }
            else {
                return true;
            }
        }
        else {
            return false;
        }
    }
};

3. Time & Space Complexity

时间复杂度: O(n), 空间复杂度: O(n)