题目:
7-1 括号匹配 (30 分)
给定一串字符,不超过100个字符,可能包括括号、数字、字母、标点符号、空格,编程检查这一串字符中的( ) ,[ ],{ }是否匹配。
输入格式:
输入在一行中给出一行字符串,不超过100个字符,可能包括括号、数字、字母、标点符号、空格。
输出格式:
如果括号配对,输出yes,否则输出no。
输入样例1:
sin(10+20)
输出样例1:
yes
输入样例2:
{[}]
输出样例2:
no
分析:
通过详读题目以及例题我们可以知道:程序会读入随机输入的一串字符串,而当只有 '('和')' 、'['和']' 、 '{'和'}'相匹配的时候输出“yes”,其他情况都会输出“no”。
这时候我们可以采用顺序栈的结构来解决这一个问题:
将所有的左括号(即" ( 、[ 、{ ")存入栈中,遇到右括号(即" )、]、}")时出栈,再判断两者是否匹配。
代码:
#include<iostream>
#include<string.h>
using namespace std;
//定义栈
#define max_size 200//栈的最大容量
typedef char datatype;
typedef struct{
datatype zhan[max_size];
int top;//栈顶
}stack;
//栈的初始化
void initial(stack &st)
{
st.top = 0;
}
//类型为datatype的x入栈
void push(stack &st, datatype x)
{
//当栈顶和max_size相等时,栈满
if(st.top == max_size){
// cout<<"This stack has already full!";
cout<<"no";
exit(0);
}else{
st.zhan[st.top] = x;
st.top++;
}
}
//出栈
char pop(stack &st){
if(st.top == 0){
// cout<<"This stack is empty!";
cout<<"no";
exit(0);
}else{
st.top--;
return st.zhan[st.top];
}
}
int main(){
stack s;
initial(s);
/*输入字符串,并将字符串放到字符数组中,
实现能够逐个扫描字符串中的字符,并且不跳过空格符
*/
string str;
getline(cin, str);
char ch[200]={'\0'};
strcpy(ch,str.c_str());
//flag标志状态 1为括号匹配,0为不匹配
int flag=1;
int i;
for(i=0; ch[i]!='\0'; i++){
//元素若为{,(,[则入栈
if((ch[i] == '{' )|| (ch[i] =='[') || (ch[i] =='(')){
push(s, ch[i]);
}//元素若为},),]则出栈 赋值给a
else if((ch[i] == '}') || (ch[i] ==']') || (ch[i] ==')')){
char a;
a = pop(s);
//若a与ch[i]匹配,进行下一个字符扫描
if((a == '{' && ch[i] == '}') || (a == '(' && ch[i] == ')') || (a == '[' && ch[i] == ']')){
continue;
}else flag = 0;
}
}
if(s.top != 0){ //当左括号多出没有与右括号匹配的时候(如:" {() ")
flag = 0
}
if(flag == 0){
cout<<"no";
}else cout<<"yes";
return 0;
}
编程过程中遇到的问题: 1. 在对字符串进行入栈操作时s.top(栈顶)的数值不增加,总为1 错误代码如下:
运行结果如下:
这段代码对于初学者来说看上去逻辑和操作过程似乎都没有问题,同时也困扰了我许久, 在参考了《数据结构(c语言版)》李云清等编著的教程后,我发现我犯了一个致命的低级错误: 编程push函数的时候,传入的参数为 stack st ,是不具有返回的功能,也就意味着在 push 函数中对于 st.top++ 这个操作没有更改主函数中st.top的数值。 修改代码如下: 将传入的参数为 stack st 改为 => 传入的参数为 stack &st, 当然,将它写成具有返回值的函数或者传入指针也是可行的。
2. 字符串入栈时,每个字符都入栈,没有通过是否为左括号(即" ( 、[ 、{ ")的判断 错误代码如下:
运行结果如下: 此运行结果为debug时设置的多点输出,数字均为 s.top ,加个a只是区分两个地方...
这样看我们的push函数!又似乎没有什么问题对不对! 但实际上if里面的语句是有问题的,受到多年数学的影响,判断是否为左括号,不能写成 " ch[i] == '{' || '[' || '(' " , 而需要修改为: " (ch[i] == '{' )|| (ch[i] =='[') || (ch[i] =='(') " 修改后代码: 那么另一个低级错误也就告一段落了... 可见基础中的基础的重要性啊!
3. 运行pop函数时,没有字符的返回 错误代码如下:
运行结果如下: 第一个数字1为调用push后的flag , 第二个数字0为调用push和pop后的flag
从运行结果我们可以看到,理应出栈的 " ) " 和 " } "都是没有正常显示出来的, 也就是没有正常的返回给错误代码中的 datatype x 。 一开始我以为是在 函数传入形参的时候,利用引用值返回x 的这种方法并不行,于是我又将它改写成利用含有返回值函数返回我们需要的 x 这种方法(如上图错误代码所示) 但是结果都是一模一样的,这时候我就揪着这个函数看,很明显的,既然错误不在传入传出的参数中那么只能出现在if{....} 或 else{...}的语句中(显而易见,是在else{...}中) bug也很容易看出来了,毕竟也就只有两句。 修改代码如下: 其实改完回来再看的时候也觉得很无语,第一个入栈的字符(有且只有一个入栈)是在 st.zhan[ 0 ] 中存放的, 而再错误代码中我首先pop出来的却是 st.zhan[ 1 ] ,并没有这个字符,程序当然会出错啦。
总结: 在这种调用多个函数的这种题目中,debug 可能是最考验人意志力的一步了 最后再强调一遍: 基础真的很重要!!! && 如有不正确的地方或有值得改进的地方,希望各位大佬指点一下。 :)
转载于:https://www.cnblogs.com/yi2105/p/10604850.html