数据结构课程设计之表达式求值

《数据结构课程设计之表达式求值》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、学生课程设计题目：表达式求值问题姓名：赵旺学号：124090102042所在院(系)：计算机与信息科学学院专业：2012级计算机科学与技术班级：(2）班指导教师：冯韵2014年9月24日一．问题描述要求对包含加、减、乘、除、括号运算符的任意整型表达式进行求解。二．设计思路这个程序的关键是对数字与运算符的判断和运算符优先级的判断，以及出栈的运算。建立两个栈，分别存储数字与运算符，栈1存运算符，栈2存数字。依次读取表达式的字符串，先判断是数字还是运算符，如果是数字不能马上压入栈2，因为可能是大于10的数字，应该继续循环，如果还是数字，则利用计算保存数

2、值，直到指到运算符时停止，将计算后的数字压入栈2。压入运算符之前先将要压入的与栈顶的运算符优先级相比较，如果栈顶是‘（’而当前不是‘）’，则不需比较优先级，直接压入；如果栈顶是‘（’，当前是‘）’，则抵消（弹出‘（’，指向表达式下一个字符）；若当前的运算符优先级大于栈顶的，则压入；若当前的运算符优先级小于栈內时，弹出栈顶的运算符，同时弹出两组数字，经过运算符的运算后再重新压到栈内。为了方便判断运算结束，在存储运算符之前先将‘#’压入栈1中，在输入表达式时以“#”结束，所以可以以运算符==‘#’并且栈1顶==‘#’来结束运算，弹出栈2的数值，即为表

3、达式求值的最终结果。上述操作的算法步骤：（1）初始化算符S1,数字栈S2;，将‘#’压入算符栈S1中。（2）读表达式字符=>w。（3）当栈顶为‘#’并且w也是‘#’时结束；否则循环做下列步骤：（3-1）如果w是数字，存储到m，再经过计算存储到num中。m=w-‘0’;num=num*pow(10,n)+m;n++;读下一个字符=>w，如果是运算符，则跳出循环；转3-2。（3-2）w若是运算符，则：（3-2-1）如果栈顶为‘（’并且w为‘）’则‘（’出栈，读下一个字符=>w；转（3）。（3-2-2）如果栈顶为‘（’或者栈顶优先级小于w优先级，则w入

4、栈，读下一个字符=>w；转（3）。否则：从算符栈中出栈，并从数字栈中弹出两组数字进行运算，将结果重新压入数字栈，转（3）。2.1数据结构设计前面提到，要用栈存储数据，由于一个数字一个运算符，所以要定义两个不同的栈，栈1的运算符为字符型；栈2的数字为浮点型，以便运算大数字。再给存储的数据个数加个上制。具体结构定义如下：#defineMAXSIZE100typedefstruct{chardata[MAXSIZE];/*字符型，存储运算符*/inttop;}charSeqStack,*charPSeqStack;typedefstruct{doubl

5、edata[MAXSIZE];/*浮点型，存储数字*/inttop;}SeqStack,*PSeqStack;2.2功能函数设计（1）判断操作数的函数isnum()判断当前所指字符是否属于数字，是就返回‘1’，不是返回‘0’。（2）求运算符优先级函数priority()为了方便判断运算符优先级，先利用switch函数将不同的运算符返回不同的整型数字，再根据数字的大小判断优先级。‘+’、‘-’优先级相同，返回相同数字，‘*’、‘/’也是。（3）表达式求值函数infix_value()此函数是直接按照设计思路完成问题要求的函数，其中要调用到判断操作符

6、的函数isnum()和求运算符优先级的函数priority()。循环结束弹出栈2的数值，并返回。（1）主函数main()定义一个数组存储表达式整个字符串，将返回的数值直接赋到浮点型的result，输出result。（2）两个栈的函数设计：栈的初始化函数charInit_SeqStack()Init_SeqStack()判栈空Empty_SeqStack()charEmpty_SeqStack()入栈函数Push_SeqStack()charPush_SeqStack()出栈函数Pop_SeqStack()charPop_SeqStack()取栈顶

7、函数GetTop_SeqStack()charGetTop_SeqStack()销毁栈Destroy_SeqStack()charDestroy_SeqStack()三.程序代码#include#include#include#defineMAXSIZE100typedefstruct{doubledata[MAXSIZE];inttop;}SeqStack,*PSeqStack;typedefstruct{chardata[MAXSIZE];inttop;}charSeqStack,*cha

8、rPSeqStack;/*定义栈，两个不同的存储类型*/PSeqStackInit_SeqStack(void){PSeqStackS;