数据结构课程设计报告-表达式求值.doc

班级：计101 学号：1013023007姓名：嵇媛媛课程设计题目：表达式求值一、 需求分析1表达式求值是在日常生活中经常要用到的数学问题，也是程序设计语言编译中的一个最基本问题，它的实现是栈应用的一个典型例子。在本程序中用到的是“算符优先法”，使用两个工作栈，一个称作OPND，用以寄存操作数和运算结果；一个称作OPTR，用以寄存运算符。 2程序说明：（1）输入的形式和输出值的范围：输入的操作数要求在实数范围内，表达式要以#号结束；输出值也为实数。（2）输出的形式：将表达式的结果输出，结果为双精度型。（3）程序所能够达到的功能：当用户输入一个合法的算术表达式后，能够返回正确的结果，能够计算的运算符包括：加、减、乘、除和括号。对于异常表达式能给出错误提示。二、 详细设计1 本程序所用到的数据及其数据结构的定义（1）本程序所用的数据结构是栈，定义如下：typedef struct /定义操作数栈 double arrayN; int top; /栈顶指针 OPND; typedef struct /定义运算符栈 char arrayN; int top; /栈顶指针 OPTR; （2）基本操作 int Cint(char mychar) /将字符0-9转换成数值 void PushNum(OPND *OPND,double num) /操作数进栈 void PopNum(OPND *OPND,double *num) /操作数出栈 void PushOp(OPTR *OPTR,char optr) /运算符进栈 void PopOp(OPTR *OPTR,char *op) /运算符出栈 double Calculate(double a,double b,char c) /进行二元运算 char Priority(char y,char x) /判定运算符的优先关系 void Process(OPND *OPND,OPTR *OPTR,char x) /计算表达式int IsOp(char ch) /判断是否为运算符void TestMes(int n) /提示信息显示int Test(char s ) /检查表达式是否有错2 主程序 void main()OPND OPND; OPTR OPTR; char sN; int i=0; OPND.top=0; OPTR.top=0; PushOp(&OPTR,#); coutn请输入一个以#字符结束的算术表达式：endl; cin.getline(s,sizeof(s);while(!Test(s) coutn请重新输入一个以#字符结束的算术表达式：endl; cin.getline(s,sizeof(s); for(i=0;istrlen(s);i+) Process(&OPND,&OPTR,si); printf(结果是：%fn,OPND.arrayOPND.top-1); getch(); 3 函数间的调用关系图 mainPushOpTestProcessCintPushNumPriorityCalculateTestMesPopNumIsOpPopOp三、 调试分析问题及解决方法（1）在程序最后用了getch()，编译时无法识别。解决方法：加上头文件conio.h（2）程序中定义的输入类型是字符型，而操作数栈为双精度型，在进栈前必须转换。解决方法：加入函数int Cint(char mychar) return (mychar-48);，利用ASCII码将字符0-9转换成数值，并用double tempnum；将数值转换成双精度型再进栈。四、 用户手册1键入所要求值的表达式，并以#号结束。如图，输入表达式3*（7-2）+5#，可以得到结果是20，所得结果是double型的。 2 当输入的是一个以运算符开头的表达式时，出现如下界面，要求重新输入。3当输入的表达式没有以#号结尾时，会出现如下界面，要求重新输入。五、 测试结果1 输入表达式：5*（6+2）-4#，输出结果是：36.0000002 输入表达式：5-3，输出结果是：没有以#字符结束.，请重新输入3 输入表达式：+8-4#，输出结果是：表达式首字符不能是运算符.，请重新输入六、 附录源程序：#define N 100#include #include #include #include #include #include typedef struct /定义操作数栈 double arrayN; int top; /栈顶指针 OPND; typedef struct /定义运算符栈 char arrayN; int top; /栈顶指针 OPTR; int Cint(char mychar) /将字符0-9转换成数值 return (mychar-48);void PushNum(OPND *OPND,double num) /操作数进栈 OPND-top+; OPND-arrayOPND-top-1=num;void PopNum(OPND *OPND,double *num) /操作数出栈 *num=OPND-arrayOPND-top-1; OPND-top-;void PushOp(OPTR *OPTR,char optr) /运算符进栈 OPTR-top+; OPTR-arrayOPTR-top-1=optr;void PopOp(OPTR *OPTR,char *op) /运算符出栈 *op=OPTR-arrayOPTR-top-1; OPTR-top-;double Calculate(double a,double b,char 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=;break; case *: case /:if(y=( | y=#| y=+ | y=-)priority=;break; case (:priority=;break; case ):if(y=()priority=;break; case #:if(y=#)priority=;break; default:priority=E; return priority;void Process(OPND *OPND,OPTR *OPTR,char x) /计算表达式 double a,b;char c; static double tempnum=0.00000000; static int len=10; /用于各数位上的值的转换 static int dot=0,flags=0; /flags用于判定操作数是否进栈 if(isdigit(x) | x=.)if(x=.) dot=1; else if(dot=0) tempnum=tempnum*10+Cint(x); else tempnum=tempnum+(double)Cint(x)/len; len*=10; else if(flags=0 & x!=()PushNum(OPND,tempnum); tempnum=0.00000000;len=10;dot=0; switch(Priority(OPTR-arrayOPTR-top-1,x) case :PushOp(OPTR,x);flags=0;break; case : PopOp(OPTR,&c); PopNum(OPND,&b); PopNum(OPND,&a); PushNum(OPND,Calculate(a,b,c);flags=1; Process(OPND,OPTR,x);break; case =:PopOp(OPTR,&c);flags=1;break; default:printf(Wrong Express!); exit(0); int IsOp(char ch) /判断是否为运算符 switch (ch) case +: case -: case *: case /: return 1; break; default: return 0; break; void TestMes(int n) /提示信息显示 switch (n) case 1: coutn表达式首字符不能是运算符.endl; break; case 2: coutn没有以#字符结束.endl; break; default: break; int Test(char s) /检查表达式是否有错 int i; char ch; ch = s0; if (IsOp(ch) /第一个是运算符 TestMes(1); return 0; for(i=0;istrlen(s);i+); if (si-1 != #) /结束符错误 TestMes(2); return 0; else return 1; void main()OPND OPND; OPTR OPTR; char sN; int i=0; OPND.top=0; OPTR.top=0; /置空栈 PushOp(&OPTR,#); /表达式起始符#为运算符栈的栈底元素 coutn请输入