1、如果栈内元素的优先级大于等于当前元素的,则依次出栈元素进行计算。每次计算要在数栈出栈两个整合后的数,先出栈的数字放在运算符后面,后出栈的数字放在运算符的前面,将运算以后的结果再次存入数栈。如果遇到左括号则无条件进栈,并只在有右括号出现的时候才有可能出栈。如果遇到右括号,则无条件让栈内元素出栈进行计算,直到左括号出栈为止。如此计算将表达式所有元素全部索引。之后再对栈内剩余元素进行操作。为了方便计算,计算过程使用了函数体。主函数只负责输入中缀表达式和输出最后的运算结果。同时,建立了优先级函数使用了swich语句为每个运算符赋值优先级,方便在计算过程中直接调用。也建立了运算函数对每个运算符做特定的运
2、算,也是使用了swich语句。另外,最后为了能够识别一些错误,在运算过程中加入了错误的判定,比如出栈时栈空或者左右符号不符等。在编写过程中发现数栈的看栈顶没有使用过,所以删除了数栈的看栈顶。二、算法流程图中缀转后缀再计算的算法分两个流程,第一步是中缀表达式转换成后缀表达式;图1 中缀转后缀算法流程图第二步是将后缀表达式进行计算输出。图2 后缀计算算法流程图边转换边计算的算法只一个流程即可。图3 边转换边计算算法流程图三、源代码下面给出的是用中缀转后缀再计算的算法实现的程序的源代码:#include#define N 100 /*N为数栈和表达式数组容量*/#define M 50 /*M为符栈
3、和其他数组容量*/typedef struct /*定义运算符类型,level为运算符等级*/ char Type; int level;Type;typedef struct /*定义数栈*/ double stackN; int top;OdStack;typedef struct /*定义符栈*/ Type stackM;OpStack;void Init_OdStack(OdStack *s) /*定义初始化数栈*/ (*s).top=0; void OdPush(OdStack *s,double n) /*进数栈*/ if(*s).top=N-1) /*如果栈满则报错退出程序*/
4、Error(); (*s).stack(*s ).top=n; (*s).top+;double OdPop(OdStack *s) /*定义出数栈*/ if (*s).top=0) /*如果栈空则报错退出程序*/ else (*s).top-; return (*s).stack(*s).top;void Init_OpStack(OpStack *s) /*定义初始化符栈*/void OpPush(OpStack *s,Type *sign) /*定义进符栈*/ if(*s).top=M-1) /*如果栈满则报错退出程序*/ (*s).stack(*s).top=*sign;Type Op
5、Pop(OpStack *s) /*定义出符栈*/ if (*s).top=0) /*栈空则报错退出程序*/Type OpPeek(OpStack *s) /*定义看符栈顶*/ Type ren; if (*s).top=0) /*判栈空,空则赋等级0值*/ =0; return ren; return (*s).stack(*s).top-1;int Error() /*报错函数*/ printf(Error!); getch(); exit(1);int Com(char tempch) /*定义运算符等级*/ /*给不同运算符定级*/ switch (tempch) case +:-le
6、vel=1;break;*/%level=2; return level;double Oper(double a,double b,char tempch) /*定义运算过程*/ double ren; switch (tempch) /*对不同运算符执行运算并返回结果*/ren=b+a;ren=b-a;ren=b*a;ren=b/a;ren=(int)b%(int)a; /*取模运算将数取整*/double Calu(char *exp1) OdStack OdStack; /*定义数栈*/ OpStack OpStack; /*定义符栈*/ Type tempsign; /*定义Type
7、型运算符*/ char exp2N,tempexpM,tempch; /*定义后缀表达式数组exp2,整合数组tempexp,tempch为运算符*/ int index1,index2,tempindex; /*index1为主要索引,index2为次要索引,tempindex为附加索引*/ double number,a,b,c; /*number为整合数,a、b、c为运算数*/ Init_OdStack(&OdStack); /*初始化数栈*/ Init_OpStack(&OpStack); /*初始化符栈*/ index1=0; /*初始化索引,附加索引*/ index2=0; tem
8、pindex=0; tempexp0=0; /*初始化整合数组*/ while(exp1index1!=) /*处理初始表达式转化成后缀表达式*/ if(exp1index10& exp1index1) | exp1index1=. ) exp2index2=exp1index1; /*连续的数字元素不分开并依次存入后缀表达式*/ index2+; index1+; exp2index2= /*结束后用空格将其与后面的元素分开*/ if(exp1index1=|exp1index1=) /*处理运算符元素*/ =exp1index1; =Com; /*求运算符等级*/ while(OpPeek
9、(&OpStack).level= /*当栈中符的等级大于当前等级时则取出符存入后缀表达式*/ exp2index2=OpPop(&OpStack).Type; /*每两个运算符之间用空格分开*/ OpPush(&OpStack,&tempsign); /*结束后将当前运算符入栈*/ if(exp1index1=() /*如果是左括号则无条件进栈*/ =-1; /*进栈后等级为-1,以便遇到右括号出栈*/) /*右括号规则*/OpStack).level != -1) /*遇到右括号则不断出栈存入后缀表达式直到寻到左括号*/ OpPop(& /*直到遇到左括号将左括号出栈*/ else /*如
10、果输入了非法字符则报错退出程序*/=0) /*原表达式结束后对栈进行操作直到栈空*/ if(OpPeek(&OpStack).level=-1) /*如果有为用掉的左括号则报错退出程序*/ ; /*最后结束后缀表达式*/nThe Post Expression is : n %s,exp2); /* 得到后缀表达式 */ /*索引归零,开始计算结果*/ while(exp2index1 != ) /*循环直到后缀表达式结束*/ if(exp2index1 exp2index1) | exp2index1= ) /*用附加索引判断数的长度并整合入整合数组*/ tempexptempindex=e
11、xp2index1; tempindex+; tempexptempindex= /*结束整合数组*/ if( tempexp0 !) /*如果整合数组有值则转换成浮点型存入数栈*/ number = atof(tempexp); OdPush(&OdStack ,number); /*入栈后初始化整合数组和附加索引以便下次整合*/ if(exp2index1=) /*判断空格,有则跳过*/ while(exp2index1=)if(exp2index1=|exp2index1=) /*对加减乘除和取模进行运算*/ a=OdPop(& b=OdPop(& tempch=exp2index1;
12、c=Oper(a,b,tempch);OdStack,c); /*将计算结果放入数栈*/ return OdPop(&OdStack) ; /*弹出结果*/main() char strN; /*定义数组以存储表达式*/ double result; /*定义result以存储结果*/Please Enter the Expression:n scanf(%s,str); result=Calu(str); /*计算表达式并返回结果值*/nThe result is : n %f,result);下面给出的是用边转换边运算的算法实现的程序的源代码:void Init_OdStack(OdSta
13、ck *s) /*定义初始化数栈*/ double Oper(double a,double b,char tempch) /*定义运算过程*/double Calu(char *exp) /*定义计算过程,依次读入字符*/ char tempexpM,tempch; /*定义整合数组tempexp,tempch为运算符*/ int index,tempindex; /*index为索引,tempindex为附加索引*/ index=0; while(expindex!) /*执行操作直到表达式结束*/ if(expindex expindex)|expindex= tempexptempindex=expindex; index+; if(tempexp0!) /*如果整合数组有值则转换成浮点型存入数栈*/ number=atof(tempexp); if(expindex=|expindex= =expindex;/*当栈中符的等级大于当前等级时则取出符进行运算*/ tempch=OpPop(& /*直到无法运算将当前符放入栈中*/) /*如果是左括号则无条件进栈*
copyright@ 2008-2023 冰点文库 网站版权所有
经营许可证编号:鄂ICP备19020893号-2