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

admin2019-08-01  42

问题 设计一个算法,判断一个算术表达式中的括号是否配对。算术表达式保存在带头结点的单循环链表中,每个结点有两个域: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’(’:push(s,p一>ch);break; case’)’:if(StackEmpty(s)IIStackGetTop(s)!=’(’){ printf(”括号不配对\n”);retum(0): } else pop(S); break; case’[’:push(s,p->ch);break; case’[’:if(StackEmpty(s)|| StackGetTop(s)!=l[’){ printf(”括号不配对\n”);return(0); } else pop(S); breaki 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/I8Ci777K
0

最新回复(0)