BasicCalculatorIII.java

 public int calculate(String s) {
        if (s == null || s.length() == 0) {
            throw new IllegalArgumentException("invalid input");
        }
        
        s = s.trim();
        int i = 0;

        Stack<Long> operands = new Stack<>();
        Stack<Character> operators = new Stack<>();
        StringBuilder number = new StringBuilder(); // deal with non single digit numbers

        while (i < s.length()) {
            char c = s.charAt(i);

            if (c == ' ') {
                i++;
                continue;
            }

            if (Character.isDigit(c)) {
                number.append(c);
            } else if (this.isValidOperator(c)) {
                if (number.length() != 0) {
                    operands.push(Long.parseLong(number.toString()));
                    number = new StringBuilder();
                }

                // Basically based on different priority of operators
                if (operators.isEmpty()) {
                    // it says it only contains non-negative integer, but now we have "-1 + 2", "-(2+3)*4"
                    // this is to deal with the starting negative case
                    if (c == '-' && i == 0) {
                        operands.push(-1L);
                        operators.push('*');
                    } else {
                        operators.push(c);
                    }
                } else if (!operators.isEmpty() && (c == '*' || c == '/') && (operators.peek() == '+' || operators.peek() == '-')) {
                    // do nothing, keep pushing because */ has higher priority than +-
                    operators.push(c);
                } else if (!operators.isEmpty() && (c == '+' || c == '-') && (operators.peek() == '*' || operators.peek() == '/')) {
                    // calculate all previous expressions till hit the left bracket
                    while (!operators.isEmpty() && operators.peek() != '(') {
                        operands.push(this.calculateValue(operands, operators.pop()));
                    }

                    operators.push(c);
                } else if (c == '(') {
                    operators.push(c);
                    // this is to deal with 1 * (-7+2) case
                    if (this.isNegativeNumberFollowingLeftBracket(s, i + 1)) {
                        operands.push(-1L);
                        operators.push('*');
                        while (i < s.length()) {
                            if (s.charAt(i) == '-') {
                                // i++;  // skip this '-', later we i++ on line 129
                                break;
                            }
                            i++;
                        }
                    }
                } else if (c == ')') {
                    if (number.length() != 0) {
                        operands.push(Long.parseLong(number.toString()));
                        number = new StringBuilder();
                    }

                    while (!operators.isEmpty() && operators.peek() != '(') {
                        char op = operators.pop();
                        operands.push(this.calculateValue(operands, op));

                    }
                    operators.pop(); // pop out the left (

                } else {
                    // for normal +- with previous +- || */ with previous */ case just calculate 1 step ahead
                    // but because 15 / 3 / 5 should be 1, but it won't work 3 / 5 = 0, so we have to calculate
                    // every time we can calculate and get result
                    if (!operators.isEmpty() && operators.peek() != '(') {
                        operands.push(this.calculateValue(operands, operators.pop()));
                    }
                    operators.push(c);
                }
            }
            i++;
        }

        if (number.length() != 0) {
            operands.push(Long.parseLong(number.toString()));
        }
        // for "3+2*2" case that's why we need a while loop
        while (!operators.isEmpty()) {
            operands.push(this.calculateValue(operands, operators.pop()));
        }

        return (int)operands.pop().longValue();
    }

    // given the current index(this would normally be the index after the '(', find out if there is
    // a negative integer following the '('
    private boolean isNegativeNumberFollowingLeftBracket(String s, int index) {
        while (index < s.length()) {
            char c = s.charAt(index);
            if (c == ' ') {
                index++;
                continue;
            }
            if (c == '-') {
                return this.isDigitFollowing(s, index + 1);
            } else {
                return false;
            }
        }
        return false;
    }

    // given the current index, find out if it's a digit following it.
    private boolean isDigitFollowing(String s, int index) {
        while (index < s.length()) {
            char c = s.charAt(index);
            if (c == ' ') {
                index++;
                continue;
            }
            if (Character.isDigit(c)) {
                return true;
            }
            return false;
        }
        return false;
    }


    private boolean isValidOperator(char op) {
        if (op == '+' || op == '-' || op == '*' || op == '/' || op == '(' || op == ')') {
            return true;
        }
        return false;
    }

    private long calculateValue(Stack<Long> operands, char op) {
        long o2 = operands.pop();
        long o1 = operands.pop();

        if (op == '+') {
            return o1 + o2;
        } else if (op == '-') {
            return o1 - o2;
        } else if (op == '*') {
            return o1 * o2;
        } else if (op == '/') {
            return o1 / o2;
        } else {
            throw new IllegalArgumentException("invalid op! " + op);
        }
    }