stack
1. How to use?
#include <stack>
using namespace std;
2. stack的定义
stack<typename> name;
3. 元素的访问
- 只能通过
top()来访问栈顶元素
4. 常用函数解析
-
push(x): O(1) -
top(): O(1) -
pop(): O(1) -
empty(): O(1) -
size(): O(1)
- stack没有
clear()方法，因为stack 没用提供迭代器,而vector或list中clear 是通过迭代器来实现的。 - 置空方法：
while(!s.empty()) s.pop();
5. 常见用途
- 模拟实现一些递归，防止程序对栈内存的限制而导致程序运行错误
6. 习题
- 简单计算器
-
提示
float num1 = nums.top(); float num2 = nums.top(); float re = num2 operaotr num2; // 注意：这里的顺序很容易出错- 新的操作符需要与栈顶的操作符进行循环比较，知道比栈顶的优先级高，才可插入栈中。
- 我原先是新加的操作符与栈顶的操作符优先级进行比较，只有当栈顶的优先级更高时，才弹出栈顶的操作符，这样做会有问题。当出现2-2-2这样的式子的时候，结果会变成2，所以后面我把判断条件改成了如果当栈顶的优先级更高或者他们的优先级相同时，弹出栈顶的操作符。
此代码提交后会出现段错误，查不出时什么原因，但是这个代码，去掉外层循环，可以在牛客网的相同题目（input只需要输入一行）上accept。猜测不被codeup accept的原因是外层终止条件出现了问题，但是我把网上其他人的终止条件都试过，还是会出现段错误。
#include<iostream>
#include<string>
#include<stack>
#include<queue>
using namespace std;
int N;
int charTpri(char ch) {
int pri;
switch (ch) {
case '+':
pri = 1;
break;
case '-':
pri = 2;
break;
case '*':
pri = 3;
break;
case '/':
pri = 4;
break;
}
return pri;
}
int main() {
stack<int> operators;
stack<double> nums;
string str = "";
while (getline(cin, str), str != "0") {
while (!operators.empty()) operators.pop();
while (!nums.empty()) nums.pop();
int num = 0;
// +:1 -:2 *:3 /:4. The bigger, the more prior
operators.push(0);
for (int i = 0; i < str.length(); i++) {
if (str[i] == ' ') {
if (num != 0) {
nums.push(num);
}
// the previous char is operator
else {
}
// reinit
num = 0;
}
else if (str[i] >= '0' && str[i] <= '9') {
num = num * 10 + (str[i] - '0');
if (i == str.length() - 1) {
nums.push(num);
}
}
else {
int top_pri = operators.top();
int cur_pri = charTpri(str[i]);
while (top_pri >= cur_pri) {
float num2 = nums.top();
//
nums.pop();
float num1 = nums.top();
nums.pop();
float res = 0;
if (top_pri == 1) {
res = num1 + num2;
}
else if (top_pri == 2) {
res = num1 - num2;
}
else if (top_pri == 3) {
res = num1 * num2;
}
else {
res = num1 / num2;
}
nums.push(res);
operators.pop();
top_pri = operators.top();
}
operators.push(cur_pri);
}
}
while (operators.top() != 0) {
int top_pri = operators.top();
operators.pop();
float num2 = nums.top();
nums.pop();
float num1 = nums.top();
nums.pop();
float res = 0;
if (top_pri == 1) {
res = num1 + num2;
}
else if (top_pri == 2) {
res = num1 - num2;
}
else if (top_pri == 3) {
res = num1 * num2;
}
else {
res = num1 / num2;
}
nums.push(res);
}
printf("%.2f\n", nums.top());
//getline(cin, str);
}
return 0;
}
- 括号匹配
-
提示
代码(使用vc6.0在使用
cin.ignore()后还是会有问题(需要在每个getline后在使用ignore)，推荐使用其他IDE)
#include <stack>
#include <iostream>
#include <string>
using namespace std;
bool matching(char ch1, char ch2) {
if ((ch1 == '[' && ch2 == ']') ||
(ch1 == '(' && ch2 == ')') ||
(ch1 == '{' && ch2 == '}')) return true;
else return false;
}
stack<char> op;
int main() {
int N;
cin >> N;
// 需要用不带参数的get()方法接收掉换行符
cin.ignore();
for (int i = 0; i < N; i++) {
bool flag = false;
string str;
getline(cin, str);
while (!op.empty()) {
op.pop();
}
for (int j = 0; j < str.length(); j++) {
if (str[j] == '[' || str[j] == '{' || str[j] == '(') {
op.push(str[j]);
}
else if (str[j] == ']' || str[j] == '}' || str[j] == ')') {
if (op.empty()) {
flag = false;
break;
//printf("%s\n", "no");
}
else {
char ch = op.top();
op.pop();
if (matching(ch, str[j])) flag = true;
else {
flag = false;
break;
}
}
}
else {
continue;
}
}
//
if (flag == true && op.empty()) cout << "yes" << endl;
else cout << "no" << endl;
}
return 0;
}
