数据结构算术表达式求值

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

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

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

4、 栈为空栈的时候，返回 ERROR printf( 运算符栈为空 !n); return ERROR;elsee=*; /栈不为空的时候用e做返回值，删除S的栈顶元素，并返回return OK;int StackTraverse(SqStack &s) / 运算符栈的遍历char *t;t= ;if =printf( 运算符栈为空 !n); / 栈为空栈的时候返回 ERROR return ERROR;while(t!=printf( %c,*t); /栈不为空的时候依次取出栈内元素t+;return ERROR;OK2)数字栈部分： struct SqStackn / int *base;

5、/ int *top; / int stacksize; /;定义数栈栈底指针栈顶指针栈的长度int InitStackn (SqStackn &s) /建立一个空栈 S=(int*)malloc(50*sizeof(int); if(!exit(OVERFLOW); / 存储分配失败一 J=50;return OK; int GetTopn(SqStackn s,int &e) /数栈取栈顶元素if =printf( 运算数栈为空 !n); / 栈为空的时候返回 ERROR return ERROR;elsee=*; / 栈不为空的时候，用 e 作返回值，返回 S 的栈顶元素，并返回 OK

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

7、删除 S的栈顶元素，用e返回其值，并返回return OK;int StackTraversen(SqStackn &s) / 数栈遍历int *t;t=;if =printf( 运算数栈为空!n); /栈为空栈的时候返回 ERRORreturn ERROR;while(t!=printf( %d,*t); /栈不为空的时候依次输出t+；return ERROR;五、算法及时间复杂度1算法:建立两个不同类型的空栈，先把一个# 压入运算符栈。输入一个算术表达式的字符串(以 #结束)，从第一个字符依次向后读，把读 取的数字放入数字栈，运算符放入运算符栈。判断新读取的运算符和运算 符栈顶得运算符号的

8、优先级，以便确定是运算还是把运算符压入运算符 栈。最后两个 #遇到一起则运算结束。数字栈顶的数字就是要求的结 果。2、时间复杂度：0(n)数据压缩存储栈，其操作主要有：建立栈 int Push(SeqStack *S, char x)入栈 int Pop(SeqStack *S, char x)出栈。以上各操作运算的平均时间复杂度为0(n),其主要时间是耗费在输入操作。六、测试用例如图所示运舁付悅为:A *运算数役为:2运算符役为; 崔韶娥为i2 34运算符栈为:II + * 运算数栈为:2 34运算符栈为;tt + * -运算数栈为:2 34 6运算符栈为:运算数桂为:2 a4 G 4 理為

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

10、#include #include #include #include #define OK 1#define ERROR 0#define STACK_INIT_SIZE 100/#define STACKINCREMENT 10 /=/ 以下定义两种栈，分别存放运算符和数字/=/*运算符栈部分 *struct SqStack /char *base; / char *top; / int stacksize; /定义栈栈底指针栈顶指针栈的长度int InitStack (SqStack &s) / 建立一个空栈 S if (! = (char *)malloc(50 * sizeof(ch

11、ar) exit(0);一 J=50; return OK;运算符取栈顶元素char GetTop(SqStack s,char &e) /if = / 栈为空的时候返回 ERROR printf( 运算符栈为空 !n); return ERROR; elsee=*; /return 0K;栈不为空的时候用e做返回值，返回S的栈顶元素，并返回0Kint Push(SqStack &s,char e) / 运算符入栈 if = printf( 运算符栈满 !n);=(char*)realloc ,+5)*sizeof(char) ); / 栈满的时候，追加 5 个存 储空间if(! exit (

12、OVERFLOW);=+;+=5;*+=e; / 把 e 入栈return OK;int Pop(SqStack &s,char &e) / 运算符出栈if = / 栈为空栈的时候，返回 ERRORprintf( 运算符栈为空 !n);return ERROR; elsee=*; /栈不为空的时候用e做返回值，删除S的栈顶元素，并返回0K return OK;运算符栈的遍历int StackTraverse(SqStack &s) / char *t;t= ;if =printf( 运算符栈为空 !n); / 栈为空栈的时候返回 ERROR return ERROR; while(t!=pri

13、ntf( %c,*t); / 栈不为空的时候依次取出栈内元素 t+; return ERROR;数字栈部分*struct SqStackn / 定义数栈int *base; /栈底指针int *top; /栈顶指针int stacksize; / 栈的长度 ;int InitStackn (SqStackn &s) / 建立一个空栈 S =(int*)malloc(50*sizeof(int); if(!exit(OVERFLOW); / 存储分配失败一 J=50; return OK;int GetTopn(SqStackn s,int &e) / 数栈取栈顶元素if =printf（ 运算

14、数栈为空 !n）; / 栈为空的时候返回 ERROR return ERROR;elsee=*; / 栈不为空的时候，用 e 作返回值，返回 S 的栈顶元素，并返回 OK return OK;int Pushn(SqStackn &s,int e) / 数栈入栈if =printf( 运算数栈满 !n); / 栈满的时候，追加 5 个存储空间=(int*)realloc ,+5)*sizeof(int) );if(! exit (OVERFLOW);=+; / 插入元素 e 为新的栈顶元素+=5;*+=e; / 栈顶指针变化 return OK;int Popn(SqStackn &s,int

15、 &e) / 数栈出栈if =printf( 运算符栈为空 !n); / 栈为空栈的视时候，返回 ERROR return ERROR;elsee=*; /栈不空的时候，则删除S的栈顶元素，用e返回其值，并返回 OKreturn OK;int StackTraversen(SqStackn &s) / 数栈遍历int *t;t= ;if =printf( 运算数栈为空 !n); / 栈为空栈的时候返回 ERROR return ERROR;while(t!=printf( %d,*t); /栈不为空的时候依次输出t+;return ERROR;/= / 以下定义函数/= int Isopera

16、tor(char ch) / 判断是否为运算符，分别将运算符和数字进入不同的栈 switch (ch)case +:case -:case *:case /:case (:case ):case #:return 1;default:return 0;int Operate(int a, char op, int b) /运算操作int result;switch(op)case +:result=a+b;break;case -:result=a-b;casebreak;1*1.result=a*b;break;case /:result=a/b;break; return result;c

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

18、运算符不匹配 !n) ; exit(0);else if (ch2 = #)p = =;elsep=;break;return p;/=/ 以下是求值过程/=int EvaluateExpression() /参考书 p53 算法int a, b, temp, answer;char ch,op,e;char *str;int j = 0;SqStackn OPND; /OPND 为运算数字栈SqStack OPTR; /OPTR 为运算符栈InitStack(OPTR);Push(OPTR,#); /, 所以此栈底是 # ，因为运算符栈以 # 作为结束标志InitStackn(OPND);/

19、 printf(nn 按任意键开始求解 :nn);/ ch=getch();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(!Isoperator(ch)temp=temp*10 + ch

20、-0; / 将逐个读入运算数的各位转化为 十进制数ch=strj;j+;Pushn(OPND,temp);else if (Isoperator(ch) / 判断是否是运算符 , 不是运算符则进栈switch (Precede(e,ch)case : Pop(OPTR,op); / 弹出最上面两个，并运算，把结 果进栈Popn(OPND,b);Popn(OPND,a);Pushn(OPND,Operate(a,op,b); printf(nn 运算符栈为： n); StackTraverse(OPTR); printf(n 数栈为： n); StackTraversen(OPND);elseprintf( 您的输入有问题，请检查重新输入 !);exit(0);GetTop(OPTR,e); / 取出运算符栈最上面元素是否是 # /whileGetTopn(OPND,answer); / 已输出。数字栈最上面即是最终结果 return answer;/=/ 执行部分/=void ShowMenu()printf(nn);printf( n);printf( n);printf(”表达式求值系统 n);printf( n);printf( n);void Quit();void Manage()int answer;/ ShowMenu();answer=EvaluateExpr