代码随想录 | Day13 | 栈和队列：有效的括号&&删除字符串中的所有相邻重复项

20.有效的括号

思路：

分为2种情况

第一，遇到左括号类型，就入栈对应的右括号

第二，遇到右括号类型，看栈顶是否是对应的左括号，是的话就就弹出栈顶元素就行，不是的话就直接false，说明前面的左括号少了，而咱们多出来的这个右括号类型后面再也不可能被匹配掉

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        for(auto c:s)
        {
            //遇到左括号
            if(c=='(')
                st.push(')');
            else if(c=='[')
                st.push(']');
            else if(c=='{')
                st.push('}');
            //遇到右括号并且类型符合
            else if(!st.empty()&&c==st.top())
                st.pop();
            //不符合条件
            else
                return false;
        }
        return st.empty()?true:false;
    }
};

关键点：

1.遇到左括号入栈相应的右括号，方便后面进行比较

2.题目要求：左括号必须以正确的顺序闭合，这一要求直接印证了咱们的第二种情况

举例：

1
2
3

/*
(  [  {  ]  }  ) 这种情况下是不符合条件的，因为没有按照正确的顺序闭合，尽管数量匹配
*/

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

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

思路：

利用栈，遍历s然后将元素入栈

此时有两种情况，第一种情况是该元素和栈顶元素相同，那就弹出栈顶元素，相当于删除了重复项

第二种情况是该元素和栈顶元素不同，那就直接入栈即可

class Solution {
public:
    string removeDuplicates(string s) {
        stack<char> st;
        string str;
        for(auto c:s)
        {
            //不是重复元素
            if(st.empty() || st.top()!=c)
                st.push(c);
           	//是重复元素
            else
                st.pop();
        }
        while(!st.empty())
        {
            str+=st.top();
            st.pop();
        }
        //注意最后反转字符串
        reverse(str.begin(),str.end());
        return str;
    }
};

150.逆波兰表达式求值

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

思路：

两种情况

第一，遇到数字，入栈，作为操作数

第二，遇到运算符号，出栈前两个元素，进行相应的运算，再把结果入栈作为新的操作数

注意：

字符串转函数的使用

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