0 更新记录

  • 2024-09-26: 初始版本

这篇文章写的很不在状态，断断续续写了三天四天才完成……

栈是一个比较常用的基础数据结构，其后进先出（LIFO，Last In First Out）的特点适合一些特定的场景。比如下面题目中的括号匹配问题、相邻元素消除、表达式计算等。

使用栈解决的问题基本都是模拟运算或者操作过程，最难的地方在于将复杂的问题拆解成各种情况。

与前面写过的题目总结类似，代码不求精简，尽量做到逻辑清晰，有的地方看起来可能比较啰嗦。

1 题目列表

LeetCode题目链接 本文小节链接
20.有效的括号 20.有效的括号
1047.删除字符串中的所有相邻重复项 1047.删除字符串中的所有相邻重复项
1209.删除字符串中的所有相邻重复项 II 1209.删除字符串中的所有相邻重复项 II
150.逆波兰表达式求值 150.逆波兰表达式求值
224.基本计算器 224.基本计算器
227.基本计算器 II 227.基本计算器 II

2 题解

20.有效的括号

思路

匹配类的问题是用栈解决的经典问题。核心思路就是能正确匹配的括号直接“消除”，栈中总是保留左括号，等待栈顶加入的右括号将栈内元素全部消除。

按照这个思路可以发现，对于匹配的括号，只要所有输入遍历完了，那么栈也弹空了，只要最后栈中还有元素，或者读到右括号时，栈已经空了，就是出现了不匹配的情况。

不匹配有两种情况分别对应多左括号和多右括号：

  • 多左括号：即缺少与之匹配的右括号，最终会造成栈中剩余左括号无法配对弹出；
  • 多右括号：缺少左括号，最后会导致栈提前清空。

实现细节

代码实现并不复杂，C++中有专门的栈容器适配器stack可以使用，适配器定义了栈相关的接口，底层容器默认使用deque。也可以直接使用双端队列deque或者数组vector自己按照栈只能在一端写入和移除数据来模拟栈。

下面给出两个版本的实现：

  • 入栈左括号，遇到右括号时判断栈顶是不是能够配对消除的左括号，如果配对则消除，不配对立即返回false；
  • 入栈右括号，即遍历输入时遇到左括号，将其对应的右括号入栈，如果遇到右括号，只需要判断栈顶和当前的右括号是否一致即可，判断条件较版本一简洁一些。

入栈右括号的代码中使用了switch-case，需要注意case如果没有break，会继续匹配后面的case，直到遇到break或者switch语句结束。

这个特性可以用来匹配多种case，比如这里用这个特性实现了if(s[i] == ')' || s[i] == ']'|| s[i] == '}')这样的逻辑。

代码-入栈左括号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        for(char ch : s) {
            if(ch == '(' || ch == '{' || ch == '[') {
                st.push(ch);
            } else {
                if(st.empty()) return false;
                if(st.top() == '(' && ch != ')') return false;
                if(st.top() == '[' && ch != ']') return false;
                if(st.top() == '{' && ch != '}') return false;
                st.pop();
            }
        }
        if(!st.empty()) return false;
        return true;
    }
};

代码-入栈右括号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        for(int i = 0; i < s.size(); i++) {
            switch(s[i]) {
                case '(': st.push(')'); break;
                case '[': st.push(']'); break;
                case '{': st.push('}'); break;
                case ')':
                case ']':
                case '}':
                    if(!st.empty() && s[i] == st.top())
                        st.pop();
                    else
                        return false;
                    break;
                default: break;
            }
        }
        if(!st.empty()) return false;
        return true;
    }
};

1047.删除字符串中的所有相邻重复项

思路

这道题从题意上来看，是一个相邻元素消除的问题，这与在20.有效的括号中的“消除”思路类似。

逐个遍历输入字符，使用一个栈来存放那些等待消除的字符。在读到字符后检查栈顶的字符，如果两个字符相同，则直接出栈，这两个字符消除；如果字符不相同，表示当前的输入字符也是一个等待消除的字符，应当入栈。

