中缀表达式的延迟处理方式

今儿又学了一招：对于中缀表达式的延迟处理。一直以来对于计算中缀表达式这种需要使用栈的题目都不是很熟悉，也没有特别研究一下。今天刚好碰到，就来研究一下

• 先给出 题目 和代码模板

class Solution {
public:
    int calculate(string s) {

        stack nums;
        char c = '+';
        long long num = 0, n = s.size(), a;
        // 这里应该允许 i = n, 从而保证流中最后一个数字的压栈 
        // string的最后一个字符同样以''结束, 即 s[n] == ''
        for(int i = 0; i <= n; ++i){    
            if(s[i] == ' ')
                continue;
            else if(isdigit(s[i]))
                num = num * 10 + s[i] - '0';
            else{
                switch(c){
                    case '+':
                        nums.push(num);
                        break;
                    case '-':
                        nums.push(-num);
                        break;
                    case '*':
                        a = nums.top();
                        nums.pop();
                        nums.push(a*num);
                        break;
                    default:
                        a = nums.top();
                        nums.pop();
                        nums.push(a/num);
                        break;
                }
                c = s[i];
                num = 0;
            }
        }
        int ans = 0;
        while(nums.size()){
            ans += nums.top();
            nums.pop();
        }
        return ans;
    }
};

• 这道题其实不需要使用双栈，因为表达式中没有涉及’(‘和’)’，所以只需要单栈记录数值即可。同时，这道题在计算过程中做到了延迟处理：当碰到一个新的运算符时，才来判断前一个运算符 c c c，并将中间的数字通过 c c c 的类型来压入栈中。这种处理方式把表达式流成功转换为分开的数字，最后弹栈即可完成运算。