day11 栈与队列
20.有效的括号
1047.删除字符串中的所有相邻重复项
150.逆波兰表达式求值
1 有效的括号
给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。
有效字符串需满足:
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 注意空字符串可被认为是有效字符串。
1.1 思路:
栈
3种错误情况:
- 奇数次多余
- 不匹配
- 偶数次多余
1.2 代码:
//4.有效的括号
bool isValid(string s){
//1. 情况1,字符串的字符个数为奇数
if(s.size()/2 != 0){
return false;
}
//2.
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();
}
}
2 删除字符串中的所有相邻重复项
给出由小写字母组成的字符串 S,重复项删除操作会选择两个相邻且相同的字母,并删除它们。
在 S 上反复执行重复项删除操作,直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
2.1 思路:
栈
字符串遍历,往栈中放,相同就弹出,不同就放入
2.2 代码:
string removeSameStr(string s){
stack<char> st;
for(char a : s){//判断是不是相同字符
if(st.empty() || s != st.top()){
st.push(a);
}
else{
st.pop();
}
}
string result = "";
while (!st.empty())
{
result += st.top();
st.pop();
}
reverse(result.begin(), result.end());
return result;
}
3 逆波兰表达式求值
根据 逆波兰表示法,求表达式的值。
有效的运算符包括 + , - , * , / 。每个运算对象可以是整数,也可以是另一个逆波兰表达式。
说明:
整数除法只保留整数部分。 给定逆波兰表达式总是有效的。换句话说,表达式总会得出有效数值且不存在除数为 0 的情况。
3.1 思路:
遇到运算符取2个值运算。
3.2 代码:
int evalRPN(vector<string>& tokens) {
stack<long long> st;
for (int i = 0; i < tokens.size(); i++) {
//如果是运算符就弹出2个元素,并运算放入栈;否则把字符放入栈
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;
}