20.有效的括号
春节假期后的第一题。因为看到了主题是栈和队列，所以这道题很容易有思路。一下就写出来了。
class Solution {
public:
bool isValid(string s) {
stack<char> st;
for(int i=0; i<s.length(); i++){
if(st.empty()){
st.push(s[i]);
}
else{
if(((s[i] == ')') && (st.top() != '('))
|| ((s[i] == '}') && (st.top() != '{'))
|| ((s[i] == ']') && (st.top() != '['))){
return false;
}
else if((s[i] == ')') || (s[i] == '}') || (s[i] == ']')){
st.pop();
}
else{
st.push(s[i]);
}
}
}
if(st.empty()){
return true;
}
else{
return false;
}
}
};
但是对比了Carl的答案，发现自己写的还是有些啰嗦。很多地方可以优化，比如说可以先检查s的长度是不是复数，如果不是的话，那么其中肯定包括了不是有效的括号。所以以后做题的时候，要先从宏观的角度看看这道题。 而且在处理数据的角度来看，也是精妙了好多。Carl并没有把左括号放进来，而是把相对因的右括号放进来。然后对比下一个符号是不是等于目前的top的括号。这样写起来的确比我的更简洁。
1047.删除字符串中的所有相邻重复项
我开始是创建了一个栈来做这道题，但是忘了其实string本身就可以进行stack的操作。在我运行时间过长之后我才反应过来。以下是想到直接用string之后的结果。
class Solution {
public:
string removeDuplicates(string s) {
string res;
for(int i=0; i<s.length(); i++){
if(res.empty()){
res.push_back(s[i]);
}
else{
if(res.back() == s[i]){
res.pop_back();
}
else{
res.push_back(s[i]);
}
}
}
return res;
}
};
150.逆波兰表达式求值
同样是使用栈完成了这道题。比较简单。
class Solution {
public:
int evalRPN(vector<string>& tokens) {
int first_num,second_num,new_num;
stack<int> st;
for(int i=0; i<tokens.size(); i++){
if(tokens[i] == "*"){
second_num = st.top();
st.pop();
first_num = st.top();
st.pop();
new_num = first_num * second_num;
st.push(new_num);
}
else if(tokens[i] == "/"){
second_num = st.top();
st.pop();
first_num = st.top();
st.pop();
new_num = first_num / second_num;
st.push(new_num);
}
else if(tokens[i] == "+"){
second_num = st.top();
st.pop();
first_num = st.top();
st.pop();
new_num = first_num + second_num;
st.push(new_num);
}
else if(tokens[i] == "-"){
second_num = st.top();
st.pop();
first_num = st.top();
st.pop();
new_num = first_num - second_num;
st.push(new_num);
}
else{
new_num = stoi(tokens[i]);
st.push(new_num);
}
}
return st.top();
}
};
Carl写的比我简洁太多了，他首先是判断了目前要读取的是不是运算符号，如果是的话，在统一读stack里的两个数。如果不是的话，直接把数加进去。
class Solution {
public:
int evalRPN(vector<string>& tokens) {
// 力扣修改了后台测试数据，需要用longlong
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]));
}
}
int result = st.top();
st.pop(); // 把栈里最后一个元素弹出（其实不弹出也没事）
return result;
}
};
