表达式求值课程设计报告.docx

精选优质文档-----倾情为你奉上目 录2.2.1 栈的抽象数据类型的定义……………………………………………………………………....32.2.2栈的基本功能…………………………………………………………………………………….48专心---专注---专业1 需求分析1.1问题描述在计算机中，算术表达式由常量、变量、运算符和括号组成由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行因而在程序设计时，借助栈实现算法输入：一个算术表达式，由常量、变量、运算符和括号组成（以字符串形式输入）操作符为+、-*、/，用#表示结束算法输出：表达式运算结果算法要点：设置运算符栈和运算数栈辅助分析算符优先关系在读入表达式的字符序列的同时，完成运算符和运算数的识别处理，以及相应运算本算法的时间复杂度与输入的表达式的长度有密切的关系，在此不作深入分析1.2基本要求 设计友好的用户界面，利用所学工具开发一个简单的表达式求值应用程序，该程序能够对表达式进行加、减、乘、除运算，表达式中的操作数要求在实数范围内；对于异常表达式应能给出错误提示针对前面的要求分别设计合理的测试数据，比如3.154*(12+18)-23的结果应该是71.62等。

2 概要设计2.1 数据结构 表达式求值是程序设计语言编译中的一个最基本的问题它的实现是栈应用的一个典型例子本程序使用通常使用的算法为“算符优先法”要把一个表达式翻译成正确求值的一个机器指令序列，或者直接对求值 首先要能够正确解释表达式例如，要对下面的算术表达式求值：4+2*3-10/5首先要了解算术四则运算的规则即：（1）先乘除，后加减；（2）从左算到右；（3）先括号内，后括号外；由此，这个算术表达式的计算顺序应为4+2*3-10/5=4+6-10/5=10-10/5=10-2=8算符优先法就是根据这个运算优先关系的规定来实现对表达式的编译或解释执行的任何一个表达式都是由操作数（operand）、运算符（operator）、和界限符（delimiter）、组成的，我们称它们为单词一般地操作数即可以是常数也可以是被说明为变量或常量的标识符；运算符可以分为算术运算符、关心运算数和逻辑运算符三类；基本界限符有左右括号和表达式结束等这里我们仅讨论算数表达式的求值问题这种表达式只含有加、减、乘、除四种运算符我们把运算符和界限符统称为算符，他们构成的集合命名为OP根据上述三条运算规则，在运算的每一步中，任意两个相继出现的算符θ1和θ2之间的优先关系至多是下面三种关系之一； θ1<θ2 θ1的优先权低于θ2 θ1=θ2 θ1的优先权等于θ2 θ1>θ2 θ1的优先权高于θ2 表2.1定义了算符之间的优先关。

表2.1 算符间的优先关系θ1 θ2 + - * / （ ） #+>><<<>>->><<<>>*>>>><>>/>>>><>>（<<<<<=）>>>>>>#<<<<<=2.2 各模块间的调用关系及算法设计 各模块间的调用关系如下图：主程序模块初始化两个栈输入表达式表达式计算输出结果图 2.1 模块间的调用关系为了实现算符优先算法，可以使用两个工作栈一个称做OPTR，用以寄存运算符；另一个称做OPND，用以寄存操作数或运算结果算法的基本思想是:(1) 首先置操作数栈为空栈，表达式起始符“#”为运算符的栈底元素；(2) 依次读入表达式中每个字符，若是操作数则进OPND栈，若是运算符则和OPTR栈的栈顶运算符比较优先权后做相应操作，直至整个表达式求值完毕（即OPTR栈的的栈顶元素和当前读入的字符均为“#”）2.2.1 栈的抽象数据类型的定义ADT Stack{数据对象：D={ai |ai∈ElemSet,i=1,2,…，n, n≧0}数据对象：R1={|ai-1,ai∈D ,i=2,…，n}约定端为栈顶，ai端为栈底 InitStack(&S) 操作结果：构造一个空栈S。

