《数据结构》课程设计 利用栈求表达式的值 班级： 2 学号： 100171021330 姓名： 吴迪 指导老师： 王方 利用栈求表达式的值 1、 设计思路 这个程序的关键是对数字与运算符的判断和运算符优先级的判断，以及出栈的运算。建立两个栈，分别存储数字与运算符，栈1 存运算符，栈2 存数字。依次读取表达式的字符串，先判断是数字还是运算符，如果是数字不能马上压入栈2，因为可能是大于10 的数字，应该继续循环，如果还是数字，则利用计算保存数值，直到指到运算符时停止，将计算后的数字压入栈2。压入运算符之前先将要压入的与栈顶的运算符优先级相比较，如果栈顶是‘（’而当前不是‘）’，则不需比较优先级，直接压入；如果栈顶是‘（’ ，当前是‘）’，则抵消（弹出‘（’ ，指向表达式下一个字符）；若当前的运算符优先级大于栈顶的，则压入；若当前的运算符优先级小于栈內时，弹出栈顶的运算符，同时弹出两组数字，经过运算符的运算后再重新压到栈内。为了方便判断运算结束，在存储运算符之前先将‘#’压入栈1 中，在输入表达式时以‚#‛结束，所以可以以运算符==‘ #’并且栈1 顶==‘ #’来结束运算，弹出栈2 的数值，即为表达式求值的最终结果。 上述操作的算法步骤： （ 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 入栈，读下一个字符=>w；转（3）。否则：从算符栈中出栈，并从数字栈中弹出两组数字进行运算，将结果重新压入数字栈，转 （ 3）。 2、 数据结构设计 前面提到，要用栈存储数据，由于一个数字一个运算符，所以要定义两个不同的栈，栈1 的运算符为字符型；栈2 的数字为浮点型，以便运算大数字。再给存储的数据个数加个上制。具体结构定义如下： #define MAXSIZE 100 typedef struct{ char data[MAXSIZE]; /*字符型，存储运算符*/ int top; }charSeqStack,*charPSeqStack; typedef struct{ double data[MAX...
VIP
