1、 数据结构课程设计数据结构课程设计 表达式求值表达式求值 班级：班级： 学号：学号： 姓名：姓名： 指导老师：指导老师： 表达式求值表达式求值 1 1、 问题描述问题描述 要求对包含加、减、乘、除、括号运算符的任意整型表达式 进行求解。 2 2、 设计思路设计思路 这个程序的关键是对数字与运算符的判断和运算符优先级的判 断，以及出栈的运算。建立两个栈，分别存储数字与运算符，栈 1 存 运算符，栈 2 存数字。依次读取表达式的字符串，先判断是数字还是 运算符，如果是数字不能马上压入栈 2，因为可能是大于 10 的数字， 应该继续循环，如果还是数字，则利用计算保存数值，直到指到运算 符时停止，将计
2、算后的数字压入栈 2。压入运算符之前先将要压入的 与栈顶的运算符优先级相比较，如果栈顶是 （而当前不是） ， 则不需比较优先级，直接压入；如果栈顶是 （ ，当前是） ，则抵 消（弹出 （ ，指向表达式下一个字符） ；若当前的运算符优先级大 于栈顶的，则压入；若当前的运算符优先级小于栈內时，弹出栈顶的 运算符，同时弹出两组数字，经过运算符的运算后再重新压到栈内。 为了方便判断运算结束，在存储运算符之前先将#压入栈 1 中， 在输入表达式时以#结束，所以可以以运算符=#并且栈 1 顶 =#来结束运算，弹出栈 2 的数值，即为表达式求值的最终结果。 上述操作的算法步骤： （1） 初始化算符 S1,数
3、字栈 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 入栈，读下一个字符=w；转（3） 。否则：从算符栈中出栈，并 从数字栈中弹出两组数字
4、进行运算， 将结果重新压入数字栈， 转 （3） 。 3 3、 数据结构设计数据结构设计 前面提到，要用栈存储数据，由于一个数字一个运算符，所以要 定义两个不同的栈，栈 1 的运算符为字符型；栈 2 的数字为浮点型， 以便运算大数字。 再给存储的数据个数加个上制。 具体结构定义如下： #define MAXSIZE 100 typedef struct char dataMAXSIZE; /*字符型，存储运算符*/ int top; charSeqStack,*charPSeqStack; typedef struct double dataMAXSIZE; /*浮点型，存储数字*/ int t
5、op; SeqStack,*PSeqStack; 4 4、 功能函数设计功能函数设计 （1）判断操作数的函数 isnum() 判断当前所指字符是否属于数字，是就返回1 ，不是返回0 。 （2）求运算符优先级函数 priority() 为了方便判断运算符优先级， 先利用 switch 函数将不同的运算符 返回不同的整型数字，再根据数字的大小判断优先级。 + 、 -优 先级相同，返回相同数字， * 、 /也是。 （3）表达式求值函数 infix_value() 此函数是直接按照设计思路完成问题要求的函数，其中要调用到 判断操作符的函数 isnum()和求运算符优先级的函数 priority()。
6、循 环结束弹出栈 2 的数值，并返回。 （4） 主函数 main() 定义一个数组存储表达式整个字符串，将返回的数值直接赋到浮 点型的 result，输出 result。 （5） 两个栈的函数设计： 栈的初始化函数 charInit_SeqStack() Init_SeqStack() 判栈空 Empty_SeqStack() charEmpty_SeqStack() 入栈函数 Push_SeqStack() charPush_SeqStack() 出栈函数 Pop_SeqStack() charPop_SeqStack() 取栈顶函数 GetTop_SeqStack() charGetTop_SeqStack() 销毁栈 Destroy_SeqStack() charDestroy_SeqStack() 5 5、 程序代码程序代码 #includ
