代码随想录算法训练营第十一天|20 有效的括号、1047 删除字符串中的所有相邻重复项、150 逆波兰表达式求值

20 有效的括号

题目链接：有效的括号

思路

由于栈结构的特殊性，非常适合做对称匹配类的题目。按照逻辑来讲，首先我们要确定下有几种不匹配的情况：

• 多了左括号
• 多了右括号
• 左右括号不匹配

然后左括号和右括号是一对一的，在消除完后，理应栈为空。
在多了左括号时，可以想到的是，消除结束后，栈不为空。
在多了右括号时，可以想到的是，栈中没有匹配的元素可以出栈。
左右括号不匹配时，可以想到的是，栈中出栈的元素和字符串中的元素不相等。

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

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

题目链接：删除字符串中的所有相邻重复项

思路

这道题目天生就是为栈这种数据类型准备的。元素进栈时，如果栈顶元素和元素相等，则消除，弹出栈顶元素。只不过要注意栈为空时，无法获得栈顶元素这种情况。然后将字符串中的所有元素遍历，最终栈中剩下的元素就是剔除相邻重复项后的字符串，只不过进行了翻转，所有还要做个翻转。

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

150 逆波兰表达式求值

题目链接：逆波兰表达式求值

思路

这道题目和上题类似，遇到+、-、*、/符号时弹出栈中的两个元素，然后做相应运算后再入栈。

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        int a,b;
        for(int i=0; i<tokens.size(); i++){
            if(tokens[i] == "+"){
                a = st.top();
                st.pop();
                b = st.top();
                st.pop();
                st.push(b + a); 

            }
            else if(tokens[i] == "-"){
                a = st.top();
                st.pop();
                b = st.top();
                st.pop();
                st.push(b - a); 
            }
            else if(tokens[i] == "*"){
                a = st.top();
                st.pop();
                b = st.top();
                st.pop();
                st.push(b * a); 
            }
            else if (tokens[i] == "/"){
                a = st.top();
                st.pop();
                b = st.top();
                st.pop();
                st.push(b / a); 
            }
            else{
                st.push(stoi(tokens[i]));
            }
        }
        return st.top();
    }
};

参考链接：

1. 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#%E6%80%9D%E8%B7%AF