输入遍历结束后，留在栈中的字符，就是需要输出的字符。不过需要注意，栈底字符是先加入的字符，栈顶是后加入的字符，直接按照出栈顺序拼接的字符串与正确结果是相反的，最后还需要做一次字符串反转。

实现细节

代码实现比较直观，逻辑上没有特别需要解释的地方。只是注意在获取栈顶元素（的引用）top()和出栈pop()之前，需要确保栈非空。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    string removeDuplicates(string s) {
        stack<char> st;
        st.push(s[0]);
        for(int i = 1; i < s.size(); ++i) {
            char ch = s[i];
            if(!st.empty() && st.top() == ch)
                st.pop();
            else
                st.push(s[i]);
        }
        string result;
        while(!st.empty()) {
            result += st.top();
            st.pop();
        }
        std::reverse(result.begin(), result.end());
        return result;
    }
};

1209.删除字符串中的所有相邻重复项 II

思路

本题要求比上一题更复杂一些，需要相邻个数达到k个之后进行删除。由于还是相邻元素删除，基本思路还是使用栈，不过需要额外记录字符出现的次数。可以使用两个栈，一个和上一题一样记录遍历过的字符，栈内元素是等待消除的元素；另一个栈记录对应字符的个数，两个栈同步更新。

实现细节

本题使用了vector来模拟栈。在后面程序中，也经常使用vector，用push_back()，pop_back()和back()对应栈的push()，pop()和top()。有时在输出时需要顺序遍历栈（从栈底到栈顶），对比本题和上一题输出部分的代码，可以发现使用vector模拟栈带来的一点便利。

代码实现逻辑：

  • 当栈为空或者当前遍历到的输入字符为一个新字符时（即与栈顶字符不同），将新字符入栈，并记录其出现次数为1；
  • 当输入字符与栈顶字符相同时，只需要更新其出现次数；
  • 检查出现次数是否到达k个，如果是直接删除这个字符，将其计数也删除；
  • 最后遍历栈中字符，按照cnt栈中记录的出现次数拼接到输出字符串上。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    string removeDuplicates(string s, int k) {
        vector<int> cnt;
        vector<char> st;
        for(auto& ch : s) {
            // 栈空或者新字符
            if(st.empty() || st.back() != ch) {
                st.push_back(ch);
                cnt.push_back(1);
            } else { // ch 与栈顶元素相同
                cnt.back()++;
            }
            if(cnt.back() == k) {
                st.pop_back();
                cnt.pop_back();
            }
        }
        string result;
        // “正向遍历”
        for(int i = 0; i < st.size(); i++) {
            while(cnt[i]--) result += st[i];
        }
        return result;
    }
};

一点改进

以上解决方法是分别记录字符与次数，同步更新，可以将字符和次数封装成一个pair，这样只需要操作一个栈即可，代码实现更简洁。

代码的输出部分，对st的遍历使用了结构化绑定直接获取pair的first和second。

结构化绑定声明需要C++17支持。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    string removeDuplicates(string s, int k) {
        vector<pair<char, int>> st;
        for(int i = 0; i < s.size(); i++) {
            char ch = s[i];
            if(st.empty() || ch != st.back().first) {
                st.push_back({ch, 1});
            } else {
                st.back().second++;
                if(st.back().second == k) st.pop_back();
            }
        }
        string result;
        // “正向遍历”
        for(auto& [ch, n] : st) {
            while(n--) result += ch;
        }
        return result;
    }
};

150.逆波兰表达式求值

思路

逆波兰表达式（Reverse Polish Notation，RPN）也叫后缀表达式。从题目给出的几个样例可以看出，逆波兰表达式的特点是运算符（加减乘除）总是在两个操作数后面。

