资源描述:
《判别括号匹配.doc》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、判别括号匹配一.问题描述一个算术表达式含圆括号、中括号、花括号,且它们可任意嵌套使用。写一程序,判断任一算术表达式中所含括号是否正确配对。(1)表达式从键盘输入。(2)利用栈求解此问题。(3)测试用例自己设计。二.设计本实验需要用堆栈进行解决。首先建立堆栈typedefstruct{Charstack[M];inttop;}SeqStack;//定义seqstack堆栈结构体实验中也同时用到了堆栈的各种基本操作。初始化堆栈voidStackinit(SeqStack*s){s->top=0;}进栈intSt
2、ackpush(SeqStack*s,charx){if(s->top>=maxsize){cout<<"堆栈已满无法插入!";return0;}else{s->stack[s->top]=x;s->top++;return1;}}出栈intStackpop(SeqStack*s,char*x){if(s->top<=0){cout<<"堆栈已空无数据出栈!";return0;}else{s->top--;*x=s->stack[s->top];return1;}}判断堆栈是否为空intStackn
3、otempty(SeqStacks){if(s.top<=0)return0;elsereturn1;}取栈顶元素intStacktop(SeqStacks,char*x){if(s.top<=0){cout<<"堆栈为空!";return0;}else{*x=s.stack[s.top-1];return1;}}判断函数;voidtestcorrect(chara[],intn){SeqStackmystack;inti;charc;intcount=0;Stackinit(&mystack);//初
4、始化堆栈for(i=0;i<=n;i++){if((a[i]=='(')
5、
6、(a[i]=='[')
7、
8、(a[i]=='{'))Stackpush(&mystack,a[i]);//若果是前括弧,进栈elseif(a[i]==')'&&Stacknotempty(mystack)&&Stacktop(mystack,&c)&&c=='(')Stackpop(&mystack,&c);//a[i]为")"栈顶为"("时出栈elseif(a[i]==')'&&Stacknotempty(mystack)&&Sta
9、cktop(mystack,&c)&&c!='('){cout<<"左右括弧配对不正确!";return;}//当a[i]与栈顶括弧不匹配,输出错误提示elseif(a[i]==']'&&Stacknotempty(mystack)&&Stacktop(mystack,&c)&&c=='[')Stackpop(&mystack,&c);//a[i]为"]"栈顶为"["时出栈elseif(a[i]==']'&&Stacknotempty(mystack)&&Stacktop(mystack,&c)&&c!
10、='['){cout<<"左右括弧配对不正确!";return;}//当a[i]与栈顶括弧不匹配,输出错误提示elseif(a[i]=='}'&&Stacknotempty(mystack)&&Stacktop(mystack,&c)&&c=='{')Stackpop(&mystack,&c);//a[i]为"}"栈顶为"{"时出栈elseif(a[i]=='}'&&Stacknotempty(mystack)&&Stacktop(mystack,&c)&&c!='{'){cout<<"左右括弧配对不正
11、确!";return;}//当a[i]与栈顶括弧不匹配,输出错误提示elseif(((a[i]==')')
12、
13、(a[i]==']')
14、
15、a[i]=='}')&&!Stacknotempty(mystack)){cout<<"存在右括弧无左括弧匹配!";return;}//当a[i]为右括弧但栈内已无括弧时输出错误提示}if(Stacknotempty(mystack))cout<<"存在左括弧无右括弧匹配";//当i=n但栈内依旧有括弧时,输出错误提示elsecout<<"左右括弧匹配正确!
16、";}主要算法框图:三.调试为检验程序是否可行,分别输入以下括弧序列:1.{[(])}括弧配对错误1.。{[()左括弧多于右括弧2.()))右括弧多于左括弧3.{[()]}括弧配对正确经检验,程序运行正确。测试括弧序列1时,程序显示括弧匹配正确,与实际结果不符。多次试验后发现中文与英文输入法的括弧是不一样的。此问题可在输入括弧序列时避免,也可在代码中添加中英两种括弧进行匹配。四.经验和体会本次实验中,判可定义co