算术表达式的求解数据结构课程设计报告

1、word课程设计报告题目：算术表达式求值一、需求分析1、设计要求：给定一个算术表达式，通过程序求出最后的结果1>、从键盘输入要求解的算术表达式；2>、采用栈结构进行算术表达式的求解过程；3>、能够判断算术表达式正确与否；4>、对于错误表达式给出提示；5>、对于正确的表达式给出最后的结果；2、设计设想：为了实现算符优先算法使用两个工作栈，一个称作OPTR，以存放运算符；另一个称作OPND，用以存放操作数或运算结果。在操作数和操作符入栈前，通过一个函数来判别，输入的是操作数还是操作符，操作数入OPND，操作符入OPTR。在输入表达式的最后输入#，设定#的优先级最低，代

2、表表达式输入结束。在表达式输入过程中，遇操作数那么直接入栈，遇到运算符那么与栈顶运算符比拟优先级,假设当前运算符优先级高，那么当前运算符入栈,扫描下一符号;否那么栈顶运算符出栈,两操作数出栈,进行运算,所得结果入数栈,重新比拟当前运算符与新栈顶运算符。如此重复直到栈顶运算符与当前符号均为#，运算结束。二、概要设计1、本程序包含的模块：1栈模块实现栈抽象数据类型2运算模块实现数据表达式的运算3主程序模块算术运算式的求解栈模块主函数模块main运算模块初始化栈定义栈结构出栈入栈取栈顶元素判断输入字符类型判断符号优先级根底运算函数运算函数三、详细设计1栈模块1、定义栈结构struct Sqstack