我们习惯上使用的如 $1+1$ 这种运算符在操作数中间的表达式为中缀表达式，中缀表达式对计算机来说是不易解析和计算的，并且需要用括号来指定运算优先级。而后缀表达式的优点就是方便用栈计算，并且运算符的位置决定运算次序，不需要使用括号来指定优先级。

将中缀表达式转换为后缀表达式是一个比较复杂的过程，在下一题224.基本计算器中将实现一个简化的转换程序。

本题先解决后缀表达式的计算，其实知道是用栈这一数据结构来计算就已经扫除了本问题的最大困难，简单模拟一下运算过程可以归纳基本运算步骤如下：

  • 遍历输入字符，遇到数字则入栈；
  • 遇到运算符则弹出两个数，根据运算符做运算，运算结果入栈；
  • 遍历结束栈中只剩下唯一的元素即整个表达式运算结果。

实现细节

代码实现上需要注意，在弹出操作数时，先弹出的数记为num2，后弹出的数记为num1，后面计算都是num1在运算符左侧，num2在运算符右侧。这样做是考虑到不满足交换律的运算，如减法和除法，两个操作数需要保持和输入相同的顺序参与计算。

题目中特意提示的向零截断的除法无需特殊处理，在C++中/运算本来就是向零截断的。

题目保证输入合法，所有最后栈中一定会剩下唯一的元素，就是表达式的计算结果，我们使用vector模拟栈，直接取出st[0]即可，或者使用更符合栈逻辑的st.back()。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        vector<int> st;
        unordered_set<string> opeators{"+", "/", "*", "-"};
        for(auto& token : tokens) {
            // 遇到运算符：pop两个数，计算后再入栈
            if(opeators.count(token) > 0) {
                // pop两个数，计算结果再入栈
                int num2 = st.back();
                st.pop_back();
                int num1 = st.back();
                st.pop_back();
                int res = 0;
                if(token == "+") res = num1 + num2;
                if(token == "-") res = num1 - num2;
                if(token == "*") res = num1 * num2;
                if(token == "/") res = num1 / num2;
                st.push_back(res);
            } else {
                // 遇到数字，转int后入栈
                st.push_back(stoi(token));
            }
        }
        return st[0];
    }
};

224.基本计算器

思路

本题似乎被LeetCode修改过，之前可能没有这条要求：
- 可以用作一元运算 (即 -1 和 -(2 + 3) 是有效的)
LeetCode评论区及题解很多都没有考虑这种情况。

在完成上一题150.逆波兰表达式求值后，解决此问题的一个自然的想法就是，先将输入字符串转换成一个后缀表达式，然后直接调用上一题的代码即可。

中缀表达式转后缀的分析

接下来就按照这个思路，分析一下如何将中缀表达式转换成后缀表达式。

需要说明：此处分析及代码考虑了比本题要求更多的情况：

  • 考虑了乘法和除法，输入字符串中合法的字符增加了*和/；
  • /运算表示向零截断的除法，即C++中/运算符的含义；
  • 考虑了乘除的运算优先级高于加减。

接下来结合几个例子来分析解析中缀表达式（输入字符串s），组织后缀表达式（以字符串数组形式存储在result）的过程：

解析过程中需要使用一个栈op_stk来临时存放表达式。例如对于最简单的 $1+2$ 转换为[1,2,+]，运算符+与操作数2位置的交换，就需要一种“先进后出”的逻辑。

解析表达式字符串s，遍历每个字符ch = s[i]：

两种最常规情况是：

  • 如果ch是空格，跳过，解析下一字符；
  • 如果ch是数字，取出完整数字，将数字入栈；

取出数字也有不同的实现方法：

  • 可以遇到第一个数字就循环取出完整的数字，然后移动i来跳过后面几位数字字符，这种方法在循环中操作循环变量，要格外小心越界；
  • 也可以使用一个变量来存当前的数字，每次循环只扩展当前字符这一位，直到当前字符不再是数字，或者循环结束，得到完整的数字后将这个变量清空，准备记录下个数字。
