摘要

• 今天主要学习的内容为栈的经典应用，栈是在我们需要处理相邻匹配元素的很好的一个工具。
• 解决问题时，可以从测试用例的角度去考虑，自己编写的代码能不能正确覆盖（通过）所有测试用例？先思考可能出现的情况，再动手写代码，不要急于求成。

今日学习的视频和文章

• 代码随想录 有效的括号
• 代码随想录 删除字符串中的所有相邻项
• 代码随想录 逆波兰表达式求值

LeetCode20 有效的括号

20. 有效的括号 - 力扣（Leetcode）

• 初见题目时的想法：
  • 从左到右扫描输入的字符串，遇到左括号即'('、'['、'{'时，则将该左括号入栈；遇到右括号即')'、']'、'}'时，检查栈顶的元素，如果
    1. 栈为空，则说明没有出现左括号就出现右括号，即括号没有成对出现或者出现了多余的右括号，所以返回false
    2. 栈顶元素不是与当前元素匹配的左括号，例如栈顶元素为'('而当前元素为']'，说明括号没有正确地成对闭合，而是出现了交错，也返回false
    3. 栈顶元素是与当前元素匹配的左括号，则让栈顶元素出栈，继续遍历输入字符串
  • 扫描完整个字符串后，如果栈为空，说明所有括号都正确地成对出现，返回true；如果栈不为空，说明有括号没有正确匹配，返回false。

完整的题解代码如下

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        for (auto& iter : s) {
            switch (iter) {
                case '(': st.push(')'); break;
                case '[': st.push(']'); break;
                case '{': st.push('}'); break;

                case ')':
                case ']':
                case '}': {
                    if (!st.empty()) {
                        if (iter != st.top()) {
                            return false;
                        }
                        else {
                            st.pop();
                        }
                    }
                    else {
                        return false;
                    }
                } break;

                default: break;
            }
        }
        return st.empty();
    }
};

• 看了讲解之后的思考：
  • 最近在学习软件测试，做实验时要求编写的测试用例尽可能地覆盖待测代码的每一条语句。其实反过来也是一样的，我们先考虑、分析输入可能有几种情况，再动手写代码，保证我们的代码能覆盖我们考虑到的所有可能情况。
• 本题中括号正确匹配的可能情况，抽象地来看，应该有这三种情况。
  1. 左括号多余
  2. 右括号多余
  3. 左右括号类型不匹配
• 再具体地去解释，就对应我上面写的代码思路。
  1. 左括号多余，则遍历完字符串后，栈中仍残留有括号，栈不为空
  2. 右括号多余，则说明没有出现左括号就出现右括号，即括号没有成对出现或者出现了多余的右括号
  3. 左右括号类型不匹配，栈顶元素不是与当前元素匹配的左括号，例如栈顶元素为'('而当前元素为']'，说明括号没有正确地成对闭合。

LeetCode1047 删除字符串中所有相邻重复项

1047. 删除字符串中的所有相邻重复项 - 力扣（Leetcode）

• 初见题目时的想法：
• 这道题目的关键在于“相邻”和“重复”。且题目提示我们，“相邻”是动态的。又想到相邻跟先后顺序有关，后遍历到的会和再下一次遍历到的相邻，联想到栈的“后进先出”。所以这题用栈来记录我们遍历过的元素及其顺序，就可以很好的处理“相邻”的匹配问题。
• 将遍历到的元素不断尝试入栈
  1. 在当前元素入栈前，先判断栈是否为空，若栈为空则当前元素直接入栈
  2. 若栈不为空，则判断栈顶元素是否与当前元素相同，若相同则栈顶元素出栈且当前元素不入栈，完成一次删除；若栈顶元素不与当前元素相同则直接入栈。
• 遍历字符串完后仍然保存在栈中的元素即可组成答案字符串，但要注意栈的“后进先出”，字符的出栈顺序和最后答案的字符顺序是相反的，所以不断将栈顶元素放入答案字符串直到栈为空后，还要对答案字符串做一次reverse操作。

完整题解代码如下：

class Solution {
public:
    string removeDuplicates(string s) {
        stack<char> st;
        for (auto& iter : s) {
            if (!st.empty() && iter == st.top()) {
                st.pop();
                continue;
            }
            st.push(iter);
        }

        string res(st.size(), 0);
        for (int i = 0; i < res.size(); i++) {
            res[i] = st.top();
            st.pop();
        }
        reverse(res.begin(), res.end());

        return res;
    }
};

LeetCode150 逆波兰表达式求值

150. 逆波兰表达式求值 - 力扣（Leetcode）

• 初见题目时的想法：这道题是数据结构里的经典例子了，大二上课的时候也学过，不过实现中还有一些细节需要注意的。
  • 操作数的顺序：要注意21-是2 - 1而不是1-2，虽然是1先出栈，但逆波兰表达式仍然是从左向右读的，因此还是后出栈的2作为第一个操作数。
  • 两个操作数运算后的结果要记得放回栈中。
  • 从左到右遍历逆波兰表达式，若遇到数字，则将数字放入栈中；若遇到操作符，则从栈中依次取出两个操作数，运算后将结果放回栈中。

完整的题解代码如下

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<long long> st;
        for (auto& iter : tokens) {
            if (iter == "+" || iter == "-" || iter == "*" || iter == "/") {
                long long num2 = st.top();
                st.pop();
                long long num1 = st.top();
                st.pop();
                if (iter == "+") st.push(num1 + num2);
                if (iter == "-") st.push(num1 - num2);
                if (iter == "*") st.push(num1 * num2);
                if (iter == "/") st.push(num1 / num2);
            }
            else {
                st.push(stoll(iter));
            }
        }
        return st.top();
    }
};