栈¶
前置知识¶
一维数组、stack
目标¶
利用栈解决表达式求值的问题
What¶
栈是一种线性数据结构 支持两种基本操作：进栈、出栈 栈的修改与访问，是按照先进后出的原则进行
Why¶
栈的应用：回溯、递归、深度优先搜索
How¶
用数组模拟栈¶
// 0 入栈
// 1 出栈
// 2 输出栈顶
#include <bits/stdc++.h>
using namespace std;
int stk[110], tt;
int n, op, x;
int main() {
cin >> n;
while (n--) {
cin >> op;
if (op == 0) {cin >> x; stk[++tt] = x;}
if (op == 1 && op > 0) tt--;
if (op == 2 && op > 0) cout << stk[tt] << '\n';
}
return 0;
}
用STL中的栈¶
// 0 入栈
// 1 出栈
// 2 输出栈顶
#include <bits/stdc++.h>
using namespace std;
stack<int> stk;
int n, op, x;
int main() {
cin >> n;
while (n--) {
cin >> op;
if (op == 0) {cin >> x; stk.push(x);}
if (op == 1 && !stk.empty()) stk.pop();
if (op == 2 && !stk.empty()) cout << stk.top() << '\n';
}
return 0;
}
总结¶
表达式括号匹配(stack)，只判断括号是否匹配 后缀表达式的值，给你的是后缀，但也需要用getline读入，拆数字 表达式求值，给你的中缀表达式，一个字符串读入，也需要拆数字，需要处理运算符优先级 中缀表达式值(expr)，还要判断表达式的合法性，最麻烦，但也最锻炼人