设计一个算法,判断一个算术表达式中的括号是否配对。算术表达式保存在带头结点的单循环链表中,每个结点有两个域:ch和link,其中ch域为字符类型。

admin2019-08-01  33

问题 设计一个算法,判断一个算术表达式中的括号是否配对。算术表达式保存在带头结点的单循环链表中,每个结点有两个域:ch和link,其中ch域为字符类型。

选项

答案表达式中的括号有以下三对:‘(‘、’)’、‘[‘、’]’、‘{‘、’}’,使用栈,当为左括号时入栈,右括号时,若栈顶是其对应的左括号,则退栈,若不是其对应的左括号,则结论为括号不配对。当表达式结束,若栈为空,则结论表达式括号配对:否则,结论表达式括号不配对。 int Match(LinkedList la){ //算术表达式存储在以la为头结点的单循环链表中,本算法判断括号是否正确配对 char s[]; //s为字符栈,容量足够大 p=la一>link; //p为工作指针,指向待处理结点 stack Init(s); //初始化栈s while(p!=la){ //循环到头结点为止 switch(p一>ch){ case‘(’:pLish(s,p一>ch);break; case‘)’:if(StackEmpry(s)||StackGetTop(s)!=‘(’){ printf(”括号不配对\n”);return(0); } else pop(s); break; case‘[’:push(S,p->ch);break; case‘[’:if(StackEmpty(s)llStackGetTop(S)!=‘[’){ printf(“括号不配对\n”);retum(0); } else pop(s); break; case‘{’:push(s,p->ch); break; case‘}’:if(StackEmpty(s)||StackGetTop(S)!=‘{’){ printf(“括号不配对\n”);retum(0); } else pop(s); break; } p=p一>link;//后移指针 }//while if(StackEmpty(s)){ printf(“括号配对\n”);return(1); } else{ printf(“括号不配对\n”);return(0); } } 提示:算法中对非括号的字符未加讨论。遇到右括号时,若栈空或栈顶元素不是其对应的左圆(方、花)括号,则结论括号不配对,退出运行。最后,若栈不空,结论仍是括号不配对。

解析
转载请注明原文地址:https://kaotiyun.com/show/ftCi777K
0

相关试题推荐
最新回复(0)