用两种方式实现表达式自动计算.doc

用两种方式实现表达式自动计算一、设计思想本项目用两种方式实现表达式自动计算：一是，用扫两遍表达式的方法；二是，用扫一遍表达式的方法。其算法如下：u 算法一：扫两遍表达式求值的基本思路是：先将中缀表达式转化为后缀表达式，再通过计算后缀表达式求表达式的值。第一遍扫描中缀表达式，将其转换为后缀表达式，在这步中用到一个运算符栈和一个列表（用数组实现）。当扫到一个数时，因为运算数的位数不一定而且还有小数点，所以需要判断运算数的位数，将这个运算数按原来的顺序挂到列表中；当扫到一个运算符时，如果栈空：运算符直接入栈。栈不空时：遇到左括号，直接入栈；遇到右括号，则开始出栈挂到列表后，直到栈顶为左括号，左括号出栈；遇到加、减、乘、除、求余运算符号时，当栈顶的运算符优先级低于扫到的运算符，运算符入栈，否则运算符出栈挂到列表后，直到满足入栈条件；当扫描完整个中缀表达式，将栈里面的运算符全都出栈挂列表后。另外，因为后缀表达式中两个运算数会连在一起，所以为了区分两个运算数，每当扫描到加、减、乘、除、求余运算符号和栈中运算符出栈挂表后，在列表中添加一个空格作为分隔符。这样列表中的表达式就是对应的后缀表达式。 第二遍扫描后缀表达式，并计算，这步中用到一个栈来放扫描到的数。当扫到一个数时，因为运算数的位数不一定而且还有小数点，所以在扫到一个数时要判断这个数的位数，将这个完整的运算数字符串整个取出，把这个字符串转化为数值型（如;利用 atof（） 函数将字符串转换为浮点型等），将其入栈；当扫到一个运算符时，则出栈两个数，先出栈的数作为第一个运算数后出栈的作为第二个运算数，按照所扫描到的运算符进行计算，并将计算结果放到栈中。当扫描完整个后缀表达式后，在栈中只有一个数，这个数就是我们所要求值的表达式的结果。u 算法二：扫一遍表达式求值的基本思路是：用两个栈（一个字符栈、一个数字栈）边扫描边计算，最后在数字栈中所得的数就是计算结果。扫描要求值的表达式，当扫描到一个数时，因为运算数的位数不一定而且还有小数点，所以在扫到一个数时要判断这个数的位数，将这个完整的运算数字符串整个取出，把这个字符串转化为数值型（如;利用 atof（） 函数将字符串转换为浮点型等），将其入数字栈。当扫描到一个运算符时，如果运算符栈空：运算符直接入运算符栈。运算符栈不空时：遇到左括号，直接入运算符栈；遇到右括号则从数字栈中出栈两个数，先出栈的数作为第一个运算数后出栈的作为第二个运算数，从运算符栈中出栈一个运算符，将两个数按照出栈运算符进行计算，并将计算结果放到数字栈中，直到运算符栈栈顶为左括号，左括号出栈；遇到加、减、乘、除、求余运算符号时，当运算符栈栈顶的运算符优先级低于扫到的运算符，运算符入运算符栈，否则从数字栈中出栈两个数，先出栈的数作为第一个运算数后出栈的作为第二个运算数，从运算符栈中出栈一个运算符，将两个数按照出栈运算符进行计算，并将计算结果放到数字栈中，直到满足入栈条件。当扫描完整个表达式，如果运算符栈中不空，则从数字栈中出栈两个数，先出栈的数作为第一个运算数后出栈的作为第二个运算数，从运算符栈中出栈一个运算符，将两个数按照出栈运算符进行计算，并将计算结果放到数字栈中，直到运算符栈为空。这样，最后在数字栈中只有一个数了，这个数就是我们所要求值的表达式的结果。二、算法流程图开始初始化运算数栈和运算符栈输入一个表达式，存在数组exp1中扫描到数？扫描到（ ？扫描到 ）？exp1index = 0？扫描到 + - * / % ？是否否否否否否运算符栈为空？运算符栈出栈一个运算符存到数组exp2输出数组exp2，即后缀表达式取出整个运算数，存入exp2数组中,入运算符栈栈顶为 ( ？运算符栈出栈一个运算符存到数组exp2运算符栈中（ 出栈运算符优先级高于运算符栈顶？入运算符栈运算符栈出栈一个运算符存到数组exp2是否是否是是是是是是exp2index = 0？否运算符栈空？运算数栈出栈两个数运算符栈出栈一个运算符，计算结果入运算数栈是扫描到数？扫描到 + - * / % ？否是是输出运算数栈中的数即表达式的值结束是取出整个运算数，转换为浮点型，入运算数栈运算数栈出栈两个数与扫到运算符运算，计算结果入运算数栈运算符优先级高于运算符栈顶？是否否入运算符栈否图1 扫两遍算法流程图开始初始化运算数栈和运算符栈输入一个表达式，存在数组exp中扫描到数？扫描到（ ？扫描到 ）？expindex = 0？0扫描到 + - * / % ？是否否否否否否运算符栈为空？运算数栈出栈两个数运算符栈出栈一个运算符，计算结果入运算数栈输出运算数栈中的元素，即运算结果结束取出整个运算数，转换为浮点型，入运算数栈入运算符栈栈顶为 （ ？运算数栈出栈两个数运算符栈出栈一个运算符，计算结果入运算数栈运算符栈中（ 出栈运算符优先级高于运算符栈顶？入运算符栈运算数栈出栈两个数运算符栈出栈一个运算符，计算结果入运算数栈是否是否是是是是是图2 扫一遍算法流程图图1 : 扫两遍的算法流程图，在扫描中以index为索引作为数组的下标，扫完一个字符，完成相应操作，index自加；在扫完每个运算数后加个空格作为分隔符；在将数字转化为浮点数时，取到整个数的字符串，用atof()函数将其转换为浮点数。在每次扫描各用到一个栈，在程序的过程中，我们能得到后缀表达式。图2 ：扫一遍的算法流程图，在扫描中以index为索引作为数组的下标，扫完一个字符，完成相应操作，index自加；在将数字转化为浮点数时，取到整个数的字符串，用atof()函数将其转换为浮点数。在扫描计算的过程中用到两个栈。三、源代码下面给出的是用扫两遍算法实现的程序的源代码：在本算法中在每次扫描表达式时各用到一个栈，在第一边扫描过程中先把中缀表达式转换为后缀表达式，通过计算后缀表达式，间接的求得表达式的值。代码如下：#include#includetypedef struct /* 定义数栈 */double arrary_num100;int top_num;STACK_NUM;typedef struct /* 定以结构体类型 */ char mysign; int level; MYSIGN;typedef struct /* 定义运算符号栈 */MYSIGN arrary_sign20;int top_sign;STACK_SIGN;void Init_stack_num(STACK_NUM *s) /* 初始化栈 */ (*s).top_num = 0; void Init_stack_sign(STACK_SIGN *s) (*s).top_sign = 0; void push_num (STACK_NUM *s,double n) /* 进栈 */(*s).arrary_num(*s).top_num = n;(*s).top_num+;void push_sign(STACK_SIGN *s,MYSIGN *sign)(*s).arrary_sign(*s).top_sign = *sign;(*s).top_sign+;double pop_num(STACK_NUM *s) /* 出栈 */if (*s).top_num = 0) return NULL;else (*s).top_num-; return (*s).arrary_num(*s).top_num; MYSIGN pop_sign(STACK_SIGN *s) MYSIGN ren; if (*s).top_sign = 0) ren.level=0; return ren; else (*s).top_sign-; return (*s).arrary_sign(*s).top_sign; double gettop_num(STACK_NUM *s) /* 看栈顶 */if (*s).top_num = 0) return NULL ;else return (*s).arrary_num(*s).top_num-1;MYSIGN gettop_sign(STACK_SIGN *s) MYSIGN ren;if (*s).top_sign = 0) ren.level=0; return ren; else return (*s).arrary_sign(*s).top_sign-1;double cal_exp(char *exp1)STACK_NUM stack_num;STACK_SIGN stack_sign;MYSIGN tempsign;int index1,index2,tempindex;double number;char exp2100,tempexp20;double a,b;char tempch;Init_stack_num(&stack_num);Init_stack_sign(&stack_sign);index1=0;index2=0;tempindex=0;tempexp0=0;while(exp1index1 != 0) if(exp1index1=0& exp1index1=0& exp1index1=tempsign.level) exp2index2=pop_sign(&stack_sign).mysign; index2+; exp2index2= ; index2+; exp2index2=0 ; push_sign(&stack_sign,&tempsign); index1+; else if(exp1index1=* | exp1index1=/ | exp1index1=%) exp2index2= ; index2+; tempsign.mysign=exp1index1; tempsign.level=2; while(gettop_sign(&stack_sign).level=tempsign.level) exp2index2=pop_sign(&stack_sign).mysign; index2+; exp2index2= ; index2+; push_sign(&stack_sign,&tempsign); index1+; else if(exp1index1=() tempsign.mysign = exp1index1; tempsign.level=-1; push_sign(&stack_sign,&tempsign); index1+; else if(exp1index1=) while(gettop_sign(&stack_sign).level != -1) exp2index2=pop_sign(&stack_sign).mysign; index2+; pop_sign(&stack_sign); index1+; while(gettop_sign(&stack_sign).level !=0) exp2index2= ; index2+; exp2index2=pop_sign(&stack_sign).mysign; index2+; exp2index2=0 ;printf(nThe expression2 is : %s,exp2); /* 得到后缀表达式 */index1=0;while(exp2index1 != 0) if(exp2index1=0& exp2index1=0& exp2index1=9) | exp2index1=. ) tempexptempindex=exp2index1; tempexptempindex+1=0; index1+; tempindex+; if( tempexp0 != 0) number = atof(tempexp); push_num(&stack_num ,number); tempexp0=0; tempindex=0; else if(exp2index1= ) while(exp2index1= ) index1+; else if(exp2index1=+ | exp2index1=-) a=pop_num(&stack_num); b=pop_num(&stack_num); switch (exp2index1) case +:push_num(&stack_num ,b+a);break; case -:push_num(&stack_num ,b-a);break; index1+; else if(exp2index1=* | exp2index1=/ | exp2index1=%) a=pop_num(&stack_num); b=pop_num(&stack_num); switch (exp2index1) case *:push_num(&stack_num ,b*a);break; case /:push_num(&stack_num ,b/a);break; case %:push_num(&stack_num ,(int)b%(int)a);break; index1+; return pop_num(&stack_num) ;main()char expression100;double result;printf(Please input the expression :n);scanf(%s,expression);result=cal_exp(expression);printf(nThe result is : %f,result);getch();下面给出的是用扫一遍算法实现的程序的源代码：在本算法中用到两个栈，一个运算数栈、一个运算符栈，在扫描过程中，边扫描边计算，直接计算所给的中缀表达式，得到所要求的表达式的值。代码如下：#include#includetypedef struct /* 定义数栈 */ double arrary_num100; int top_num;STACK_NUM;typedef struct char mysign; int level; MYSIGN;typedef struct /* 定义运算符号栈 */ MYSIGN arrary_sign20; int top_sign;STACK_SIGN;void Init_stack_num(STACK_NUM *s) /* 初始化栈 */ (*s).top_num = 0; void Init_stack_sign(STACK_SIGN *s) (*s).top_sign = 0; void push_num(STACK_NUM *s,double n) /* 进栈 */ (*s).arrary_num(*s ).top_num = n; (*s).top_num+; void push_sign(STACK_SIGN *s,MYSIGN *sign) (*s).arrary_sign(*s).top_sign = *sign; (*s).top_sign+; double pop_num(STACK_NUM *s) /* 出栈 */ if (*s).top_num = 0) return NULL; else (*s).top_num-; return (*s).arrary_num(*s).top_num; MYSIGN pop_sign(STACK_SIGN *s) MYSIGN ren; if (*s).top_sign = 0) ren.level=0; return ren; else (*s).top_sign-; return (*s).arrary_sign(*s).top_sign; double gettop_num(STACK_NUM *s) /* 取栈顶 */if (*s).top_num = 0) return NULL ;else return (*s).arrary_num(*s).top_num-1;MYSIGN gettop_sign(STACK_SIGN *s) MYSIGN ren; if (*s).top_sign = 0) ren.level=0; return ren; else return (*s).arrary_sign(*s).top_sign-1; double cal_exp(char *exp) STACK_NUM stack_num;STACK_SIGN stack_sign;MYSIGN tempsign;int index,tempindex;double number;char tempexp20;double a,b;char tempch;Init_stack_num(&stack_num);Init_stack_sign(&stack_sign);index=0;tempindex=0;tempexp0=0;while(expindex!=0) if(expindex=0& expindex=0& expindex= tempsign.level) tempch=pop_sign(&stack_sign).mysign; a=pop_num(&stack_num); b=pop_num(&stack_num); switch (tempch) case +:push_num(&stack_num ,b+a);break; case -:push_num(&stack_num ,b-a);break; case *:push_num(&stack_num ,b*a);break; case /:push_num(&stack_num ,b/a);break; case %:push_num(&stack_num ,(int)b%(int)a);break; push_sign(&stack_sign,&tempsign); index+; else if(expindex=* | expindex=/ | expindex=%) tempsign.mysign=expindex; tempsign.level=2; while(gettop_sign(&stack_sign).level=tempsign.level) tempch=pop_sign(&stack_sign).mysign; a=pop_num(&stack_num); b=pop_num(&stack_num); switch (tempch) case *:push_num(&stack_num ,b*a);break; case /:push_num(&stack_num ,b/a);break; case %:push_num(&stack_num ,(int)b%(int)a);break; push_sign(&stack_sign,&tempsign); index+; else if(expindex=() tempsign.mysign=expindex; tempsign.level=-1; push_sign(&stack_sign,&tempsign); index+; else if(expindex=) while(gettop_sign(&stack_sign).level != -1) tempch=pop_sign(&stack_sign).mysign; a=pop_num(&stack_num); b=pop_num(&stack_num); switch (tempch) case +:push_num(&stack_num ,b+a);break; case -:push_num(&stack_num ,b-a);break; case *:push_num(&stack_num ,b*a);b