# 0772. Basic Calculator III
###### tags: `Leetcode` `FaceBook` `Calculator` `Hard`
Link: https://leetcode.com/problems/basic-calculator-iii/
## 思路
参考的链接在[这里](https://leetcode-cn.com/problems/basic-calculator-ii/solution/shi-yong-shuang-zhan-jie-jue-jiu-ji-biao-c65k/)
计算器终极解法
双栈
一个栈装operator，一个栈装数字
具体内容写在注解里面了
## Code

class Solution {
    Map<Character,Integer> map = new HashMap<>(){{
        put('-',1);
        put('+',1);
        put('*',2);
        put('/',2);
    }};
    public int calculate(String s) {
        char[] charArray = s.toCharArray();
        Stack<Integer> nums = new Stack<>();
        //由于第一个出现的数可能是负数，所以为了减少边界判断，先往nums里面添加一个0
        nums.add(0);
        Stack<Character> ops = new Stack<>();
        int idx = 0;
        while(idx<s.length()){
            //遇到(，直接加入ops栈，等待与之匹配的)
            if(charArray[idx]=='('){
                ops.add('(');
            }    
            //使用现有的nums和ops进行计算，直到遇到最近的（为止，最后把计算结果放到nums里面
            else if(charArray[idx]==')'){
                while(ops.peek()!='('){
                    compute(nums, ops);
                }
                ops.pop();
            }
            //遇到数字，全部取出来
            else if(Character.isDigit(charArray[idx])){
                int num = 0;
                while(idx<charArray.length && Character.isDigit(charArray[idx])){
                    num = num*10+(charArray[idx]-'0');
                    idx++;
                }
                nums.add(num);
                idx--;
            }
            //遇到operator
            else{
                //如果现在这个operator前面是(或者+或者-，就说明有可能出现了(-12或（+12或*-3这种情况，这时候先加一个0，可以把表达式变成(0-12或者(0+12或者*(0-3，省略了边界情况处理
                if(idx!=0 && (charArray[idx-1]=='(' || charArray[idx-1]=='+' || charArray[idx-1]=='-')){
                    nums.add(0);
                }
                //有一个新的operator入栈的时候，先把栈内可以算的都算了
                //只有满足 栈内运算符比当前运算符优先级高/同等的时候才可以运算
                while(!ops.isEmpty() && ops.peek()!='('){
                    char prev = ops.peek();
                    if(map.get(prev)>=map.get(charArray[idx])){
                        compute(nums, ops);
                    }
                    else{
                        break;
                    }
                }
                ops.add(charArray[idx]);
            }
            idx++;
        }
        //把剩余的计算完
        while(!ops.isEmpty()) compute(nums, ops);
        return nums.peek();
    }
    public void compute(Stack<Integer> num, Stack<Character>ops){
        int b = num.pop();
        int a = num.pop();
        char c = ops.pop();
        if(c == '+') num.push(a+b);
        if(c == '-') num.push(a-b);
        if(c == '*') num.push(a*b);
        if(c == '/') num.push(a/b);
    }
}