《(盐城工学院大大数据结构课程设计)栈地应用表达式求值》由会员分享，可在线阅读，更多相关《(盐城工学院大大数据结构课程设计)栈地应用表达式求值（30页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程设计报告栈的应用：表达式求值的设计专 业学生姓名班级学号指导教师徐燕萍完成日期目 录1设计内容:j2设计分析2.1 系统需求分析.1系统目标：.!主体功能：.12.2系统概要设计.1系统的功能模块划分 .1系统流程图 23设计实践3.1 基本分析：33.2 中缀表达式求值.：43.3后缀表达式求值.：53.4中缀表达式转换成后缀表达式 .64测试方法4.1基本测试.74.2拓展测试.:74.3容错测试.:85程序运行效果.76设计心得.8-7附录：源代码.10栈的应用：表达式求值的设计1设计内容设计一个表达式求值的程序。该程序必须可以接受包含（，），+, *，/，%，和八（求幕运算
2、符，aAb=a b）的中缀表达式，并求出结果。 如果表达式正确，则输出表达式的结果；如果表达式非法，则输出错误 信息。2设计分析2.1系统需求分析系统目标利用栈设计一个程序，该程序能够用于表达式求值，程序将读入的 中缀表达式转换为后缀表达式，然后读取后缀表达式，输出结果。输入要求：程序从“ input.txt ”文件中读取信息，在这个文件中如 果有多个中缀表达式，则每个表达式独占一行，程序的读取操作在文件 的结尾处停止。输出要求：对于每一个表达式，将其结果放在“ output.txt ”文件 的每一行中。这些结果可能是值（精确到小数点后两位） ，也可能是错 误信息“ ERROR IN INFI
3、X NOTATION ”。主体功能能够处理以字符序列的形式输入的不含变量的实数表达式，正确处 理负数与小数，判断表达式是否语法正确（包含分母不能为零的情况）， 正确实现对算术四则混合运算表达式的求值，能够将计算中遇到的问题和结果以文件的形式予以存储。2.2系统概要设计221系统的功能模块划分1判断操作数的函数isnum()判断当前所指字符是否属于数字，是就返回1 不是就返回 0 2. 求运算符优先级函数priority。为了方便判断运算符优先级，先利用switch函数将不同的运算符返 回不同的整型数字，在根据数字的大小判断优先级。+ -优先级相同，返回数字相同，* /也是。3. 表达式求值函数
4、infix_value()此函数是直接按照设计思路完成问题要求的函数，其中要调用到判 断操作符的函数isnum()和求运算符优先级的函数priority。循环结束 弹出栈2的数值，并返回。4. 主函数main()定义一个数组存储表达式整个字符串，将返回的数值直接赋值到浮 点型的result，输出result。5两个栈的函数设计：栈的初始化函数charlnit_SeqStack()Ini t_SeqStack()栈判空Empty_SeqStack()char Empty_SeqStack()入栈函数Push_SeqStack()charPush_SeqStack()出栈函数Pop_SeqStac
5、k()charPop_SeqStack()取栈顶函数GetTop_SeqStack()charGetTop_SeqStack()销毁栈Destory_SeqStack()charDestory_SeqStack()222系统流程图1IXA4:图1系统流程图3设计实践3.1基本分析在计算机中，算术表达式的计算往往是通过使用栈来实现的。 所以, 本表达式求值程序的最主要的数据结构就是栈。 可以使用栈来存储输入 表达式的操作符和操作数。输入的表达式是由操作数和运算符以及改变运算次序的圆括号连接而成的式子。表达式求值是高级语言编译中的一个基本问题，是栈的典型应用实例。任何一个表达式都是由操作数(ope
6、rand)、运算符(operator)和界 限符(delimiter)组成的。操作数既可以是常数，也可以是被说明为变量 或常量的标识符；运算符可以分为算术运算符、关系运算符和逻辑运算 符三类；基本界限符有左右括号和表达式结束符等。3.2中缀表达式求值中缀表达式：每个二目运算符在两个运算量的中间，假设操作数是 整型常数，运算符只含加、减、乘、除等四种运算符，界限符有左右括 号和表达式起始、结束符“#” ，如：# (7+15)*(23-28/4)#。要对一个简单的算术表达式求值，首先要了解算术四则运算的规则，即：(1) 从左到右；(2) 先乘除，后加减；(3) 先括号内，后括号外。运算符和界限符可
7、统称为算符，它们构成的集合命名为OPS。根据 上述三条运算规则，在运算过程中，任意两个前后相继出现的算符B 1 和B2之间的优先关系必为下面三种关系之一：61 02 , 01的优先权高于0 2。实现算符优先算法时需要使用两个工作栈：一个称作 operator , 用以存放运算符；另一个称作 opera nd，用以存放操作数或运算的中 间结果。算法的基本过程如下：首先初始化操作数栈opera nd和运算符栈operator ,并将表达式 起始符“#”压入运算符栈；依次读入表达式中的每个字符，若是操作数则直接进入操作数栈opera nd，若是运算符，则与运算符栈 operator的栈顶运算符进行优
8、 先权比较，并做如下处理：(1) 若栈顶运算符的优先级低于刚读入的运算符，贝S让刚读入的运 算符进operator 栈；(2) 若栈顶运算符的优先级高于刚读入的运算符，则将栈顶运算符 退栈，送入B,同时将操作数栈opera nd退栈两次，得到两个操作数a、 b，对a、b进行B运算后，将运算结果作为中间结果推入 opera nd栈；(3) 若栈顶运算符的优先级与刚读入的运算符的优先级相同，说明 左右括号相遇，只需将栈顶运算符(左括号)退栈即可。 operator栈 的栈顶元素和当前读入的字符均为“ #”时，说明表达式起始符“ #”与 表达式结束符“ # ”相遇，整个表达式求解结束。int Exp
9、Evaluati on()/*读入一个简单算术表达式并计算其值。*/In itStack (&opera nd);In itStack(&operator);PushStack(&operator, #);printf( nn Please in put an expressi on (Ending with# ): )；ch=getchar();/*读入表达式中的一个字符*/while(ch!= # |GetTop(operator)!= #)if(!In(ch, OPS)/* 判断 ch 是否运算符 */ a=GetNumber(&ch);/*用ch逐个读入操作数的各位数码，并转化为十进制
10、数a */PushStack (&opera nd,a);elseswitch(Compare(GetTop(operator),ch) case vPushStack(&operator,ch);ch=getchar();break;case = :PopStack(&operator，&x);ch=getchar(); break;case :PopStack(&operator,&op);PopStack(&opera nd, & b);PopStack(&opera nd,& a);v=Execute(a,op,b);PushStack (&opera nd,v);break;v=Ge
11、tTop(opera nd);retur n(v);为了处理方便，编译程序常把中缀表达式首先转换成等价的后缀表 达式，后缀表达式的运算符在运算对象之后。在后缀表达式中，不再引 入括号，所有的计算按运算符出现的顺序，严格从左向右进行，而不用 再考虑运算规则和级别。中缀表达式“(a+b*c)-d/e ”的后缀表达式为：“ abc*+de/- ”。3.3后缀表达式求值计算一个后缀表达式，算法上比计算一个中缀表达式简单的多。这 是因为表达式中即无括号又无优先级的约束。具体做法：只使用一个对 象栈，当从左向右扫描表达式时，每遇到一个操作数就送入栈中保存， 每遇到一个运算符就从栈中取出两个操作数进行当前的
12、计算，然后把结果再入栈，直到整个表达式结束，这时送入栈顶的值就是结果。下面是后缀表达式求值的算法，在下面的算法中假设，每个表达式是合乎语法的，并且假设后缀表达式已被存入一个足够大的字符数组A中，且以 # 为结束字符，为了简化问题，限定运算数的位数仅为一 位且忽略了数字字符串与相对应的数据之间的转换问题。double calcul_exp(char *A) /*本函数返回由后缀表达式 A表示的表达式运算结果*/ SeqStarck s;ch二*A+ ; In itStack(s); while(ch!二 #) if(ch!=运算符)PushStack(s, ch);else PopStack(s
13、, &a);PopStack(s, &b); /*取出两个运算量*/switch(ch) case ch= +case ch=case ch=case ch=case ch=% : c=a%b;c=a+b; break ; c=a-b;break ;c=a*b;break ;c=a/b; break break PushStack (s, c); ch=*A+ ;PopStack(s, result);retur nresult ;3.4中缀表达式转换成后缀表达式将中缀表达式转化为后缀表达式和前述对中缀表达式求值的方法完全类似，但只需要运算符栈，遇到运算对象时直接放后缀表达式的存 储区，假设中
14、缀表达式本身合法且在字符数组 A中，转换后的后缀表达 式存储在字符数组B中。具体做法：遇到运算对象顺序向存储后缀表达 式的B数组中存放，遇到运算符时类似于中缀表达式求值时对运算符的 处理过程，但运算符出栈后不是进行相应的运算， 而是将其送入B中存 放。读者不难写出算法，在此不在赘述。 程序的整体算法分两步：第一步，从” input.txt ”文件中读取中缀表达式，并应用运算符栈 OpHolder把中缀表达式转换为后缀表达式，将输出结果存放在一个 temp文件中。第二步，从temp文件中读取中缀表达式，并应用操作栈Opera nds 计算后缀表达式结果，将结果输出到”output.txt ”文件中。4测试方法设计针对程序的input.txt文件，并将运行结果与期望测试进行比较。5程序运行效果5.1基本测试：在in put文件中输入表达式如下图2:则输出结果如下图3:FP input, txt -记/事本二冈Fr output.Tst-记事本(J问冈文件編辑墮)林式& (V)文件骗揖格式查看妁帮购4P帮肋3.801 + 23.0018.3?
