• 思路
• 最简单的计算器（好像也不简单，因为有*/）
• 224
• 772 困难计算器 可以通解224 227 和上面的题

思路

用一个栈ops存操作，用一个栈nums存数字
然后从前往后做，对遍历到的字符做分情况讨论：

• 空格 : 跳过
• ( : 直接加入 ops 中，等待与之匹配的 )
• ) : 使用现有的 nums 和 ops 进行计算，直到遇到左边最近的一个左括号为止，计算结果放到 nums
• 数字 : 从当前位置开始继续往后取，将整一个连续数字整体取出，加入 nums
• +/- : 需要将操作放入 ops 中。在放入之前先把栈内可以算的都算掉，使用现有的 nums 和 ops 进行计算，直到没有操作或者遇到左括号，计算结果放到 nums

最简单的计算器（好像也不简单，因为有*/）

https://leetcode.cn/problems/calculator-lcci/description/

224

772 困难计算器 可以通解224 227 和上面的题

在上述的要求中，出现了四则运算的比较，如何比较四则运算的优先顺序呢，简单来说，我们用一个map来映射运算符的优先级：
如：
unordered_map<char, int> level = {{'-', 1}, {'+', 1}, {'*', 2}, {'/', 2}};
当运行到有加减乘除的区域，就计算优先级了

• 当读取到：5+5*2
  读取到*时，*的优先级为2，大于+的1优先级，那么这里就选择直接入栈，等到其他的情况再进行运算
• 当读取到: 5+5*2/或是5+5*2)
  这里就发现/的优先级等于*的优先级，可以直接把*运算了，再读取+的时候发现又小于/的优先级，再次停止运算

class Solution {
public:
    unordered_map<char,int> level={
        {'-', 1},
        {'+', 1},
        {'*', 2},
        {'/', 2}
    };

    int calculate(string s) {
         // 存放所有的数字
        stack<int> nums;
        // 为了防止第一个数为负数，先往 nums 加个 0
        nums.push(0);
        // 将所有的空格去掉
        removeSpace(s);
        //去掉所有形如(- (+的玩意
        removeSpecial(s);
        // 存放所有的操作，包括 +/-
        stack<char> ops;
        int n = s.size();
        for(int i = 0; i < n; i++) {
            char c = s[i];
            if(c == '(')
                ops.push(c);
            else if(c == ')') {
                // 计算到最近一个左括号为止
                while(!ops.empty()) {
                    char op = ops.top();
                    if(op != '(')
                        calc(nums, ops);
                    else {
                        ops.pop();
                        break;
                    }
                }
            }
            else {
                if(isdigit(c)) {
                    int cur_num = 0;
                    int j = i;
                    // 将从 i 位置开始后面的连续数字整体取出，加入 nums
                    while(j <n && isdigit(s[j]))
                    {
                        cur_num = cur_num*10 + (s[j] - '0');
                        j++;
                    }
                    // 注意上面的计算一定要有括号，否则有可能会溢出
                    nums.push(cur_num);
                    i = j-1;
                }
                else {
                    // 有一个新操作要入栈时，先把栈内可以算的都算了
                    //并且比较其中运算符的优先级，如果新读取到的运算符优先级没有栈内的高/等于栈内运算符优先级，那么可以直接进行运算
                    while(!ops.empty() && ops.top() != '('&&level[ops.top()]>=level[c])
                        calc(nums, ops);
                    ops.push(c);
                }
            }
        }
        while(!ops.empty())
            calc(nums, ops);
        return nums.top();

    }
    void removeSpace(string & s)
    {
        int pos=s.find(' ');
        while(pos!=-1)
        {
            s.erase(pos,1);
            pos=s.find(' ');
        }
    }
    void removeSpecial(string & s)
    {
        int pos=s.find('(');
        while(pos!=-1&&pos+1<s.length())
        {
            if(s[pos+1]=='+')
            {
                s.replace(pos,2,"(0+");
            }
            else if(s[pos+1]=='-')
            {
                s.replace(pos,2,"(0-");
            }
            pos=s.find('(',pos+1);
        }
    }
    void calc(stack<int>& nums,stack<char>& ops)
    {
        if(nums.size()<2||ops.empty())
        {
            return;
        }
        int b=nums.top();nums.pop();
        int a=nums.top();nums.pop();
        char op=ops.top();ops.pop();
        switch(op)
        {
            case '+':
                nums.push(a+b);
                break;
            case '-':
                nums.push(a-b);
                break;
            case '*':
                nums.push(a*b);
                break;
            case '/':
                nums.push(a/b);
                break;
            default:
                break;
        }
        
    }
};