大纲
● 20. 有效的括号
● 1047. 删除字符串中的所有相邻重复项
● 150. 逆波兰表达式求值
有效的括号
题目链接:20. 有效的括号
题目需要判断括号是否匹配
解题思路:
使用栈来实现,当为**{[(时入栈,当遇到)]}时,判断栈顶元素释放能匹配。需要单独处理只有右边**单个括号的情况。
bool isRightString(string s)
{
stack<char> _stack;
for (int i = 0; i < s.size(); ++i) {
if (s[i] == '['
|| s[i] == '{'
|| s[i] == '(') {
_stack.push(s[i]);
}
if (s[i] == ']'
|| s[i] == '}'
|| s[i] == ')')
{
if (!_stack.empty()) {
char ch = _stack.top();
if ( (s[i] == ']' && ch != '[')
|| (s[i] == '}' && ch != '{')
|| (s[i] == ')' && ch != '('))
return false;
_stack.pop();
} else {
return false;
}
}
}
return _stack.empty();
}
删除字符串中的所有相邻重复项
题目链接:1047. 删除字符串中的所有相邻重复项
分析过程:
本题也是使用栈来解决,不断消除相邻相同的元素。剩下栈中的元素需要逆序。文章来源:https://www.toymoban.com/news/detail-676286.html
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;
}
逆波兰表达式求值
题目链接:150. 逆波兰表达式求值
分析过程:
逆波兰表达式其实就是后缀表达式求值,模拟计算机计算表达式的过程。思路是使用栈保存操作数,遇到操作符则取出栈中元素做计算,之后再把结果放回栈中。【特别要注意栈中元素放回顺序和实际顺序相反】
需要注意处理栈为空的情况和注意操作数顺序。文章来源地址https://www.toymoban.com/news/detail-676286.html
bool isNumber(string s) {
if (s == "+" || s == "-" || s == "*" || s == "/") {
return false;
}
return true;
}
int getExpressValue(vector<string>& tokens)
{
stack<int> _stack;
for (int i = 0; i < tokens.size(); ++i) {
if (!isNumber(tokens[i])) {
int val1 = _stack.top();
_stack.pop();
int val2 = _stack.top();
_stack.pop();
if (tokens[i] == "+") {
_stack.push(val2 + val1);
}
else if (tokens[i] == "-") {
_stack.push(val2 - val1);
}
else if (tokens[i] == "*") {
_stack.push(val2 * val1);
}
else {
_stack.push(val2 / val1);
}
} else {
int _val1 = atoi(tokens[i].c_str());
_stack.push(_val1);
}
}
return _stack.empty() ? 0 : _stack.top();
}
到了这里,关于day11 代码回想录-栈与队列part02-有效的括号&删除字符串中的所有相邻重复项&逆波兰表达式求值的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!