资源描述：
《数据结构实验二.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、1.数据结构设计任何一个表达式都是由操作符，运算符和界限符组成的。我们分别用顺序栈来寄存表达式的操作数和运算符。栈是限定于紧仅在表尾进行插入或删除操作的线性表。顺序栈的存储结构是利用一组连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置，base为栈底指针，在顺序栈中，它始终指向栈底，即top=base可作为栈空的标记，每当插入新的栈顶元素时，指针top增1，删除栈顶元素时，指针top减1。2.算法设计为了实现算符优先算法。可以使用两个工作栈。一个称为OP
2、TR，用以寄存运算符，另一个称做OPND，用以寄存操作数或运算结果。 （1）首先置操作数栈为空栈，表达式起始符”#”为运算符栈的栈底元素； （2）依次读入表达式，若是操作符即进OPND栈，若是运算符则和OPTR栈的栈顶运算符比较优先权后作相应的操作，直至整个表达式求值完毕算术表达式求值【问题描述】由输入的四则算术表达式字符串，动态生成算术表达式所对应的后缀式，通过后缀式求值并输出。【实验要求】设计十进制整数四则运算计算器。（1）采用顺序栈等数据结构。可以将数据存储在顺序表中。（2）给定表达式字符串
3、，后缀表达式。（3）对后缀表达式求值并输出。#include#include#include#include#defineSTACK_INIT_SIZE100;typedefstruct{int*base;int*top;intstacksize;}SqStack;SqStackOPND,OPTR;//运算数栈,运算符栈charprecede(charth,charc)//优先级{if(th=='+'
4、
5、th=='-')if
6、(c=='+'
7、
8、c=='-'
9、
10、c==')'
11、
12、c=='#')return('>');elsereturn('<');if(th=='*'
13、
14、th=='/')if(c=='(')return('<');elsereturn('>');if(th=='(')if(c==')')return('=');elsereturn('<');if(th==')')return('>');if(th=='#')if(c=='#')return('=');elsereturn('<');}intOperate(
15、inta,charoptr,intb)//运算{if(optr=='+')return(a+b);if(optr=='-')return(a-b);if(optr=='*')return(a*b);if(optr=='/')return(a/b);}intresult(){printf("请输入表达式，以#结束:");OPTR.base=(int*)malloc(100*sizeof(char));OPTR.top=OPTR.base;OPTR.stacksize=STACK_INIT_SIZE;
16、*OPTR.top++='#';OPND.base=(int*)malloc(100*sizeof(int));OPND.top=OPND.base;OPND.stacksize=STACK_INIT_SIZE;charabc,optr,c;inta,l=0,i=0,j=0,k=0,b,d=0;intab[10];c=getchar();abc='#';while(c!='#'
17、
18、*(OPTR.top-1)!='#'){if(c>=48&&c<=57){ab[i]=c-48;i++;abc=c;c
19、=getchar();}else{if(abc=='0'
20、
21、abc=='1'
22、
23、abc=='2'
24、
25、abc=='3'
26、
27、abc=='4'
28、
29、abc=='5'
30、
31、abc=='6'
32、
33、abc=='7'
34、
35、abc=='8'
36、
37、abc=='9'){for(k=i-1;k>=0;k--)d=d+ab[k]*pow(10,i-k-1);*OPND.top++=d;i=0;d=0;}switch(precede(*(OPTR.top-1),c)){case'<':*OPTR.top++=c;abc=c;c=ge
38、tchar();break;case'=':OPTR.top--;abc=c;c=getchar();break;case'>':optr=*--OPTR.top;abc=c;b=*--OPND.top;a=*--OPND.top;*OPND.top++=Operate(a,optr,b);break;}}}printf("计算结果为：");return*(OPND.top-1);}voidmain(){printf("%d",result());}
