LeetCode 20.有效的括号
题目：
给定一个只包括 '('，')'，'{'，'}'，'['，']'的字符串 s ，判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。
思路：
括号不匹配总共有两大类：1、顺序匹配；2、数量不匹配，其中数量不匹配又分为左边多了和右边多了两种情况，所以总共有三种情况：1、左边多了括号；2、括号顺序不匹配；3、右边多了括号。解决方法可以是找到左括号将相应的右括号入栈，等遍历到右括号时弹出栈内的右括号进行比较，情况1会出现栈内有多余的括号，情况2会出现弹出的右括号与遍历的右括号不相等，情况3会出现空栈但是还没有遍历完。根据以上情况返回相应的值即可。
代码：
class Solution {
public:
bool isValid(string s) {
stack<char> temp;
if(s.size()%2!=0)return false;
for(int i=0;i<s.size();i++)
{
if(s[i]=='(')
{
temp.push(')');
}else if(s[i]=='[')
{
temp.push(']');
}else if(s[i]=='{')
{
temp.push('}');
}else if(temp.empty()||s[i]!=temp.top())
{
return false;
}
else{temp.pop();}
}
return temp.empty();
}
};
LeetCode 1047. 删除字符串中的所有相邻重复项
题目：
给出由小写字母组成的字符串S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。在 S 上反复执行重复项删除操作，直到无法继续删除。在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
思路：
这道题可以把每次遍历之前的元素入栈，如果遍历的元素和栈顶的元素相等，则说明找到了相邻的重复项，此时只要将栈里面的元素弹出即可，如果遍历的元素和栈顶的元素不相等，则将该元素入栈。
代码：
class Solution {
public:
string removeDuplicates(string s) {
string temp;
for(int i=0;i<s.size();i++)
{
if(temp.empty()||temp.back()!=s[i])
{
temp.push_back(s[i]);
}else{
temp.pop_back();
}
}
return temp;
}
};
LeetCode 150.逆波兰表达式求值
题目：
给你一个字符串数组 tokens ，表示一个根据逆波兰表示法 表示的算术表达式。请你计算该表达式。返回一个表示表达式值的整数。
思路：
将中缀表示的式子转换成二叉树的形式，二叉树后序遍历的结构就是逆波兰式。逆波兰式转化为中缀表达式的过程是将逆波兰式从头遍历，碰到数字就入栈，碰到字母就弹出栈里面的两个数字运算，将结果再次入栈，直至遍历完成。需要注意的是第一次弹出的数是被减数/被除数，第二次弹出的是减数/除数。
代码：
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<long long> temp;
for(int i=0;i < tokens.size();i++)
{
if(tokens[i] == "+" || tokens[i]== "-" || tokens[i] == "*" || tokens[i] == "/" )
{
long long n1=temp.top();
temp.pop();
long long n2=temp.top();
temp.pop();
if(tokens[i] == "+" ) temp.push(n1+n2);
if(tokens[i] == "-" ) temp.push(n2-n1);
if(tokens[i] == "*" ) temp.push(n1*n2);
if(tokens[i] == "/" ) temp.push(n2/n1);
}
else
{
temp.push(stoll(tokens[i]));
}
}
int result=temp.top();
temp.pop();
return result;
}
};
