数据结构考研分类复习真题 第三章 答案[20]

[题目分析]表达式中的括号有以下三对（）[]{}使用栈当为左括号时入栈右括号时若栈顶是其对应的左括号则退栈若不是其对应的左括号则结论为括号不配对当表达式结束若栈为空则结论表达式括号配对否则结论表达式括号不配对

int Match(LinkedList la)

//算术表达式存储在以la为头结点的单循环链表中本算法判断括号是否正确配对

{char s[]; //s为字符栈容量足够大

p=la>link; //p为工作指针指向待处理结点

StackInit(s); //初始化栈s

while (p!=la) //循环到头结点为止

{switch (p>ch)

{case (:push(sp>ch); break;

case ):if(StackEmpty(s)||StackGetTop(s)!=()

{printf(括号不配对\n); return();} else pop(s);break;

case [:push(sp>ch); break;

case ]: if(StackEmpty(s)||StackGetTop(s)!=[)

{printf(括号不配对\n); return();} else pop(s);break;

case {:push(sp>ch); break;

case }: if(StackEmpty(s)||StackGetTop(s)!={)

{printf(括号不配对\n); return();} else pop(s);break;

} p=p>link; 后移指针

}//while

if (StackEmpty(s)) {printf(括号配对\n); return();}

else{printf(括号不配对\n); return();}

}//算法match结束

[算法讨论]算法中对非括号的字符未加讨论遇到右括号时若栈空或栈顶元素不是其对应的左圆（方花）括号则结论括号不配对退出运行最后若栈不空仍结论括号不配对

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []