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

admin2019-08-01  43

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

选项

答案表达式中的括号有以下三对:’(’、’)’、’[‘、’]’、’{’、’}’,使用栈,当为左括号时入栈,右括号时,若栈顶是其对应的左括号,则退栈,若不是其对应的左括号,则结论为括号不配对。当表达式结束,若栈为空,则结论表达式括号配对;否则,结论表达式括号不配对。 int Match(LinkedList 1a){ //算术表达式存储在以la为头结点的单循环链表中,本算法判断括号是否正确配对 char s[]; //s为字符栈,容量足够大 p=la一>link; //p为工作指针,指向待处理结点 Stack Init(s); //初始化栈s while(p!=la){ //循环到头结点为止 switch(p一>ch){ case’(’:push(s,p一>ch);break; case’)’:if(StackEmpty(s)||StackGetTop(s)!=’(’){ pfintf(”括号不配对\n”);return(0); } else pop(S); break; case ’[’:push(s,p一>ch);break; case’[’:if(StackEmpty(s)||StackGetTop(s)!=’[’){ printf(”括号不配对\n”);return(0); } else pop(s); break; case’{’:push(s,P一>ch);break: case’}’:if(StackEmpty(s)||StackGetTop(s)!=’{’){ printf(”括号不配对\n”);return(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/bVCi777K
0

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