Push(&S，ch) 初始条件：栈S已存在 操作结果：插入元素ch为新的栈顶元素 Pop(&S) 初始条件：栈S已存在 操作结果：删除S的栈顶元素Priority (c1, c2) 初始条件：c1,c2为运算符操作结果：判断运算符优先权，返回优先权高的Process(a,op,b)初始条件：a,b为实数，op为运算符操作结果：a与b进行运算，op为算符，返回其值}ADT Stack2.2.2栈的基本功能InitNumStack(NumStack *s) 和InitOpStack(OpStack *s)分别构造操作数栈与构造算符栈， PushNum(NumStack *numstack,double num)操作数栈插入num为新的栈顶元素，PushOp(OpStack *opstack,char op) 算符栈插入op为新的栈顶元素，PopOp(OpStack *opstack,char *op) 删除运算符栈s的栈顶元素，用p返回其值，PopNum(NumStack *numstack,double *num)删除操作数栈s的栈顶元素，用p返回其值。

其中部分操作的算法如下：void Process(NumStack *numstack,OpStack *opstack,char x){//根据输入的表达式求值，若表达式输入正确则返回结果，否则返回错误处理 double a,b;char c; static double tempnum=0.;static int len=10;static int dot=0,flags=0; if(isdigit(x) || x=='.')//判断输入的字符是否是0——9或小数点 { /*这段是处理数字符*/ if(x=='.')dot=1; else { if(dot==0) tempnum=tempnum*10+Cint(x);//Cint将字符数转化为整数 else { tempnum=tempnum+(double)Cint(x)/len; len*=10; } } } else { /*这段是处理操作符*/ if(flags==0 && x!='(') {PushNum(numstack,tempnum);tempnum=0.;len=10;dot=0;} switch(Priority(opstack->array[opstack->top-1],x)) { /*根据Priority的返回值做相应的处理*/ case '>':PushOp(opstack,x);flags=0;break;//大于进栈 case '<'://小于出栈进行运算并把结果入栈 PopOp(opstack,&c); PopNum(numstack,&b); PopNum(numstack,&a); PushNum(numstack,Calc(a,b,c));flags=1; Process(numstack,opstack,x);break; case '=':PopOp(opstack,&c);flags=1;break;//脱括号处理 default:printf("Wrong Express!");exit(0);//错误处理 } }}3 详细设计3.1数据存储结构设计元素类型、结点类型typedef struct{ int top;//栈的指针 double array[N];//用数组来存储}NumStack;//数字栈typedef struct{ int top; char array[N];}OpStack;//操作符栈3.2 主函数和其它函数的设计与实现void main(){ NumStack numstack;OpStack opstack;char s[N];int i=0; numstack.top=0;opstack.top=0; PushOp(&opstack,'#'); printf("\nEnter your expression and end it with #:");scanf("%s",s); for(i=0;(unsigned)i < strlen(s);i++) Process(&numstack,&opstack,s[i]); printf("The result is %f",numstack.array[numstack.top-1]); }int Cint(char mychar){//将数字符(0—9）转化为整数(0-9) return (mychar-48);}void PushNum(NumStack *numstack,double num){ //数字符进栈函数 numstack->top++; numstack->array[numstack->top-1]=num;}void PopNum(NumStack *numstack,double *num){ //数字符出栈函数 *num=numstack->array[numstack->top-1]; numstack->top--;}void PushOp(OpStack *opstack,char op){ //操作符进栈 opstack->top++; opstack->array[opstack->top-1]=op;}void PopOp(OpStack *opstack,char *op){ //操作符入栈函数 *op=opstack->array[opstack->top-1]; opstack->top--;}double Calc(double a,double b,char c){ /*根据c的类型进行加减运算器函数*/ double result; switch(c) { case '+':result=a+b;break; case '-':result=a-b;break; case '*':result=a*b;break; case '/':result=a/b;break; } return result;}char Priority(char y,char x){/*判断操作符的优先级分别返回"<"或 "="或">"*/ char priority='<';。