1. DS堆栈–逆序输出（STL栈使用）
题目描述
C++中已经自带堆栈对象stack，无需编写堆栈操作的具体实现代码。
本题目主要帮助大家熟悉stack对象的使用，然后实现字符串的逆序输出
输入一个字符串，按字符按输入顺序压入堆栈，然后根据堆栈后进先出的特点，做逆序输出
stack类使用的参考代码
n包含头文件：#include
n创建一个堆栈对象s（注意stack是模板类）：stack s;//堆栈的数据类型是字符型
n把一个字符ct压入堆栈：s.push(ct);
n把栈顶元素弹出：s.pop();
n获取栈顶元素，放入变量c2：c2 =s.top();
n判断堆栈是否空：s.empty()，如果为空则函数返回true，如果不空则返回false
输入
第一行输入t，表示有t个测试实例
第二起，每一行输入一个字符串，注意字符串不要包含空格
字符串的输入可以考虑一下代码：
#include int main() { string str; Int len; cin>>str; //把输入的字符串保存在变量str中 len = str.length() //获取输入字符串的长度 }
输出
每行逆序输出每一个字符串
输入样例
2
abcdef
aabbcc
输出样例
fedcba
ccbbaa
参考代码
#include<iostream> #include<stack> #include<string> using namespace std; int main() { int t; cin>>t; while(t--) { string str; int len; cin>>str; len = str.size(); stack<char> s; for(int i=0;i<len;i++) { char ct=str[i]; s.push(ct); } for(int i=0;i<len;i++) { str[i]=s.top(); s.pop(); } cout<<str<<endl; } }
2. DS堆栈–行编辑
题目描述
使用C++的STL堆栈对象，编写程序实现行编辑功能。行编辑功能是：当输入#字符，则执行退格操作；如果无字符可退就不操作，不会报错
本程序默认不会显示#字符，所以连续输入多个#表示连续执行多次退格操作
每输入一行字符打回车则表示字符串结束
注意：必须使用堆栈实现，而且结果必须是正序输出
输入
第一行输入一个整数t，表示有t行字符串要输入
第二行起输入一行字符串，共输入t行
输出
每行输出最终处理后的结果，如果一行输入的字符串经过处理后没有字符输出，则直接输出NULL
输入样例
4 chinaa# sb#zb#u ##shen###zhen### chi##a#####
输出样例
china
szu
sz
NULL
参考代码
#include<iostream> #include<stack> #include<string> using namespace std; int main() { int t; cin>>t; while(t--) { string str; int len; cin>>str; len = str.size(); stack<char> s; for(int i = 0;i<len;i++) { if(str[i] == '#') { if(!s.empty()) s.pop(); } else { s.push(str[i]); //cout<<str[i]; } } if(s.empty()) { cout<<"NULL"<<endl; continue; } str.clear(); len=0; while(!s.empty()) { str+=s.top(); len++; s.pop(); } //cout<<len<<endl; for(int i=0;i<len;i++) { char ct=str[i]; s.push(ct); } for(int i=0;i<len;i++) { str[i]=s.top(); s.pop(); } cout<<str<<endl; } }
3. DS堆栈–括号匹配
题目描述
处理表达式过程中需要对括号匹配进行检验，括号匹配包括三种：“(”和“)”，“[”和“]”，“{”和“}”。例如表达式中包含括号如下：
| ( | ) | [ | ( | ) | ( | [ | ] | ) | ] | { | } |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
从上例可以看出第1和第2个括号匹配，第3和第10个括号匹配，4和5匹配，6和9匹配，7和8匹配，11和12匹配。从中可以看到括号嵌套的的情况是比较复杂的，使用堆栈可以很方便的处理这种括号匹配检验，可以遵循以下规则：
1、 当接收第1个左括号，表示新的一组匹配检查开始；随后如果连续接收到左括号，则不断进堆栈。
2、 当接受第1个右括号，则和最新进栈的左括号进行匹配，表示嵌套中1组括号已经匹配消除
3、 若到最后，括号不能完全匹配，则说明输入的表达式有错
建议使用C++自带的stack对象来实现
stack类使用的参考代码
n包含头文件：#include
n创建一个堆栈对象s（注意stack是模板类）：stack s;//堆栈的数据类型是字符型
n把一个字符ct压入堆栈：s.push(ct);
n把栈顶元素弹出：s.pop();
n获取栈顶元素，放入变量c2：c2 =s.top();
n判断堆栈是否空：s.empty()，如果为空则函数返回true，如果不空则返回false
输入
第一行输入一个t，表示下面将有t组测试数据。接下来的t行的每行输入一个表达式，表达式只考虑英文半角状态输入，无需考虑中文全角输入
输出
对于每一行的表达式，检查括号是否匹配，匹配则输入ok，不匹配则输出error
输入样例
2 (a+b)[45+(-6)] [58]/{(a+b)-6
输出样例
ok
error
参考代码
#include<iostream> #include<stack> #include<string> using namespace std; int main() { int t; cin>>t; while(t--) { stack<char> s; string str; cin>>str; for(int i=0;i<str.size();i++) { if(str[i]=='('||str[i]=='{'||str[i]=='[') s.push(str[i]); else { if(str[i]==')') { if(s.top()=='(') s.pop(); } else if(str[i]=='}') { if(s.top()=='{') s.pop(); } else if(str[i]==']') { if(s.top()=='[') s.pop(); } } } if(s.empty()) cout<<"ok"<<endl; else cout<<"error"<<endl; } }
