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

目录

一、（leetcode 20）有效的括号

二、（leetcode 1047）删除字符串中的所有相邻重复项

用栈存放 

将字符串直接当成栈 

三、（leetcode 150）逆波兰表达式求值

---

一、（leetcode 20）有效的括号

力扣题目链接

三种情况会出现不匹配的情况

class Solution {
public:
    bool isValid(string s) {
        if (s.size() % 2 != 0) return false;
        stack<char> st;
        for (int i = 0; i < s.size(); 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();
        }
        return st.empty();
    }
};

二、（leetcode 1047）删除字符串中的所有相邻重复项

力扣题目链接

用栈存放 

class Solution {
public:
    string removeDuplicates(string S) {
        stack<char> st;
        for(char t:S)
        {
            if(st.empty()||t!=st.top())
            {
                st.push(t);
            }
            else
            {
                st.pop();
            }
        }
        string result = "";
        while (!st.empty()) { // 将栈中元素放到result字符串汇总
            result += st.top();
            st.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;
    }
};

三、（leetcode 150）逆波兰表达式求值

力扣题目链接

思路：遇到数字则入栈；遇到运算符则取出栈顶两个数字进行计算，并将结果压入栈中

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        for (int i = 0; i < tokens.size(); i++) {
            if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {
                int num1 = st.top();
                st.pop();
                int num2 = st.top();
                st.pop();
                if (tokens[i] == "+") st.push(num2 + num1);
                if (tokens[i] == "-") st.push(num2 - num1);
                if (tokens[i] == "*") st.push(num2 * num1);
                if (tokens[i] == "/") st.push(num2 / num1);
            } else {
                st.push(stoll(tokens[i]));
            }
        }
        int result = st.top();
        st.pop(); // 把栈里最后一个元素弹出（其实不弹出也没事）
        return result;
    }
};