772. Basic Calculator III

class Solution {
    public int calculate(String s) {
        // 1. use recursion to dealwith braces
        // 2. convert characters to num and avoid overflow
        // 3. use stack to temporary keep the number within the braches
        Queue<Character> queue = new LinkedList<>();
        for(int i=0; i<s.length(); i++){
            queue.offer(s.charAt(i));
        }
        return recursion(queue);
    }
    
    // if use resursion to check braces,
    // input should be character removable
    private int recursion(Queue<Character> queue){
        
        int num = 0;
        char sign = '+';
        Stack<Integer> stack = new Stack<>();
        
        while(!queue.isEmpty()){
            char ch = queue.poll();
            if(Character.isDigit(ch)){
                num=num*10+(ch-'0');
            }
            if(ch=='(') num=recursion(queue);
            
            if(!Character.isDigit(ch) && ch!=' ' || queue.isEmpty()){
                switch(sign){
                    case '+':
                        stack.push(num);
                        break;
                    case '-':
                        stack.push(-1*num);
                        break;
                    case '*':
                        stack.push(stack.pop()*num);
                        break;
                    case '/':
                        stack.push(stack.pop()/num);
                }
                num = 0;
                sign = ch;
            }
            if (ch == ')') break;
        }
        
        int sum = 0;
        while(!stack.isEmpty()){
            sum+=stack.pop();
        }
        return sum;
    }
}