取数字的两种方法
取数字的两种方法

程序中使用的是第二种方法，并直接使用数字字符来拼接完整数字字符串，以字符串形式入栈。

考虑第一个例子 $1+2$ ，转换后为[1,2,+]：

第一个例子
第一个例子

可以发现ch是运算符时，需要做的操作之一：将栈内元素弹出到结果，直到栈空，然后将运算符入栈。

还可以发现在输入遍历结束后，还需要将栈中元素全部弹出到结果中。

考虑第二个例子 $\left ( 1+2 \right ) \times 3$ ，转换后为[1,2,+,3,*]：

第二个例子
第二个例子

ch是左括号时，应当直接入栈。

ch是右括号时，不断地从栈中弹出到结果，直到遇到左括号，将左括号弹出丢弃。

ch是运算符时，需要做的操作之二：将栈内元素弹出到结果，直到遇到左括号时停止，并将运算符入栈。

考虑第三个例子 $1+2 \times 3+4$ ，转换为[1,2,3,×,+,4,+]：

第三个例子
第三个例子

这个例子为了说明如何处理运算优先级，按图示流程可以发现，ch是运算符时需要做的操作之三为：将栈内元素弹出到结果，直到遇到更低优先级的运算符时停止，并将当前的运算符入栈。

上面三个例子几乎覆盖了所有情况，还剩下负数问题需要解决，这就是LeetCode后来对本题的补充条件。

负数在表达式中只可能有两种出现形式：

  • 出现在最开始，可以不加括号，如 $-1+2$；
  • 出现在任意操作数位置，表达式必须加括号， $2+(-1)$。

这两种情况需要分别判断，但是处理方式均为将负数变为（0 - 正数）。

最终得到了下面的分析结果：

对于每个字符ch：

  • ch是空格，跳过，解析下一字符；
  • ch是数字，取出完整数字，将数字入栈；
  • ch是左括号，直接入栈；
  • ch是右括号，将栈内元素弹出到结果，直到栈顶为左括号，将左括号弹出丢弃；
  • ch是运算符，入栈，入栈前将栈内元素弹出到结果，栈空时停止，栈顶为左括号时停止，栈顶为更低优先级运算符停止；

最后将栈弹空到结果。

负数的处理逻辑，遇到-先判断是负号还是减法，负号分为输入字符串首字符是-和用括号括起来的负数两种情况。负号处理方式统一为在栈中额外添加一个"0"，然后将负号当成普通的减法运算符。

实现细节

运算符及优先级使用一个哈希表来存储unordered_map<string, int> op_map，键为字符串格式的运算符，值为其优先级，值可以任意指定，只需要保证运算符之间的大小关系正确即可。这样做的好处是如果需要扩展其他运算可以直接添加，无需修改代码中的优先级判断逻辑。另外哈希表中还加入了括号作为最高优先级的运算符，这样对于非空格的字符，可以使用isOperator()函数查询哈希表判断字符是数字（函数返回false）还是非数字（函数返回true）。

num_str是用来取出完整数字的变量，在遇到数字字符时拼接，遇到非数字字符时入栈并清空。需要注意的是，在输入表达式最后一个字符是数字字符时，num_str在取到完整数字后，由于不会再遇到非数字字符遍历输入字符串的循环就已经终止，导致最后一个数还没有入栈，所以在循环结束后，要判断num_str是否为空，不为空要将其入栈。

针对负数的两种情况做额外判断，注意栈在尝试访问栈顶时必须保证非空：

  • 首字符是-：if(ch == "-" && i == 0)；
  • 用括号括起来的负数：if(ch == "-" && !op_stk.empty() && op_stk.back() == "(")。

这两种情况都是在栈中补一个"0"，然后当成普通减法计算，这就要求这两个判断及补零的操作，应当在处理普通减法运算符的逻辑之前，也就是在 ch是运算符，入栈，入栈前将栈内元素弹出到结果，栈空时停止，栈顶为左括号时停止，栈顶为更低优先级运算符停止 这一系列操作之前。

