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

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

admin2019-08-01  71
问题 设计一个算法，判断一个算术表达式中的括号是否配对。算术表达式保存在带头结点的单循环链表中，每个结点有两个域：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
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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