算法训练营第十一天（7.22）

目录

LeeCode20. Valid Parentheses

LeeCode1047. Remove All Adjacent Duplicates In String

LeeCode150. Evaluate Reverse Polish Notation

LeeCode20. Valid Parentheses

题目地址：力扣

题目类型：栈模拟

思路：简单栈模拟，直接AC，不过注意压栈的对象，比如碰到 '(' 压栈 ')' 可以减少码量

class Solution {
public:
    bool isValid(string s) {
        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();
    }
};

LeeCode1047. Remove All Adjacent Duplicates In String

题目地址：力扣

题目类型：栈模拟

思路：不断压栈，最后依次取出

1. 如果栈为空或者栈顶元素不等于正在处理元素，则压栈
2. 否则，弹栈

class Solution {
public:
    string removeDuplicates(string s) {
        stack<char> st;
        for (char c : s) {
            if (st.empty() || st.top() != c) st.push(c);
            else st.pop();
        }
        string str = "";
        while (!st.empty()) {
            str += st.top();
            st.pop();
        }
        reverse(str.begin(), str.end());
        return str;
    }
};

LeeCode150. Evaluate Reverse Polish Notation

题目地址：​​​​​​​力扣

题目类型：栈模拟

思路：最基本的后缀表达式，使用栈模拟

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