《数据结构》算术表达式求值

1、二课程设计2算术表达式求值一、需求分析二、程序的主要功能三、程序运行平台四、数据结构五、算法及时间复杂度六、测试用例七、程序源代码三感想体会与总结算术表达式求值一、需求分析一个算术表达式是由操作数（operand）、运算符（operator）和界限符 （delimiter）组成的。假设操作数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#”，如：# （ 7+15）*（23-28/4）#。引入表达式起始、结束符是为了方便。编程利用“算符 优先法”求算术表达式的值。二、程序的主要功能1）从键盘读入一个合法的算术表达式，输出正确的结果。2）显示输入序列和栈的变化过程

2、。三、程序运行平台Visual C+6.0 版本四、数据结构本程序的数据结构为栈。1）运算符栈部分：struct SqStack / 定义栈char *base; /栈底指针char *top; /栈顶指针int stacksize; / 栈的长度;int InitStack (SqStack &s)/建立一个空栈 Sif (!(s.base = (char *)malloc(50 * sizeof(char) exit(O);s.top=s.base;s.stacksize=50;return OK;char GetTop(SqStack s,char &e)/ 运算符取栈顶元素if (s.

3、top=s.base)栈为空的时候返回ERRORprintf(运算符栈为空!n);return ERROR;elsee=*(s.top-1);栈不为空的时候用e做返回值，返回S的栈顶元素，并返回 OKreturn OK;int Push(SqStack & s,char e) /运算符入栈if (s.top-s.base = s.stacksize)printf(运算符栈满!n);s.base=(char*)realloc (s.base,(s.stacksize+5)*sizeof(char) );/ 栈满的时候,追加5个存储空间if(!s.base) exit (OVERFLOW);s.t

4、op=s.base+s.stacksize;s.stacksize+=5;*(s.top)+=e;/把 e 入栈return OK;int Pop(SqStack & s,char & e) /运算符出栈if (s.top=s.base)/栈为空栈的时候，返回ERRORprintf(运算符栈为空!n);return ERROR;elseOKe=*-s.top;/栈不为空的时候用e做返回值，删除S的栈顶元素，并返回return OK;int StackTraverse(SqStack & s) / 运算符栈的遍历char *t;t=s.base ;if (s.top=s.base)printf(

5、运算符栈为空!n); 栈为空栈的时候返回ERRORreturn ERROR;while(t!=s.top)printf( %c,*t); /栈不为空的时候依次取出栈内元素t+；return ERROR;(2)数字栈部分：struct SqStackn / 定义数栈int*base;/栈底指针int*top;/栈顶指针intstacksize;栈的长度;int InitStackn (SqStackn &s)/建立一个空栈 Ss.base=(i nt*)malloc(50*sizeof(i nt); if(!s.base)exit(OVERFLOW);/ 存储分配失败s.top=s.base;s

6、.stacksize=50;return OK;int GetTop n(SqStackn s,i nt & e) /数栈取栈顶元素if (s.top=s.base)printf(运算数栈为空!n); /栈为空的时候返回 ERROR return ERROR;elsee=*(s.top-1);/栈不为空的时候，用 e作返回值，返回S的栈顶元素，并返回 0K return OK;int Push n(SqStackn &s,i nt e) /数栈入栈if (s.top-s.base =s.stacksize)printf(运算数栈满!n); /栈满的时候，追加5个存储空间s.base=(i nt

7、*)realloc (s.base,(s.stacksize+5)*sizeof(i nt); if(!s.base) exit (OVERFLOW);s.top=s.base+s.stacksize; / 插入元素 e为新的栈顶元素 s.stacksize+=5;*(s.top)+=e; /栈顶指针变化return OK;int Pop n(SqStackn & s,i nt & e) /数栈出栈if (s.top=s.base)printf(运算符栈为空!n); /栈为空栈的视时候，返回 ERRORreturn ERROR;elsee=*-s.top;栈不空的时候，则删除 S的栈顶元素，用

8、e返回其值，并返回OKreturn OK;int StackTraverse n( SqStackn & s) /数栈遍历int *t;t=s.base ;if (s.top=s.base)printf(运算数栈为空!n); /栈为空栈的时候返回 ERRORreturn ERROR;while(t!=s.top)printf(” d,*t); /栈不为空的时候依次输出t+；return ERROR;五、算法及时间复杂度1、算法：建立两个不同类型的空栈，先把一个妊入运算符栈。输入一个算术表达式的字符串(以结束)，从第一个字符依次向后读，把读取的数 字放入数字栈，运算符放入运算符栈。判断新读取的运

9、算符和运算符栈顶 得运算符号的优先级，以便确定是运算还是把运算符压入运算符栈。最后 两个遇到一起则运算结束。数字栈顶的数字就是要求的结果。2、时间复杂度：0(n)数据压缩存储栈，其操作主要有：建立栈 int Push(SeqStack *S, char x)入栈 int Pop(SeqStack *S, char x)出栈。以上各操作运算的平均时间复杂度为0(n),其主要时间是耗费在输入操作。六、测试用例如图所示。血-|口| X运算数栈为:2运算符栈为: 柱豊嘉栈为:2 34运算符栈为; + * 运算数栈为:2 34运算符栈为| 运算数栈为;2 34 6运算符栈为|# + -* 运算数桟为I

10、2 34 6 4最终结果如图所示:按N#n七、源代码/*第七题算术表达式求值问题描述一个算术表达式是由操作数（operand）、运算符（operator）和界限符（delimiter）组成的 假设操作数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“ #如：#（7+15）*（23-28/4）#。引入表达式起始、结束符是为了方便。编程利用 算符优先法”求算术表达式的值。基本要求（1）从键盘读入一个合法的算术表达式，输出正确的结果。（2）显示输入序列和栈的变化过程。*/#i nclude #i nclude #i nclude #in elude #in elude

11、 vconi o.h#in elude #defi ne OK 1#defi ne ERROR 0#defi ne STACK_INIT_SIZE 100#defi ne STACKINCREMENT 10/=/以下定义两种栈，分别存放运算符和数字/=运算符栈部分*struct SqStack/ 定义栈char *base;栈底指针char *top; 栈顶指针int stacksize;栈的长度;int InitStack (SqStack &s)建立一个空栈 Sif (!(s.base = (char *)malloc(50 * sizeof(char)exit(O);s.top=s.ba

12、se;s.stacksize=50;return OK;char GetTop(SqStack s,char &e)/ 运算符取栈顶元素if (s.top=s.base)栈为空的时候返回ERRORprintf(运算符栈为空!n);return ERROR;elsee=*(s.top-1);栈不为空的时候用e做返回值，返回S的栈顶元素，并返回OKreturn OK;int Push(SqStack &s,char e) / 运算符入栈if (s.top-s.base = s.stacksize)printf(运算符栈满!n);s.base=(char*)realloc (s.base,(s.st

13、acksize+5)*sizeof(char) );/ 栈满的时候，追加5个存储空间if(!s.base) exit (OVERFLOW);s.top=s.base+s.stacksize;s.stacksize+=5;*(s.top)+=e;/把 e 入栈return OK;int Pop(SqStack &s,char &e) / 运算符出栈if (s.top=s.base)栈为空栈的时候，返回 ERRORprintf(运算符栈为空!n);return ERROR;elsee=*-s.top;栈不为空的时候用e做返回值，删除S的栈顶元素，并返回OKreturn OK;int StackTr

14、averse(SqStack & s) / 运算符栈的遍历char *t;t=s.base ;if (s.top=s.base)printf(运算符栈为空!n);/栈为空栈的时候返回ERRORreturn ERROR;while(t!=s.top)printf( %c,*t); /栈不为空的时候依次取出栈内元素t+； return ERROR;数字栈部分*struct SqStackn / 定义数栈int *base; 栈底指针int *top;栈顶指针int stacksize;栈的长度;int InitStackn (SqStackn &s)建立一个空栈 Ss.base=(i nt*)ma

15、lloc(50*sizeof(i nt); if(!s.base)exit(OVERFLOW);存储分配失败s.top=s.base;s.stacksize=50;return OK; int GetTopn(SqStackn s,int &e) / 数栈取栈顶元素if (s.top=s.base)printf(运算数栈为空!n); /栈为空的时候返回ERROR return ERROR;elsee=*(s.top-1); /栈不为空的时候，用e作返回值，返回S的栈顶元素，并返回OKreturn OK;int Pushn(SqStackn &s,int e) / 数栈入栈if (s.top-s

16、.base =s.stacksize)printf(运算数栈满!n); /栈满的时候，追加5个存储空间s.base=(int*)realloc (s.base,(s.stacksize+5)*sizeof(int); if(!s.base) exit (OVERFLOW);s.top=s.base+s.stacksize; /插入元素e为新的栈顶元素 s.stacksize+=5;*(s.top)+=e; /栈顶指针变化return OK;int Popn(SqStackn &s,int &e) / 数栈出栈if (s.top=s.base)printf(运算符栈为空!n); /栈为空栈的视时

17、候，返回ERRORreturn ERROR; elsee=*-s.top;栈不空的时候，则删除S的栈顶元素，用e返回其值，并返回OKreturn OK;int StackTraverse n(SqStackn & s) / 数栈遍历int *t;t=s.base ;if (s.top=s.base)printf(运算数栈为空!n); /栈为空栈的时候返回ERRORreturn ERROR;while(t!=s.top)printf( %d,*t); /栈不为空的时候依次输出 t+;return ERROR;/=/以下定义函数/= int lsoperator(char ch)/判断是否为运算符

18、，分别将运算符和数字进入不同的栈switch (ch)case +:case -:case *:case /:case (:case ):case #:return 1;default:return 0; int Operate(i nt a, char op, int b) / 运算操作 int result;switch(op)case +:result=a+b; break;case -:result=a-b; break;case *: result=a*b; break;case /:result=a/b; break;return result;char Precede(char

19、chi, char ch2) / 运算符优先级的比较 char p;switch(chl)case +:case -:ch2运算符if (ch2=+|ch2=-|ch2=)|ch2=#)p = ;ch1运算符的优先级小于elsep =；break;case case /:if (ch2 =() p =； break;case (:if (ch2 =)p =；else if (ch2 = #)printf(表达式错误！运算符不匹配!n); exit(0);elsep =;break ;case #:if (ch2 =)printf(表达式错误！运算符不匹配!n); exit(0);else if

20、 (ch2 = #)p =；elsep=;break;return p;/=/以下是求值过程/= int EvaluateExpression()/参考书 p53 算法 3.4int a, b, temp, an swer;char ch,op,e;char *str;int j = 0;SqStackn OPND;/OPND 为运算数字栈SqStack OPTR;/OPTR 为运算符栈In itStack(OPTR);Push(OPTR,#);/,所以此栈底是#，因为运算符栈以#作为结束标志In itStack n(OPND);/ printf(nn按任意键开始求解:nn);/ ch=get

21、ch();printf(n请输入表达式并以#结束:n);str =(char*)malloc(50*sizeof(char);gets(str);ch=strj; /ch是字符型的，而e是整型的整数 j+;GetTop(OPTR,e); /e为栈顶元素返回值while (ch!=# | e!=#)if (!Isoperator(ch)遇到数字，转换成十进制并计算temp=ch-0;/将字符转换为十进制数ch=strj;j+；while(!lsoperator(ch)temp=temp*10 + ch-O;II将逐个读入运算数的各位转化为十进制数ch=strj;j+；Push n(OPND,te

22、mp);else if (Isoperator(ch)判断是否是运算符，不是运算符则进栈switch (Precede(e,ch)case : Pop(OPTR,op);/弹出最上面两个，并运算，把结果进栈Pop n( OPND,b);Pop n(OPND,a);Push n(OPND,Operate(a,op,b); printf(nn 运算符栈为：n); StackTraverse(OPTR); printf(n 数栈为：n);StackTraverse n(OPND);elseprintf(您的输入有问题，请检查重新输入！)；exit(0); /whileGetTop n(OPND,a

23、nswer);/已输出。数字栈最上面即是最终结果retur n an swer;/=/执行部分/= void ShowMe nu() prin tf(nn);printf(Uh);printf(表达式求值系统);printf();printf(void Quit();void Man age() int an swer;/ ShowMe nu();an swer=EvaluateExpressi on();printf(nn 表达式结果是:%dn,answer);Quit();void Quit()char ch;prin tf(本次运算结束。n);printf(继续本系统吗？ nn);pri

24、ntf(继续运算请按 Y/y ); printf(n退出程序请按N/n );printf(n.n);ch=getch();ch=toupper(ch);将ch字符转换成大写字母if(ch = N)printf(nn 系统退出。n); exit(O);Man age();int mai n()ShowMe nu();Man age();return 0;感想体会与总结好的算法+编程技巧+高效率=好的程序。1做什么都需要耐心，做设计写程序更需要耐心。一开始的时候， 我写函数写的很快，可是等最后调试的时候发现错误很隐蔽，就很费时间 了。后来我先在纸上构思出函数的功能和参数，考虑好接口之后才动手 编，

25、这样就比较容易成功了。2、做任何事情我决定都应该有个总体规划。之后的工作按照规划逐 步展开完成。对于一个完整的程序设计，首先需要总体规划写程序的步 骤，分块写分函数写，然后写完一部分马上纠错调试。而不是像我第一个 程序，一口气写完，然后再花几倍的时间调试。一步步来，走好一步再走 下一步。写程序是这样，做项目是这样，过我们的生活更是应该这样。3、感觉一开始设计结构写函数体现的是数据结构的思想，后面的调 试则更加体现了人的综合素质，专业知识、坚定耐心、锲而不舍，真的缺 一不可啊。4、通过这次课设，不仅仅复习了 C语言相关知识、巩固了数据结构 关于栈和排序的算法等知识，更磨练了我的意志。古希腊哲学大师亚里士多德说：人有两种，一种即 吃饭是为了活着”一种是 活着是为了吃饭”一个人之所以伟大，首先是因为他有超于常人的心。志当存高远”风物长宜放眼量”这些古语皆鼓舞人们要树立雄无数个自己，万千种模样，万千愫情