20. 有效的括号
题目链接：
https://leetcode.cn/problems/valid-parentheses/
思考：
用栈进行存储，碰到左括号加入，右括号进行判断
代码：
class Solution {
public:
bool isValid(string s) {
stack<char> kuohao;
int len = s.size();
for(int i=0;i<len;i++)
{
char c = s[i];
if( c == '(' or c == '{' or c == '[')
{
kuohao.push(c);
}
else
{
if(kuohao.empty())
return false;
char top = kuohao.top();
if(c == ')' && top != '(')
return false;
if(c == '}' && top != '{')
return false;
if(c == ']' && top != '[')
return false;
kuohao.pop();
}
}
if(kuohao.empty())
{
return true;
}
else
return false;
}
};
1047. 删除字符串中的所有相邻重复项
题目：https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/
思路：
栈可以用来解决这种消除匹配的问题。
来一个字符，判断栈顶元素是否相同，相同则弹出，并且该元素不加入，否则加入。
代码：
class Solution {
public:
string removeDuplicates(string s) {
stack<char> xiaoxiaole;
int len = s.size();
for(int i=0;i<len;i++)
{
bool flag = 0;
while(!xiaoxiaole.empty() && xiaoxiaole.top() == s[i])
{
cout<<"消除："<<xiaoxiaole.top()<<endl;
xiaoxiaole.pop();
flag=1;
}
if(flag==0)
{
cout<<"加入:"<<s[i]<<endl;
xiaoxiaole.push(s[i]);
}
}
int size = xiaoxiaole.size();
string new_s;
new_s.resize(size);
while(size--)
{
new_s[size] = xiaoxiaole.top();
xiaoxiaole.pop();
}
return new_s;
}
};
150. 逆波兰表达式求值
题目：
https://leetcode.cn/problems/evaluate-reverse-polish-notation/
思路：
使用栈解决。
遇到运算符，弹出栈顶两个元素进行计算，把加入入栈
否则直接入栈。
代码：
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> s;
int len = tokens.size();
for(int i=0;i<len;i++)
{
string top = tokens[i];
if(top != "+" && top != "-" && top != "*" && top!="/")
{
int input = stoll(top);
s.push(input);
}
else
{
int token1 = s.top();
s.pop();
int token2 = s.top();
s.pop();
int res;
if(top=="+") s.push(token2+token1);
if(top=="-") s.push(token2-token1);
if(top=="*") s.push(token2*token1);
if(top=="/") s.push(token2/token1);
}
}
return s.top();
}
};
