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

1、#include#includetypedef struct nodechar ch;node *next;Linkstack;Linkstack *Setstack() /创建空链栈Linkstack *S;S=(Linkstack *)malloc(sizeof(Linkstack);S-next=NULL;return S;Linkstack *Pushstack(Linkstack *S,char c) /入栈Linkstack *p;p=(Linkstack *)malloc(sizeof(Linkstack);p-ch=c;p-next=S-next;S-next=p;return

2、 S;Linkstack *Popstack(Linkstack *S) /出栈Linkstack *p;p=S-next;S-next=p-next;free(p);return S;char Gettop(Linkstack *S) /取栈顶数据if(S-next!=NULL)return S-next-ch;elsereturn ;int Judgepair( ) /判断圆括号是否正确配对Linkstack *p;char c;int sign=1;p=Setstack();printf(请输入算术表达式，并以#结束!n);c=getchar();while(c!=#) switch(c

3、)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;return sign;void Judgeout(int a) /判断结果输出if(a=1)printf(算术表达式圆括号配对正确!n);if(a=0)printf(算术表达式圆括号配对错误!n);voi

4、d main()Judgeout(Judgepair();实验题目：设计算法判断一个算术表达式的圆括号是否配对。问题分析：本程序要求实现判断一个算术表达式的圆括号配对是否正确，为满足上述功能，需要解决的关键问题是对左右括号的存储过程及判断配对正确与否过程。概要设计：选择链栈对需要存储的字符进行存储。扫描一个算术表达式进行时，遇到左括号时将其入栈。遇到右括号时，查看栈顶字符，若为左括号则继续扫描，否则结束扫描。遇到其他字符时，不做任何操作，继续扫描。详细设计：输入一个算术表达式后，sign置1，并依次逐个扫描表达式字符。当扫描遇到左括号时，将其存入链栈中。当扫描遇到右括号时，取链栈中栈顶字符查看

5、，若栈顶字符不是左括号，sign置0,则结束扫描（即该表达式圆括号配对不正确）；若栈顶字符是左括号，则将栈顶字符出栈，并继续扫描。当扫描遇到其他字符时，不做任何操作，继续下个字符扫描。当扫描结束后，返回sign的值。sign为0时，即表达式圆括号配对错误。sign为1时，即表达式圆括号配对正确。调试分析及小结：错误：当输入（2+3）+(1+2）# 后，程序不能执行。 错误取栈顶函数代码： char Gettop(Linkstack *S) /取栈顶数据 return S-next-ch; 错误分析：程序中对算术表达式扫描时，当扫描到右括号时，需要取字符链栈中栈顶字符进行查看，即需要调用取栈顶字符函数（该函数返回结点中的字符）。在扫描过两个左括号和右括号后，又扫描到右括号时，即需执行上述操作。而此时链栈为空，设计的函数（函数代码如上）在此情况下并不能返回一个字符，因此导致无法顺利执行程序。改正：当链栈为时，返回一个空格。代码如下： char Gettop(Linkstack *S) /取栈顶数据 if(S-next!=NULL) r