Basic Calculator II

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

You may assume that the given expression is always valid.

Some examples:

"3+2*2" = 7 " 3/2 " = 1 " 3+5 / 2 " = 5

Note: Do not use the eval built-in library function.

Credits:Special thanks to @ts for adding this problem and creating all test cases.

Solution

public class Solution {
     public int calculate(String s) {
        if (s == null || s.length() <= 0) return 0;

        Stack<Integer> stack1 = new Stack<>();
        Stack<Character> stack2 = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char currentChar = s.charAt(i);
            if (isOperand(currentChar)) {
                if (currentChar == ')') {
                    while (stack2.peek() != '(') {
                        Character operand = stack2.pop();
                        stack1.push(operate(operand, stack1.pop(), stack1.pop()));
                    }

                    stack2.pop();
                } else if (currentChar == '+' || currentChar == '-') {
                    while (!stack2.isEmpty()) {
                        if (stack2.peek() == '(') {
                            break;
                        }

                        stack1.push(operate(stack2.pop(), stack1.pop(), stack1.pop()));
                    }

                    stack2.push(currentChar);
                } else {
                    stack2.push(currentChar);
                }

            } else if (Character.isDigit(currentChar)) {
                int endIndex = i + 1;
                while (endIndex < s.length() && Character.isDigit(s.charAt(endIndex))) {
                    endIndex++;
                }

                Integer currentInteger = Integer.valueOf(s.substring(i, endIndex));
                if (!stack2.isEmpty() && (stack2.peek() == '*' || stack2.peek() == '/')) {
                    stack1.push(operate(stack2.pop(), stack1.pop(), currentInteger));
                } else {
                    stack1.push(currentInteger);
                }
                i = endIndex - 1;
            }
        }

        while (!stack2.isEmpty()) {
            stack1.push(operate(stack2.pop(), stack1.pop(), stack1.pop()));
        }

        return stack1.pop();
    }

    private int operate(Character c, int a, int b) {
        switch (c) {
            case '+':
                return a + b;
            case '-':
                return b - a;
            case '*':
                return a * b;
            case '/':
                return  a / b;
        }

        return -1;
    }

    private boolean isOperand(char c) {
        StringBuffer sb = new StringBuffer();
        sb.append(c);
        return "()+-/*".contains(sb.toString());
    }
}