3、elemtype *top;/栈顶元素elemtype *base; /栈底元素int stacksize;/栈的大小  ;2、栈的根本操作初始化栈status initstack(struct Sqstack &s)s.base=(elemtype *)malloc(stack_size*sizeof(elemtype);if(!s.base)return OVERFLOW;s.top=s.base;s.stacksize=stack_size;return OK;入栈status push(struct Sqstack &s,elemtype e)if(s.top

4、-s.base>=s.stacksize) s.base=(elemtype*)realloc(s.base,(s.stacksize+stack_increasement)*sizeof(elemtype);if(!(s.base)return OVERFLOW;s.top=s.base+s.stacksize;s.stacksize+=stack_increasement;* s.top+=e;return OK;出栈elemtype pop(struct Sqstack &s)elemtype e;if(s.top= =s.base)return ERROR;e=*-s.t

5、op;return e;取栈顶元素elemtype gettop(struct Sqstack &s)elemtype e;if(s.top=s.base)return ERROR;e=*(s.top-1);return e;2运算模块1、判断输入字符c是否为操作符：假设是，那么返回1；否那么，返回0 int In(int c) char p10="+-*/()#" int i=0; while(pi!='0') if(pi=c) return 1;i+; return 0;2、判断运算符的优先级 char precede(char top,char

6、 c)/该函数为判断当前运算符与前一个运算符的优先级，前一个运算符高于或等于当前运算符的优先级那么返回>， 前一个运算符小于当前运算符的优先级那么返<，当前一个运算符为当前运算符为时返回=，用于去除表达式的括号。 char result; switch(c) case '#': result='>' break; case '+': case '-': if(top='#'|top='(') result='<' else result='>&#

7、39; break; case '*': case '/': if(top='*'|top='/'|top='') result='>' else result='<' break; case '%': if(top='%'|top='/'|top=''|top='*') result='>' else result='<'break; case &

8、#39;)': if(top='(') result='=' else result='>' break; case '(': result='<' break; case '': result='<' break; default: printf("操作符输入错误！n"); return result;3、运算函数 根底运算函数：实现相应的加、减、乘、除、乘方及带小括号的根本数学运算并返回结果，其中a，b为两个操作数，theta为操作符

9、elemtype operate(elemtype a,char theta,elemtype b) elemtype result; switch(theta) case '+': result=a+b; break; case '-': result=a-b; break; case '*': result=a*b; break; case '/': if(b=0) printf("nn输入错误!分母不能为0!n"); result=0; else result=a/b;break; case '%

10、': if(b=0|b=NULL) printf("nn输入错误!n");return 0;break; else result=a%b;break; case '': result=(int)pow(double)a,(double)b); break; default: printf("操作符输入错误！n"); return result; 运算函数elemtype evaluate(struct Sqstack opnd,struct Sqstack optr)/该函数为求表达式的值的整个操作过程，通过调用相应的函数实现遇到

11、运算符那么与栈顶运算符比拟优先级,/假设当前运算符优先级高(前面的运算还不应执行)那么当前运算符入栈,扫描下一符号;否那么栈顶运算符出栈,同时两操作数出栈,进行运算,所得结果入数栈,/重新比拟当前运算符(注意当前运算符未变)与新栈顶运算符。如此重复直到栈顶运算符与当前符号均为#，运算结束。/假设操作数为个位数，那么直接将输入的字符减48后入栈，假设为多位数，那么通过flag来实现。假设输入字符c为操作数且flag=1(即操作数为多位数)，那么将操作数栈的栈顶元素出栈后乘以10，然后加上，c-48然后将二者的和入操作数栈。 elemtype a,b,c,theta,e; initstack(op

12、tr); push(optr,'#'); initstack(opnd); c=getchar(); int flag=0;/当输入操作数时flag=1；当输入操作符时flag=0；/当前输入为操作数且flag=1时，将操作数栈的栈顶元素出栈，然后将其和当前输入转换成相应的int类型 while(c!='#'|gettop(optr)!='#') if(!In(c) /c假设为操作数那么入opnd栈 if(flag=1) e=pop(opnd); / 取栈顶元素 push(opnd,(e*10+(c-48);/将输入数在转化为int型，并将上次输

13、入数*10并与当前操作数相加，将结果如操作数栈 else push(opnd,c-48); flag=1; c=getchar(); else flag=0;/当前字符为操作符，那么入操作符栈，并将flag置为0 switch(precede(gettop(optr),c)/ 判断当前操作数与操作符栈中的栈顶元素的优先级 case '<': push(optr,c); c=getchar(); break;/ 假设当前操作符的优先级高于操作符栈的栈顶元素，那么将当前操作符入操作符栈 case '=': e=pop(optr); c=getchar(); b

14、reak;/ 假设当前操作符与操作符栈的栈顶元素构成匹配的括号，那么/将操作符栈顶元素出栈 case '>': theta=pop(optr); b=pop(opnd); a=pop(opnd); push(opnd,operate(a,theta,b); break;/ 假设当前操作符的优先级低于操作符栈的栈顶元素，那么将操作符栈栈顶元素出栈，并将操作数栈的栈顶两个元素出栈，计算两个元素间以操作符栈栈顶元素为运算符的数学运算 /switch/if /while return pop(opnd);3主程序模块1、main函数 void main(int argc,char

15、 *argv) struct Sqstack opnd; /操作数栈 struct Sqstack optr;/操作符栈initstack(opdn);initstack(optr); elemtype result; printf("*n"); printf("算术运算式的求解"); printf("n*n"); printf("n请输入算术运算表达式(以'#'结尾):n"); printf("n"); result=evaluate(opnd,optr); printf(&q

16、uot;n*n"); printf("nn运算的结果是 :n n%dn",result); printf("n*n"); 四、调试分析1、测试结果 1> 测试数据：3+7*2-1# 测试结果： 2> 测试数据：(3+7)*2-1# 测试结果： 3> 测试数据： 1/0# 测试结果： 2、程序时间复杂度为On；3、设计中出现的问题：在开始的设计中没有注意除数不能为0 ，后来参加if(b=0) printf("分母为0,the result is errorn"); result=0; else result=a/b;break;来判断除数是否为04、算法改良：1>输入的操作数和操作码由于是字符串类型的，在原设计中实现的操作都是对个位数实现的，实用性不大，故在后来的设计中，通过一个标志flag实现了标志操作数的连续输入的判别，继而实现了多位数的表达式运算2>开始只实现了加、减、乘、除及带小括号的数学运算，考虑到实用性，在后来的设计中引入pow函数，实现了乘方的运算，调整结果如下：3>最初设计的运行界面过于单调，不够友好，改良时参