772. Basic Calculator III

Question

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

The expression string contains only non-negative integers, 4 operators , open ( and closing parentheses ) and empty spaces . The integer division should truncate toward zero.

You may assume that the given expression is always valid. All intermediate results will be in the range of [-2147483648, 2147483647].

Some examples:

"1 + 1" = 2
" 6-4 / 2 " = 4
"2*(5+5*2)/3+(6/2+8)" = 21
"(2+6* 3+5- (3*14/7+2)*5)+3"=-12

Solutions:

Method 1: Recursion + stack

class Solution {
    private int index = 0;
    private char[] arr;
    public int calculate(String s) {
        this.arr = s.toCharArray();
        return parse();
    }
    private int parse(){
        char operator = '+';
        int sum = 0;
        Stack<Integer> stack = new Stack<>();
        while(index < arr.length){
            char c = arr[index];
            if(c == '('){
                index++;
                addToStack(stack, operator, parse());
            }else if(Character.isDigit(c)){
                int temp = c - '0';
                index++;
                while(index < arr.length && Character.isDigit(arr[index])){
                    temp = temp * 10 + arr[index++] - '0';
                }
                index--;
                addToStack(stack, operator, temp);
            }else if(c == '+' || c == '-' || c == '*' || c == '/'){
                System.out.println(c);
                operator = c;
            }else if(c == ')'){
                while(!stack.isEmpty()) sum += stack.pop();
                return sum;
            }
            index++;
        }
        while(!stack.isEmpty()) sum += stack.pop();
        return sum;
    }
    private void addToStack(Stack<Integer> stack, char operator, int val){
        if(operator == '+') stack.push(val);
        else if(operator == '-') stack.push(-val);
        else if(operator == '*') stack.push(val * stack.pop());
        else if(operator == '/'){
            stack.push(stack.pop() / val);
        }
    }
}