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

目录

一、（leetcode 20）有效的括号

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

用栈存放 

将字符串直接当成栈 

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

---

一、（leetcode 20）有效的括号

力扣题目链接

状态：已AC，列好所有情况就容易了

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

1. 
2. 
3. 

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）删除字符串中的所有相邻重复项

力扣题目链接

状态：已AC

用栈存放 

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）逆波兰表达式求值

力扣题目链接

状态：已AC

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

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;}
};