224. Basic Calculator

Link

Solution

概念上也是透過兩個stack去分別記錄運算元跟運算子。 一開始都要給予初始值去幫助計算現在的運算子。 要記得 1. skip 空白 2. num處理完可能index會Out of range的問題 3. 運算子的順序要正確，否則在減法會出問題

 public int calculate(String s) {
        Stack<Character> ops = new Stack<>();
        Stack<Integer> nums = new Stack<>();
        nums.push(0);
        ops.push('+');
        for(int i = 0; i < s.length(); i++){
            if(Character.isDigit(s.charAt(i))){
                int start = i;
                while(i < s.length() && Character.isDigit(s.charAt(i))){
                    i++;
                }
                int num = Integer.parseInt(s.substring(start, i));
                char op = ops.pop();
                int ret = op == '+' ? nums.pop() + num : nums.pop() - num ;
                nums.push(ret);
                if(i == s.length()) break;
            }
            
            if(s.charAt(i) == '('){
                nums.push(0);
                ops.push('+');
            }
            else if(s.charAt(i) == ')'){
                //process all ops and nums before '('
                //output result into nums
                char op = ops.pop();
                nums.push(op == '+' ? nums.pop() + nums.pop() : 0 - (nums.pop() - nums.pop()) );
            }
            else if(s.charAt(i) == ' '){
                continue;
            }
            else{ //ops
                ops.push(s.charAt(i));
            }
        }
        return nums.pop();
    }