算法刷题 Day 11 | 20. 有效的括号 1047. 删除字符串中的所有相邻重复项 150. 逆波兰表达式求值

20. 有效的括号

讲完了栈实现队列，队列实现栈，接下来就是栈的经典应用了。

大家先自己思考一下 有哪些不匹配的场景，在看视频 我讲的都有哪些场景，落实到代码其实就容易很多了。

题目链接/文章讲解/视频讲解：https://programmercarl.com/0020.%E6%9C%89%E6%95%88%E7%9A%84%E6%8B%AC%E5%8F%B7.html

Tips：思路其实很简单，就是用栈来实现，要注意中间可能也会出现 栈空的情况，要注意判断不要出现对空栈的操作。

我的题解：

class Solution {
public:
    bool isValid(string s) {
        stack<char> stackChar;
        for(int i = 0; i<s.size();i++){
            if(s[i] == '(' ||s[i] == '{'||s[i] == '['){
                stackChar.push(s[i]);
            }
            else{
                if(s[i] == ')'){
                    if(!stackChar.empty() && stackChar.top() == '('){
                        stackChar.pop();
                    }
                    else{
                        return false;
                    }
                }
                else if(s[i] == ']'){
                    if(!stackChar.empty() && stackChar.top() == '['){
                        stackChar.pop();
                    }
                    else{
                        return false;
                    }
                }
                else if(s[i] == '}'){
                    if( !stackChar.empty() && stackChar.top() == '{'){
                        stackChar.pop();
                    }
                    else{
                        return false;
                    }
                }
            }
        }
        if(stackChar.empty()){
            return true;
        }
        return false;

    }
};

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

栈的经典应用。

要知道栈为什么适合做这种类似于爱消除的操作，因为栈帮助我们记录了 遍历数组当前元素时候，前一个元素是什么。

题目链接/文章讲解/视频讲解：https://programmercarl.com/1047.%E5%88%A0%E9%99%A4%E5%AD%97%E7%AC%A6%E4%B8%B2%E4%B8%AD%E7%9A%84%E6%89%80%E6%9C%89%E7%9B%B8%E9%82%BB%E9%87%8D%E5%A4%8D%E9%A1%B9.html

Tips：这道题有两个要注意的点

1. 字符串可以通过for (char s : S) {}这种方式来遍历

2. 需要腾空stack的时候不能用for循环，因为stack.size()是会随着元素出栈变小的，这样后面的元素就出不来了（因为i>=stack.size()了），要用while(!stack.empty())才行。

我的题解：

class Solution {
public:
    string removeDuplicates(string s) {
        stack<char> stackChar;
        for(int i = 0; i< s.size();i++){
            if(stackChar.empty()){
                stackChar.push(s[i]);
            }
            else{
                if(stackChar.top() == s[i]){
                    stackChar.pop();
                }
                else{
                    stackChar.push(s[i]);
                }
            }
        }
        string result = "";
        while(!stackChar.empty()){
            result+=stackChar.top();
            stackChar.pop();
        }
        reverse(result.begin(),result.end());
        return result;
    }
};

除了上面这种方法，还可以拿字符串直接作为栈，这样省去了栈还要转为字符串的操作。

class Solution {
public:
    string removeDuplicates(string S) {
        string result;
        for(char s : S) {
            if(result.empty() || result.back() != s) {
                result.push_back(s);
            }
            else {
                result.pop_back();
            }
        }
        return result;
    }
};

150. 逆波兰表达式求值

本题不难，但第一次做的话，会很难想到，所以先看视频，了解思路再去做题

题目链接/文章讲解/视频讲解：https://programmercarl.com/0150.%E9%80%86%E6%B3%A2%E5%85%B0%E8%A1%A8%E8%BE%BE%E5%BC%8F%E6%B1%82%E5%80%BC.html

Tips：需要注意，测试用例中数字可能很大，需要用longlong，同时因为只有数字会被压入栈，所以stack定义为longlong即可，字符串转数字的操作在入栈时完成。

我的题解：

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        // 力扣修改了后台测试数据，需要用longlong
        stack<long long> st;
        for(int i = 0; i<tokens.size();i++){
            if(tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/"){
                long long num2 = st.top();
                st.pop();
                long long num1 = st.top();
                st.pop();
                if(tokens[i] == "+") st.push(num1 + num2);
                if(tokens[i] == "-") st.push(num1 - num2);
                if(tokens[i] == "*") st.push(num1 * num2);
                if(tokens[i] == "/") st.push(num1 / num2);
            }
            else{
                st.push(stoll(tokens[i]));
            }
        }
        return st.top();
    }
};