Appearance
简介
栈是一种「先进后出」的数据结构。类似于在桶中堆积物品,取物品时只能从顶端开始取,最先进桶的被压在最底下,最后被取出来。
表达式计算
算术表达式分为三类(
- 中缀表达式:形如「
」,如「 」; - 前缀表达式:形如「
」,如「 」; - 后缀表达式:形如「
」,如「 」.
计算前/后缀表达式时,先递归求出
后缀表达式
- 定义一个栈,用于存放数;
- 逐一扫描后缀表达式中的元素:
- 若扫到一个数
,则把 入栈; - 若扫到运算符
,则弹出栈顶的两个元素,二者做 计算。将计算结果入栈。
- 若扫到一个数
最终的栈顶元素就是计算结果。时间复杂度为
cpp
bool isdigit(char ch) { // 判断是否为数字
return ch >= '0' && ch <= '9';
}
bool isop(char ch) { // 判断是否为运算符
return ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '^';
}
double postfix_calc(string str) {
stack<double> s; int i = 0;
s = stack<double>();
while (i < str.size()) {
if (isdigit(str[i])) { // 假定输入数据只包含整数
double x = 0;
while (isdigit(str[i]))
x = x * 10 + str[i ++] - '0';
s.push(x);
continue;
}
else if (isop(str[i])) {
double r = s.top(); s.pop();
double l = s.top(); s.pop();
double ans;
switch (str[i]) {
case '+' : ans = l + r; break;
case '-' : ans = l - r; break;
case '*' : ans = l * r; break;
case '/' : ans = l / r; break;
case '^' : ans = pow(l, r); break;
}
s.push(ans);
}
i ++;
}
return s.top();
}
中缀表达式
先将中缀表达式转换成 后缀表达式 再计算。
- 定义一个栈,用于存放运算符;
- 逐一扫描中缀表达式中的元素:
- 若扫到一个数
,直接输出 ; - 若扫到「左括号」,把左括号入栈;
- 若扫到「右括号」,重复取栈顶并输出,直到栈顶为左括号。最后弹出左括号;
- 若扫到其它运算符
,重复取栈顶并输出,直到栈顶的优先级大于 或者栈空。最后把 入栈。
- 若扫到一个数
运算符优先级越大,越晚出栈,因此可以将「左括号」的优先级视作最低,「右括号」的优先级视作最高.
时间复杂度为
运算符 | |||||
---|---|---|---|---|---|
优先级 | 最低(0) | 低(1) | 中(2) | 高(3) | 最高(4) |
cpp
int lev(char ch) { // 返回运算符对应的优先级
int level;
switch (ch) {
case '(' : level = 0; break; case ')' : level = 4; break;
case '+' : level = 1; break; case '-' : level = 1; break;
case '*' : level = 2; break; case '/' : level = 2; break;
case '^' : level = 3; break;
}
return level;
}
double infix_calc(string str) {
string data;
stack<char> op;
int i = 0;
while (i < str.size()) {
if (isdigit(str[i])) {
while (isdigit(str[i]))
data += str[i ++];
data += ' '; // 数与数之间用空格区分
continue;
}
else if (isop(str[i])) {
while (!op.empty() && lev(op.top()) <= lev(str[i])) {
if (op.top() != '(' && op.top() != ')')
data += op.top();
op.pop();
}
op.push(str[i]);
}
i ++;
}
while (!op.empty()) { // 输出栈内剩余元素
if (op.top() != '(' && op.top() != ')')
data += op.top();
op.pop();
}
return postfix_calc(data);
}
单调栈
单调栈中的元素从栈底到栈顶满足单调性。
插入元素
将元素
- 从栈顶依次弹掉比
大的元素,保证 栈顶; - 将
入栈。
cpp
stack<int> s;
void insert(int x) {
while (!s.empty() && s.top() > x)
s.pop();
s.push(x);
}
应用
单调递增栈可以实现快速查询「左边第一个更小的元素」。例如
顺序扫描
cpp
stack<int> s;
for (int i = 1; i <= n; i ++) {
while (!s.empty() && s.top() > a[i])
s.pop();
if (!s.empty())
cout << s.top() << endl; // 输出 a[i] 左边第一个更小的元素
else cout << "none" << endl; // 如果没有则输出 none
s.push(a[i]);
}
- 求左边第一个更小的元素:顺序扫描 + 单调递增栈;
- 求左边第一个更大的元素:顺序扫描 + 单调递减栈;
- 求右边第一个更小的元素:倒序扫描 + 单调递增栈;
- 求右边第一个更大的元素:倒序扫描 + 单调递减栈。