题目来源和说明
该题目来源自王道考研机试，希望通过该题目梳理总结机试中栈的应用问题。
题目描述
在某个字符串（长度不超过100）中有左括号、右括号和大小写字母；规定任何一个左括号都从内到外与它右边最靠近的右括号匹配。写一个程序，找到无法匹配的左括号和右括号，输出原来字符串，并在写一行标出不能匹配的括号。不能匹配的左括号用“$”标注，不能匹配的右括号用“?”标注。
样例
输入：
)(rttyy())sss)(
输出：
)(rttyy())sss)(
? ?$
C++ 代码
#include<iostream>
#include<stack>
using namespace std;
stack<int> S; //定义一个栈
char str[110]; //保存输入的字符串
char ans[110]; //保存输出字符串
int main() {
while(scanf("%s",str)!=EOF) {
int i;
for(i=0;str[i]!=0;i++) {
if(str[i]=='(') {
S.push(i); //将其数组的下标放入
ans[i]=' ';//暂且将对应的输出字符串的位置改为空格
}
else if(str[i]==')') {
if(S.empty()==false) {
S.pop(); //栈顶位置左括号与其匹配，从栈中弹出已经匹配的左括号
ans[i]=' ';
}
else ans[i]='?';//栈顶为空，则无法找到左括号与之匹配，修改输出位置为？
}
else { //其他字符不用管
ans[i]=' ';
}
}
while(!S.empty()) { //字符串遍历完，留在栈中的左括号无法匹配
ans[S.top()]='$';
S.pop();
}
ans[i]=0; //为了使得输出形成字符串，在其最后一个字符后添加一个空字符
puts(str);
puts(ans);
}
return 0;
}
同类题目
- 简单计算器
2006年浙江大学计算机以及软件工程研究生机试题目
简要分析
- 设立两个栈，一个保存运算符，另一个保存数字
- 在表达式某位添加标记运算符，该运算符运算优先级最低
- 从左到右依次遍历字符串，若遍历到运算符，则将其与运算符栈顶元素比较，若运算符栈栈顶运算符优先级小于该运算符或者此时运算符栈为空，则将该运算符压入堆栈。遍历字符串中下一个元素
- 若运算符栈栈顶运算符优先级大于该运算符，则弹出该栈顶运算符，再从数字栈中依次弹出两个栈顶数字，完成弹出的运算符对应的运算得到结果后，再将该结果压入数字栈中，重复比较此时栈顶运算符与当前遍历到的运算符优先级，根据优先级大小重复步骤3或者步骤4
- 若遍历到表达式中的数字，直接压入数字栈中
- 若运算符堆中仅存两个运算符且栈顶元素为我们人为添加的编辑运算符，那么表达式运算借宿，此时数字栈中唯一的数字即为表达式的值。
下面给出两份代码，第一份是王道考研书上给出的参考代码，但是没有分函数，嵌套关系复杂；这里又给出了第二份代码，本人更倾向于第二种。
C++代码
#include<iostream>
#include<stack>
using namespace std;
char str[220];//保存表达式字符串
int mat[][5]={ //优先级矩阵，若mat[i][j]==1,则表示i号运算符优先级大于j号运算符，运算符编码规则为+为1号，-为2号，*为3号，/为4号，我们人为添加再表达式尾部的标记为运算符0号。
1,0,0,0,0,
1,0,0,0,0,
1,0,0,0,0,
1,1,1,0,0,
1,1,1,0,0,
};
stack<int> op;//运算符栈
stack<double> in; //数字栈
void getOp(bool &reto,int &retn,int &i) { //获得表达式中下一个元素，若函数运行结束时，引用变量reto为true，则表示该元素为一个运算符，其标号保存在引用变量retn中；
//否则表示该元素为一个数字，气质表示再retn中，引用变量i表示遍历到的字符串下标
if(i==0 && op.empty()==true) { //若此时遍历字符串第一个字符，则运算符为空，我们认为添加编号为0的标记符号
reto=true;
retn=0;
return;
}
if(str[i]==0) {//空字符，表示字符串遍历完
reto=true;
retn=0;
return;
}
if(str[i]>='0'&&str[i]<='9') {
reto=false;
}
else {
reto=true;
if(str[i]=='+') retn=1;
else if(str[i]=='-') retn=2;
else if(str[i]=='*') retn=3;
else if(str[i]=='/') retn=4;
i+=2; //跳过该运算符和运算符后面的空格
return;
}
retn=0; //返回结果为数字
for(;str[i]!=' '&&str[i]!=0;i++) {
retn=retn*10+str[i]-'0';
}
if(str[i]==' ')
i++;
return;
}
int main() {
while(true) {
char ch;
int i=0;
while((ch=getchar())!='\n') {
str[i++]=ch;
}
str[i]='\0';
if(str[0]=='0' && str[1]==0) break; //输入只有一个0
bool retop;
int retnum;
int idx=0;
while(!op.empty()) op.pop();
while(!in.empty()) in.pop(); //清空
while(true) {
getOp(retop,retnum,idx); //获取表达式中下一个元素
if(retop==false) {//数字
in.push((double)retnum);
}
else { //字符
double temp;
if(op.empty()==true || mat[retnum][op.top()]==1) {
op.push(retnum);
}
else {
while(mat[retnum][op.top()]==0) {
int ret=op.top(); //栈中存放的是标号
op.pop();
double b=in.top();
in.pop();
double a=in.top();
in.pop();
if(ret==1) temp=a+b;
else if(ret==2) temp=a-b;
else if(ret==3) temp=a*b;
else temp=a/b;
in.push(temp);
}
op.push(retnum);
}
}
if(op.size()==2&&op.top()==0) break; //若堆栈中只有两个元素，且栈顶为标记运算符，则表达式求值借宿
}
printf("%.2f\n",in.top());
}
return 0;
}
#include<iostream>
#include <string.h>
#include<stack>
using namespace std;
char str[300];
stack<char> op;
stack<double> data;
void clear() {
while(!op.empty()) op.pop();
while(!data.empty()) data.pop();
}
int Priority(char c) {
if(c=='+' || c=='-') return 1;
else if(c=='*' || c=='/') return 2;
else return 0;
}
void GetNum(int &x,int &i) {
x=0;
while(str[i]!=' '&&str[i]!='\0') {
x=x*10+(str[i]-'0');
i++;
}
if(str[i]==' ') i++;
}
void CalOnce() {
if(data.size()<2) return;
double b=data.top();
data.pop();
double a=data.top();
data.pop();
switch(op.top()) {
case '+':data.push(a+b);break;
case '-':data.push(a-b);break;
case '*':data.push(a*b);break;
case '/':data.push(a/b);break;
}
op.pop();
return;
}
void Calculate() {
int x,i=0;
int len=strlen(str);
clear(); //清空栈
op.push('#');
while(i<len) {
if(str[i]>='0'&&str[i]<='9') {
GetNum(x,i);
data.push((double)x);
}
else {
if(Priority(str[i])>Priority(op.top())) op.push(str[i]);
else {
while(Priority(str[i])<=Priority(op.top())) {
CalOnce();
}
op.push(str[i]);
}
i=i+2;
}
}
while(Priority(op.top())!=0) CalOnce();
//最后输入的数没有处理，处理一下，假设输入了一个优先级很低的运算符
printf(".2f\n",data.top()); //输出结果
}
int main() {
while(gets(str)) {
if(strcmp("0",str)==0) break;
CalOnce();
}
return 0;
}
- 堆栈的使用
https://www.nowcoder.com/questionTerminal/e91982a145944ceab6bb9a4a508e0e26
简要分析
模拟堆栈的三种操作而已，逻辑上不难，但是特别要注意的是吸收缓冲区中的回车问题！
C++代码
#include<iostream>
#include<stack>
using namespace std;
stack<int> S;
int main() {
int n;
char c;
int d;
while(scanf("%d",&n)!=EOF && n!=0) {
for(int i=0;i<n;i++) {
getchar(); //特别注意读入回车
scanf("%c",&c);
switch(c) {
case 'A':{
if(S.empty()) printf("E\n");
else printf("%d\n",S.top());
break;
}
case 'P':{
scanf("%d",&d);
S.push(d);
break;
}
case 'O': {
if(!S.empty())
S.pop();
}
}
}
printf("\n");
while(!S.empty()) { //清空
S.pop();
}
}
return 0;
}
京公网安备 11010502036488号