然后就是完成ch是运算符的出栈操作，出栈过程需要判断栈非空，栈顶非左括号，栈顶是运算符且优先级更高四个条件，代码中使用while判断两个条件，栈非空并且栈顶不是左括号，循环中使用if判断另外两个条件，如果栈顶是运算符，并且优先级低于当前运算符，直接break结束循环。

最后清空栈后，得到后缀表达式，调用evalRPN()函数即可得到结果。evalRPN()函数直接使用150.逆波兰表达式求值程序，需要将函数参数修改为const，这里涉及C++的语法规则：非const引用的初始值应当是左值，我们在调用时使用的是evalRPN(toRPN(s))，toRPN(s)的返回值属于非引用返回的临时变量，是纯右值，不能直接传给非const引用的参数。

注意C++语言的一个小细节：单字符类型ch到字符串s的转换

1
2
3
4
5
6
7
8
char ch = 'A';
// 错误，调用字符串构造函数，没有参数为char的构造函数
string s = ch;
// 正确，调用字符串构造函数
string ch(1, s[i]);
// 正确，调用 operator=(char) 函数
string s;
s = ch;

代码-后缀表达式法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
class Solution {
public:
    // 运算符及优先级
    unordered_map<string, int> op_map{{"+", 0}, {"-", 0}, {"*", 1}, {"/", 1}, {"(", 10}, {")", 10}};
    int calculate(string s) {
        return evalRPN(toRPN(s));
    }
    // 处理成后缀表达式
    vector<string> toRPN(string s) {
        // 模拟栈，临时存放表达式
        vector<string> op_stk;
        // 结果
        vector<string> result;
        string num_str;
        for(int i = 0; i < s.size(); i++) {
            string ch;
            ch = s[i];
            // ch是空格，跳过
            if(ch == " ") continue;
            if(!isOperator(ch)) {
                // ch是数字，直接拼到字符串中
                num_str += ch;
            } else {
                // ch非数字，先将数字入栈
                if(!num_str.empty()) {
                    op_stk.push_back(num_str);
                    num_str.clear();
                }
                // ch是左括号，直接入栈
                if(ch == "(") {
                    op_stk.push_back("(");
                    continue;
                }
                // ch是右括号，弹出到结果中，遇到左括号停止，将左括号丢弃
                if(ch == ")") {
                    while(!op_stk.empty() && op_stk.back() != "(") {
                        result.push_back(op_stk.back());
                        op_stk.pop_back();
                    }
                    // 合法输入不会有括号不匹配，遇到右括号则栈中必然会有左括号
                    // 此处可以不判空直接弹出
                    if(!op_stk.empty() && op_stk.back() == "(") op_stk.pop_back();
                    continue;
                }
                // ch是四则运算符，入栈
                // 入栈前将栈内元素弹出到结果，栈空时停止，栈顶为左括号时停止，栈顶为更低优先级运算符停止
                // 针对首字符为负数的特殊处理
                if(ch == "-" && i == 0) {
                    op_stk.push_back("0");
                }
                // 针对非首字符为负数的特殊处理
                if(ch == "-" && !op_stk.empty() && op_stk.back() == "(") op_stk.push_back("0");
                // 栈非空并且栈顶不是左括号
                while(!op_stk.empty() && op_stk.back() != "(") {
                    // 栈顶是运算符，并且优先级低于当前运算符，停止出栈
                    if(isOperator(op_stk.back()) && (op_map[ch] > op_map[op_stk.back()])) break;
                    result.push_back(op_stk.back());
                    op_stk.pop_back();
                }
                // 最后将运算符入栈
                op_stk.push_back(ch);
            }
        }
        // 将最后一个数入栈，然后将栈弹空
        if(!num_str.empty()) {
            result.push_back(num_str);
        }
        while(!op_stk.empty()) {
            result.push_back(op_stk.back());
            op_stk.pop_back();
        }
        return result;
    }
    bool isOperator(string s) {
        return (op_map.count(s) > 0);
    }
    int evalRPN(vector<string> tokens) {
        vector<int> st;
        unordered_set<string> opeators{"+", "/", "*", "-"};
        for(auto& token : tokens) {
            if(opeators.count(token) > 0) {
                int num2 = st.back();
                st.pop_back();
                int num1 = st.back();
                st.pop_back();
                int res = 0;
                if(token == "+") res = num1 + num2;
                if(token == "-") res = num1 - num2;
                if(token == "*") res = num1 * num2;
                if(token == "/") res = num1 / num2;
                st.push_back(res);
            } else {
                st.push_back(stoi(token));
            }
        }
        return st[0];
    }
};

