表达式求值课程设计报告表达式求值《数据结构》课程设计报告题目: 栈的应用:表达式求值(系): 信息科学与工程学院院专业班级: 软件工程1102班学生姓名:学号: 指导教师:20 13 年 6 月 8 日至20 13 年 6 月 21 日表达式求值目录目录 (2)1 概述 (1)1.1 课程设计目的 (1)1.2 课程设计内容 (1)2 系统需求分析 ......................................................12.1 系统目标 (1)2.2 主体功能 (1)2.3 开发环境 (1)3 系统概要设计 ....................................................23.1 系统的功能模块划分 (2)3.2 系统流程图 (2)4系统详细设计 .....................................................35 测试 ............................................................65.1 测试方案 (6)5.2 测试结果 (6)6 小结 ............................................................8参考文献 ..........................................................9附录1 源程序清单 (10)2数据结构课程设计报告(2012)表达式求值1 概述1.1 课程设计目的1(要求学生达到熟练掌握C语言的基本知识和技能。
2(了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力。
3(提高程序设计和调试能力。
学生通过上机实习，验证自己设计的算法的正确性。
学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。
4(培养算法分析能力。
分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水平。
5(初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能。
1.2 课程设计内容设计一个表达式求值的程序。
该程序必须可以接受包含(，)，+，-，*，/，%，b和^(求幂运算符，a^b=a)的中缀表达式，并求出结果。
如果表达式正确，则输出表达式的结果;如果表达式非法，则输出错误信息。
2 系统需求分析2.1 系统目标利用栈设计一个程序，该程序能够用于表达式求值，程序将读入的中缀表达式转换为后缀表达式，然后读取后缀表达式，输出结果。
输入要求:程序从“input.txt”文件中读取信息，在这个文件中如果有多个中缀表达式，则每个表达式独占一行，程序的读取操作在文件的结尾处停止。
输出要求:对于每一个表达式，将其结果放在“output.txt”文件的每一行中。
这些结果可能是值(精确到小数点后两位)，也可能是错误信息“ERROR IN INFIXNOTATION”。
2.2 主体功能能够处理以字符序列的形式输入的不含变量的实数表达式，正确处理负数与小数，判断表达式是否语法正确(包含分母不能为零的情况)，正确实现对算术四则混合运算表达式的求值，能够将计算中遇到的问题和结果以文件的形式予以存储。
2.3 开发环境Microsoft Visual C++ 6.01表达式求值3 系统概要设计3.1 系统的功能模块划分1.判断操作数的函数isnum()判断当前所指字符是否属于数字，是就返回‘1’，不是就返回‘0’。
2.求运算符优先级函数priority()为了方便判断运算符优先级，先利用switch函数将不同的运算符返回不同的整型数字，在根据数字的大小判断优先级。
‘+’，‘-’优先级相同，返回数字相同，‘*’，‘/’也是。
3.表达式求值函数infix_value()此函数是直接按照设计思路完成问题要求的函数，其中要调用到判断操作符的函数isnum()和求运算符优先级的函数priority()。
循环结束弹出栈2的数值，并返回。
4.主函数main()定义一个数组存储表达式整个字符串，将返回的数值直接赋值到浮点型的result，输出result。
5.两个栈的函数设计:栈的初始化函数charInit_SeqStack()Init_SeqStack()栈判空 Empty_SeqStack()char Empty_SeqStack()入栈函数 Push_SeqStack()charPush_SeqStack()出栈函数 Pop_SeqStack()charPop_SeqStack()取栈顶函数 GetTop_SeqStack()charGetTop_SeqStack()销毁栈 Destory_SeqStack()charDestory_SeqStack() 3.2 系统流程图2数据结构课程设计报告(2012)开始优先级比较算法Operate 算法建立栈存放操作字符存放数据计算表达式式否合法输出错误提输出表达式值示结束图1 系统流程图4系统详细设计1. 基本分析:在计算机中，算术表达式的计算往往是通过使用栈来实现的。
所以，本表达式求值程序的最主要的数据结构就是栈。
可以使用栈来存储输入表达式的操作符和操作数。
输入的表达式是由操作数和运算符以及改变运算次序的圆括号连接而成的式子。
表达式求值是高级语言编译中的一个基本问题，是栈的典型应用实例。
任何一个表达式都是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。
操作数既可以是常数，也可以是被说明为变量或常量的标识符;运算符可以分为算术运算符、关系运算符和逻辑运算符三类;基本界限符有左右括号和表达式结束符等。
2. 中缀表达式求值:中缀表达式:每个二目运算符在两个运算量的中间，假设操作数是整型常数，运算符只含加、减、乘、除等四种运算符，界限符有左右括号和表达式起始、结束3表达式求值符“,”，如:,(7+15)*(23-28/4),。
要对一个简单的算术表达式求值，首先要了解算术四则运算的规则，即:(1) 从左到右;(2) 先乘除，后加减;(3) 先括号内，后括号外。
运算符和界限符可统称为算符，它们构成的集合命名为OPS。
根据上述三条运算规则，在运算过程中，任意两个前后相继出现的算符θ1和θ2之间的优先关系必为下面三种关系之一:θ1<θ2，θ1的优先权低于θ2。
θ1=θ2，θ1的优先权等于θ2。
θ1>θ2，θ1的优先权高于θ2。
实现算符优先算法时需要使用两个工作栈:一个称作operator，用以存放运算符;另一个称作operand，用以存放操作数或运算的中间结果。
算法的基本过程如下:首先初始化操作数栈operand和运算符栈operator，并将表达式起始符“,”压入运算符栈;依次读入表达式中的每个字符，若是操作数则直接进入操作数栈operand，若是运算符，则与运算符栈operator的栈顶运算符进行优先权比较，并做如下处理:(1) 若栈顶运算符的优先级低于刚读入的运算符，则让刚读入的运算符进operator栈;(2) 若栈顶运算符的优先级高于刚读入的运算符，则将栈顶运算符退栈，送入θ，同时将操作数栈operand退栈两次，得到两个操作数a、b，对a、b进行θ运算后，将运算结果作为中间结果推入operand栈;(3) 若栈顶运算符的优先级与刚读入的运算符的优先级相同，说明左右括号相遇，只需将栈顶运算符(左括号)退栈即可。
operator栈的栈顶元素和当前读入的字符均为“#”时，说明表达式起始符“#”与表达式结束符“#”相遇，整个表达式求解结束。
int ExpEvaluation(){ /*读入一个简单算术表达式并计算其值。
*/InitStack(&operand); InitStack(&operator);PushStack(&operator, ’,’);printf(″\n\n Please input an expression (Ending with ,) :″);ch=getchar(); /*读入表达式中的一个字符*/while(ch!=‘,’||GetTop(operator)!=‘,’){ if(!In(ch, OPS)) /*判断ch是否运算符*/{ a=GetNumber(&ch); /* 用ch逐个读入操作数的各位数码，并转化为十进制数a */PushStack(&operand,a);}elseswitch(Compare(GetTop(operator),ch)){ case ′<′: PushStack(&operator, ch); ch=getchar();break;case ′=′: PopStack(&operator,&x); ch=getchar();break;4数据结构课程设计报告(2012)case ′>′: PopStack(&operator, &op); PopStack(&operand,&b);PopStack(&operand, &a);v=Execute(a,op,b);PushStack(&operand,v); break;}}v=GetTop(operand);return(v); }为了处理方便，编译程序常把中缀表达式首先转换成等价的后缀表达式，后缀表达式的运算符在运算对象之后。
在后缀表达式中，不再引入括号，所有的计算按运算符出现的顺序，严格从左向右进行，而不用再考虑运算规则和级别。
中缀表达式“(a+b*c)-d/e”的后缀表达式为:“abc*+de/-”。
3. 后缀表达式求值:计算一个后缀表达式，算法上比计算一个中缀表达式简单的多。
这是因为表达式中即无括号又无优先级的约束。
具体做法:只使用一个对象栈，当从左向右扫描表达式时，每遇到一个操作数就送入栈中保存，每遇到一个运算符就从栈中取出两个操作数进行当前的计算，然后把结果再入栈，直到整个表达式结束，这时送入栈顶的值就是结果。
下面是后缀表达式求值的算法，在下面的算法中假设，每个表达式是合乎语法的，并且假设后缀表达式已被存入一个足够大的字符数组A中，且以‘#’为结束字符，为了简化问题，限定运算数的位数仅为一位且忽略了数字字符串与相对应的数据之间的转换问题。
double calcul_exp(char *A) /*本函数返回由后缀表达式A表示的表达式运算结果*/{ SeqStarck s;ch=*A++ ; InitStack(s);while(ch!= ’#’ ){ if(ch!=运算符) PushStack(s, ch);else{ PopStack(s, &a);PopStack(s, &b); /*取出两个运算量*/switch(ch){ case ch==’+’: c=a+b; break ;case ch==’-’: c=a-b; break ;case ch==’*’: c=a*b; break ;case ch==’/ ’: c=a/b; break ;case ch==’%’:c=a%b; break ;}PushStack (s, c) ;}ch=*A++ ;}PopStack(s, result) ;5表达式求值return result ;}4. 中缀表达式转换成后缀表达式 :将中缀表达式转化为后缀表达式和前述对中缀表达式求值的方法完全类似，但只需要运算符栈，遇到运算对象时直接放后缀表达式的存储区，假设中缀表达式本身合法且在字符数组A中，转换后的后缀表达式存储在字符数组B中。