栈与队列|20. 有效的括号、1047. 删除字符串中的所有相邻重复项、150. 逆波兰表达式求值
20. 有效的括号
自己审题思路
有效括号的匹配可以使用栈来解决问题
看完代码随想录题解后的收获
不同情况下的收敛
1、字符串里左方向的括号多余了，所以不匹配。
2、括号没有多余，但是括号的类型没有匹配上。
3、字符串里右方向的括号多余了，所以不匹配。
代码：
class Solution {
public:
bool isValid(string s) {
if (s.size() % 2 != 0) return false; // 如果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(']');
// 第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号 return false
// 第二种情况：遍历字符串匹配的过程中，发现栈里没有我们要匹配的字符。所以return false
else if (st.empty() || st.top() != s[i]) return false;
else st.pop(); // st.top() 与 s[i]相等，栈弹出元素
}
// 第一种情况：此时我们已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false，否则就return true
return st.empty(); // 直接return true "(("过不了；
}
};
参考详解
1047. 删除字符串中的所有相邻重复项
自己审题思路
使用栈进行删除相邻重复项
看完代码随想录题解后的收获
思路基本一致，可以拿字符串直接作为栈，这样省去了栈还要转为字符串的操作。
代码：
class Solution {
public:
string removeDuplicates(string S) {
stack<char> st;
for (char s : S) {
if (st.empty() || s != st.top()) {
st.push(s);
} else {
st.pop(); // s 与 st.top()相等的情况
}
}
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;
}
};
参考详解
150. 逆波兰表达式求值
自己审题思路
这道题读题的时候没有读懂
看完代码随想录题解后的收获
理解了逆波兰表达式的来龙去脉，并了解后缀表达式对于计算机的友好（不用运算符进行优先级比较）
代码：
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<long long> st;
for (int i = 0; i < tokens.size(); i++) {
if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {
long long num1 = st.top();
st.pop();
long long 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])); //stoll函数将字符串转换成long long型整数
}
}
int ans = st.top();
st.pop();
return ans;
}
};
上面代码使用了
stoll()函数完成了字符串到整形（64位）的转换，也可以使用atoi(token(i).c_str())将数字转换为整形（c_str()将string字符串转换成C语言形式的字符串(const char*)，并返回一个指向该字符串首字符的指针(临时指针，随着string的变化而发生变化，所以对于c_str()函数的返回值 ，谨慎进行操作)），其中atoi()C库函数将字符串转换为整形。