通用另法-双栈法

另外一种解决表达式类问题的通用方法是使用两个栈分别保存运算符和操作数，表达式解析与计算同步进行。

表达式解析过程与中缀转后缀的过程基本一致，对字符ch的五种情况讨论也一致，区别主要在于：

  • 数字入栈时入数字栈，非数字入栈时入符号栈；
  • 中缀转后缀方法中出栈写入结果的过程在此方法中代替为计算，即根据现有的数字和符号栈，进行后缀表达式计算，结果压入数字栈；
  • 使用calc函数完成计算，写法与evalRPN()非常相似；
  • 引入pre_action变量，保存上一步做了什么操作。

pre_action变量有什么用？

对照上一方法，思路转变还是比较顺畅的，只是这个pre_action变量的引入比较突兀。这个变量是为了解决判断-字符是负号还是减法时遇到的问题。

上一方法中，使用这样的条件来判断-是否为负号if(ch == "-" && !op_stk.empty() && op_stk.back() == "(")，这是因为上一方法中，数字和非数字都放在同一个栈op_stk中，对于 $(-3)$ 这种情况，使用当前字符为-并且栈顶是左括号是可以正确判断为负号的；而对于 $ (4-3) $ 这种常规情况，在当前字符为-时，栈中应当为[(, 4]，栈顶不是左括号，所以会判定为是减法。

但是，本方法使用双栈将数字与非数字分开，对于上面两个例子，在遇到-时，符号栈的栈顶都是左括号，这样会把正常的减法误判为负号，错误的在栈中加零，导致结果出错。

pre_action变量的引入就是为了解决这个问题。在判断-是否为负号之前，需要知道-之前是数字还是左括号：如果是数字，那上一次入栈一定是入数字栈，如果是左括号，那一定是入符号栈。

pre_action在入数字栈时赋值为1，入符号栈时赋值为0（完全可以用布尔类型），判断-是否为负号时，只需要额外检查pre_action，如果是0则说明是负号，上一步是左括号入符号栈；如果是1则说明上一步是数字入数字栈，是减法。

当然可以对最初的输入字符串做预处理避免这种复杂的判断，比如将字符串所有空格删除，然后替换"(-为"(0-"可以解决任意位置的负数；在初始的数字栈中直接加入一个0可以解决初始位置的负数，这样能省下一些麻烦。

代码-双栈法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
class Solution {
public:
    // 运算符及优先级
    unordered_map<string, int> op_map{{"+", 0}, {"-", 0}, {"*", 1}, {"/", 1}, {"(", 10}, {")", 10}};
    int calculate(string s) {
        return doubleStack(s);
    }
    int doubleStack(string s) {
        // 符号栈
        vector<string> op_stk;
        // 数字栈
        vector<int> num_stk;
        // 结果
        int result;
        string num_str;
        // 上一次操作是加了数字栈 1，加了符号栈 0
        // 用于辅助判断遇到"-"上一步做了什么
        int pre_action = 0;
        for(int i = 0; i < s.size(); i++) {
            string ch;
            ch = s[i];
            // ch是空格，跳过
            if(ch == " ") continue;
            if(!isOperator(ch)) {
                // ch是数字，直接拼到字符串中
                num_str += ch;
            } else {
                // ch是非数字，先将数字入栈
                if(!num_str.empty()) {
                    num_stk.push_back(stoi(num_str));
                    num_str.clear();
                    pre_action = 1;
                }
                // ch是左括号，直接入栈
                if(ch == "(") {
                    op_stk.push_back("(");
                    pre_action = 0;
                    continue;
                }
                // ch 是右括号，将符号栈内能计算的符号算完，遇到第一个左括号停止，将左括号丢弃
                if(ch == ")") {
                    while(!op_stk.empty() && op_stk.back() != "(") {
                        // 计算所有能算的数
                        calc(num_stk, op_stk);
                    }
                    // 弹出左括号
                    if(!op_stk.empty() && op_stk.back() == "(") op_stk.pop_back();
                    pre_action = 0;
                    continue;
                }
                // ch 是四则运算符，入符号栈，入栈前将符号栈内能计算的符号算完，结果加入数字栈。
                // 计算停止条件：栈空，遇到左括号，遇到低优先级运算符
                // 针对首字符为负数的特殊处理
                if(ch == "-" && i == 0) num_stk.push_back(0);
                // 针对非首字符为负数的特殊处理
                // 当前为"-"，上一符号是"("，上一操作不是入数字栈
                // PS：如果上一步骤是入数字栈，则是一次正常减法操作
                if(ch == "-" && pre_action == 0 && !op_stk.empty() && op_stk.back() == "(") num_stk.push_back(0);
                // 栈非空并且不是左括号
                while(!op_stk.empty() && op_stk.back() != "(") {
                    // 出栈时遇到运算符，并且是优先级低于当前运算符的，停止出栈
                    if(isOperator(op_stk.back()) && (op_map[ch] > op_map[op_stk.back()])) break;
                    // 计算所有能算的数
                    calc(num_stk, op_stk);
                }
                // 最后符号入栈
                op_stk.push_back(ch);
                pre_action = 0;
            }
        }
        // 将最后的数字加入数字栈
        if(!num_str.empty()) num_stk.push_back(stoi(num_str));
        // 继续计算清空符号栈
        while(!op_stk.empty()) calc(num_stk, op_stk);
        return num_stk[0];
    }
    bool isOperator(string s) {
        return (op_map.count(s) > 0);
    }
    // 计算当前的符号栈和数字栈，注意引用传入
    void calc(vector<int>& num_stk, vector<string>& op_stk) {
        if(op_stk.empty()) return;
        if(num_stk.size() < 2) return;
        // pop两个数和一个操作符计算，注意数的顺序
        int num2 = num_stk.back();
        num_stk.pop_back();
        int num1 = num_stk.back();
        num_stk.pop_back();
        int res = 0;
        string op = op_stk.back();
        op_stk.pop_back();
        if(op == "+") res = num1 + num2;
        if(op == "-") res = num1 - num2;
        if(op == "*") res = num1 * num2;
        if(op == "/") res = num1 / num2;
        num_stk.push_back(res);
    }
};

227.基本计算器 II

思路

这道题甚至可以把224.基本计算器的代码复制过来直接提交，从题目区别上来看，这道题增加了乘除法及运算符优先级的考虑，乘除法和运算符优先级虽然上题没有要求，但是代码中已经实现。另外本题输入中没有括号，没有单独出现的负数，难度相较于上一题其实是降低一些的。

不再赘述，直接使用224.基本计算器的代码提交。

3 参考

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

快来参与讨论吧~

博客分类标签归档
项目没什么用占个位置
社交友链留言板
更多关于GitHub
本站由 @gsh1209 使用 Stellar 主题创建
Copyright © 2023 - BG3LNT.XYZ
Favicon图标来自 @ChenCJ
本站所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处
正在计算运行时间...

蒙ICP备2022000455号-2