设计算法判断一个算术表达式的圆括号是否配对

#includestdio.h#includestdlib.htypedefstructnode{charch;node*next;}Linkstack;Linkstack*Setstack(){//创建空链栈Linkstack*S;S=(Linkstack*)malloc(sizeof(Linkstack));S-next=NULL;returnS;}Linkstack*Pushstack(Linkstack*S,charc){//入栈Linkstack*p;p=(Linkstack*)malloc(sizeof(Linkstack));p-ch=c;p-next=S-next;S-next=p;returnS;}Linkstack*Popstack(Linkstack*S){//出栈Linkstack*p;p=S-next;S-next=p-next;free(p);returnS;}charGettop(Linkstack*S){//取栈顶数据if(S-next!=NULL)returnS-next-ch;elsereturn'';}intJudgepair(){//判断圆括号是否正确配对Linkstack*p;charc;intsign=1;p=Setstack();printf(请输入算术表达式，并以'#'结束!\n);c=getchar();while(c!='#'){switch(c){case'('://扫描到'('入栈p=Pushstack(p,c);break;case')'://扫描到')'，判断栈顶是否是'('if(Gettop(p)=='(')//若栈顶是'(',则出栈p=Popstack(p);else//若栈顶不是'(',则配对错误sign=0;break;}if(sign==0)break;elsec=getchar();}if(p-next!=NULL)//最后查看栈中是否为空sign=0;returnsign;}voidJudgeout(inta){//判断结果输出if(a==1)printf(算术表达式圆括号配对正确!\n);if(a==0)printf(算术表达式圆括号配对错误!\n);}voidmain(){Judgeout(Judgepair());}实验题目：设计算法判断一个算术表达式的圆括号是否配对。问题分析：本程序要求实现判断一个算术表达式的圆括号配对是否正确，为满足上述功能，需要解决的关键问题是对左右括号的存储过程及判断配对正确与否过程。概要设计：①选择链栈对需要存储的字符进行存储。②扫描一个算术表达式进行时，遇到左括号时将其入栈。遇到右括号时，查看栈顶字符，若为左括号则继续扫描，否则结束扫描。遇到其他字符时，不做任何操作，继续扫描。详细设计：①输入一个算术表达式后，sign置1，并依次逐个扫描表达式字符。当扫描遇到左括号时，将其存入链栈中。当扫描遇到右括号时，取链栈中栈顶字符查看，若栈顶字符不是左括号，sign置0,则结束扫描（即该表达式圆括号配对不正确）；若栈顶字符是左括号，则将栈顶字符出栈，并继续扫描。当扫描遇到其他字符时，不做任何操作，继续下个字符扫描。②当扫描结束后，返回sign的值。sign为0时，即表达式圆括号配对错误。sign为1时，即表达式圆括号配对正确。调试分析及小结：错误：当输入（（2+3）+(1+2）））#后，程序不能执行。错误取栈顶函数代码：charGettop(Linkstack*S){//取栈顶数据returnS-next-ch;}错误分析：程序中对算术表达式扫描时，当扫描到右括号时，需要取字符链栈中栈顶字符进行查看，即需要调用取栈顶字符函数（该函数返回结点中的字符）。在扫描过两个左括号和右括号后，又扫描到右括号时，即需执行上述操作。而此时链栈为空，设计的函数（函数代码如上）在此情况下并不能返回一个字符，因此导致无法顺利执行程序。改正：当链栈为时，返回一个空格。代码如下：charGettop(Linkstack*S){//取栈顶数据if(S-next!=NULL)returnS-next-ch;elsereturn'';}小结：通过本次实验，意识到了标识符的重要性，恰当地设置标识符，可以减少许多不必要的运算，同时也提高了程序时间性能。