【算法】字符串之227.基本计算器 -- 双栈的变形

目录

1、题目链接

2、分析

1、确定使用的数据结构

2、处理空格（细节！！！）

3、处理数字

4、遇到操作符

5、计算最终结果

3、代码实现

1、题目链接

227. 基本计算器 II - 力扣（LeetCode）

2、分析

1、确定使用的数据结构

使用栈stack（数组模拟栈）存储‘前序操作符’为“+”的中间结果，

字符 op 作为操作符，初始化为 '+' ，表示默认的操作符为加。

2、处理空格（细节！！！）

直接跳过

3、处理数字

• 当遇到字符是数字（'0' 到 '9' 之间）时：
  • 定义一个临时变量 tmp 并初始化为 0 ，用于存储提取的数字。
  • 进入内层 while 循环，不断将数字字符转换为整数并累加到 tmp 中，直到遇到非数字字符。
  • 根据当前的操作符 op 进行相应的操作：
    • 如果 op 是 '+' ，将 tmp 压入栈中。
    • 如果 op 是 '-' ，将 -tmp 压入栈中。
    • 如果 op 是 '*' ，将栈顶元素乘以 tmp 。
    • 如果 op 是 '/' ，将栈顶元素除以 tmp 。

4、遇到操作符

将当前操作符更新为该操作符

5、计算最终结果

定义一个变量 ret 并初始化为 0 ，用于存储最终结果。

遍历栈中的元素，将它们相加存储到 ret 中。

3、代码实现

class Solution {
public:
    
    int calculate(string s) {
        vector<int> stack; //栈，只存放操作符为+的元素
        char op = '+';// 首元素的操作符默认为+
        int i = 0;

        while ( i < s.size())
        {
            //细节--空格直接跳过
            if (s[i] == ' ') i++;
            //遇到数字
            else if (s[i] <= '9' && s[i] >= '0')
            {
                int tmp = 0;

                //提取数字
                while ( i < s.size() && s[i] <= '9' && s[i] >= '0')
                {
                    tmp = tmp * 10 + ( s[i++] - '0' );
                }

                //对数字进行处理
                if (op == '+') stack.push_back(tmp);
                else if (op == '-') stack.push_back(-tmp);
                else if (op == '*') stack.back() *= tmp;
                else stack.back() /= tmp;
            }   
            else  //遇到操作符
            {
                op = s[i];
                i++;
            }           
        }

        //最后对栈处理，计算最终结果
        int ret = 0;
        for (auto a : stack) ret += a;

        return ret;
    }
};