C语言-后缀表达式计算

用两种方式实现表达式自动计算-1-一、设计思想计算算数表达式并求值，采取的共有两种方法：1.先将算数表达式转化为后缀表达式，然后对后缀表达式进行计算。2.对算数表达式进行直接的计算。第一种算法这种解决方案又分为两步：1.将表达式先转化为后缀表达式的字符串数组2.利用后缀表达式进行计算在转化过程中，第一，建立一个存符号的栈，和一个字符串数组，用来存放转化以后的表达式然后，对于得到的用户输入的字符串进行逐个的扫描，如果是数组或者小数点，则直接存放到数组中，并且在后面加入一个分隔符，如果是操作符，则和栈中的已存的进行比较，如果比栈中的操作符的优先级高，则直接入栈，如果优先级低或相等，则栈中元素出栈，存到字符串中，然后再次检查栈顶，直到栈中元素的优先级低于扫描操作符，则此操作符入栈，然后扫描下一个字符，直到遇到字符串的结束符号\0，扫描结束。数组中存的就是后缀表达式。得到后缀表达式后，进行计算，要用到数值栈。首先要将字符表示的数字转化为浮点小数，然后进行扫描，遇到数值，放入栈中，遇到操作符，就从栈中取出两个数，进行计算后再放入栈中，扫描下一个，最后的计算结果就存到了栈中，直接取出栈内元素，就是计算的最后结果。第二种算发首先要建立两个栈，一个用来存放操作符，一个用来存放数值。开始对用户输入的字符串进行扫描，如果是数字字符或者小数点，则将字符转化为浮点数存到数栈里，如果是操作符，则观察符号栈，如果栈顶元素的优先级低于观察的操作符，则操作符入栈，如果栈顶元素的优先级高于或者等于观察的操作符，则从数值栈中取出两个浮点数，从符号栈中取出栈顶的操作符，然后进行相应的数值计算，所得的结果再存到数值栈中，重复这样的操作，直到符号栈中栈顶元素的优先级低于观察的操作符，则此操作符入栈，然后对下一个字符进行扫描。如果是左括号，则不进行优先级的比较，直接入栈，入栈后优先级为-1。如果是右括号，则从数值栈中取两个操作数，符号栈中取出一个符号，然后进行计算后得数放入数栈中，不断进行此类操作，直到从栈中取出的是左括号为止，左括号去掉，扫描下一个。扫描结束后，计算也结束了，计算的结果就存放在数值栈中，最后把数值栈中的数取出，就是所得的计算结果。容错的算法简要：括号匹配：当扫描到左括号是，左括号直接入栈，扫描到右括号时，则左括号出栈，如果栈为空，则右括号多，如果最后栈中还有括号，则左括号多。给出错误提示。除数不为0：当扫描到'/'时，就判断其后面的数字是否为0，如果为0报错。取余运算：取余运算时，操作数判断是否为整数，不为整数报错。二、算法流程图第一种算法:先将表达式转化为后缀表达式，然后计算其主函数流程图为：用两种方式实现表达式自动计算-2-图1主函数算法流程图其中将中缀表达式转化为后缀表达式的主要流程为：图2中缀转化为后缀算法流程图返回直接计算的结果得到用户输入的中缀表达式调用容错函数存在错误报错并结束无错调用函数得到后缀表达式后缀表达式的计算返回计算结果调用直接计算的函数左括号优先级不高于栈顶取得字符并判断如果是数字或小数点直接放入字符数组中在其后加入分隔符如果是操作符与栈顶比较判断哪类括号直接入栈右括号取出不为'('从栈中取出操作符放入数组直接入栈优先级高于栈顶如果是括号出栈存入数组中用两种方式实现表达式自动计算-3-后缀表达式的计算，实现的流程图为：图3后缀表达式计算算法流程图下面介绍直接计算出结果的算法的实现：图4直接计算中缀表达式算法流程图从数栈取2个数做相应计算结果存入数栈判断符号类型得到后缀表达式数字字符操作符转化为浮点数入栈从数栈中取出计算结果作为返回值栈非空栈空低于栈顶高于栈顶NOYES左括号得到中缀表达式从字符串中取出一个字符判断字符类型数字字符操作符转化为浮点数入栈括号括号类型直接入栈右括号从栈中取出操作符是否为（丢弃（放入数组与栈顶比较直接入栈取出栈顶两个数作相应计算结果存入数栈符号栈是否为空将数值栈顶返回取栈顶符号与2个数计算，结果存入数值栈用两种方式实现表达式自动计算-4-三、源代码下面给出的是用先转后缀再计算和直接计算的算法实现的程序的源代码：#includestdio.h/*导入需要用到的各种包*/#includestdlib.h#includestring.htypedefstruct/*定义结构体用来存储操作符*/{charop;/*存储字符*/intlevel;/*存储优先级*/}OpNode;typedefstruct{OpNodeop[100];inttop;intsize;/*表示栈内元素的个数*/}stack;/*定义符号栈*/voidinit(stack*st)/*初始化栈*/{st-size=0;st-top=0;}OpNodepop(stack*a)/*出栈*/{if(a-size==0)/*如果栈为空结束操作*/{exit(-1);}a-size--;returna-op[--(a-top)];/*取出栈顶元素*/}voidpush(stack*a,OpNodeop)/*入栈函数*/{a-size++;a-op[(a-top)++]=op;}OpNodetop(stack*a)/*观察栈顶函数*/{if(a-size==0)/*如果栈为空结束操作*/{printf(stackisempty\n);exit(-1);}returna-op[(a-top)-1];/*只得到栈顶的值而不出栈*/用两种方式实现表达式自动计算-5-}typedefstruct/*定义数值栈*/{doublenum[100];inttop;/*栈顶指针*/intsize;}numstack;voidinit2(numstack*st)/*初始化数值栈*/{st-size=0;st-top=0;}doublepop2(numstack*a)/*数值栈出栈*/{if(a-size==0)/*出栈前的判空*/{exit(-1);}a-size--;returna-num[--(a-top)];/*得到栈顶的值*/}voidpush2(numstack*a,doublenum)/*入栈*/{a-size++;a-num[(a-top)++]=num;}voidmain()/*主函数*/{voidchange(charstr[],charexp[]);/*声明要用到的各个函数*/doubleCalResult(charexp[]);/*声明后缀表达式的计算函数*/doubleDirectcalresult(charstr[]);intcheck(charstr[],charchestr[100]);charstr[100],exp[100],chestr[100];/*str存储原算术表达式，exp存储对应的printf(算术表达式为:\n);后缀表达式,chestr存储容错字符'^'*/gets(str);if(check(str,chestr))/*调用容错函数*/{printf(表达式错在：\n);printf(%s\n,str);printf(chestr);/*根据输入情况指出错误的地方*/exit(-1);}change(str,exp);/*调用函数将中缀转化为后缀*/用两种方式实现表达式自动计算-6-printf(后缀表达式为:%s\n,exp);printf(运算结果为：%f\n,CalResult(exp));/*调用函数计算后缀表达式*/printf(直接运算的结果为:%f\n,Directcalresult(str));/*调用直接计算函数*/}voidchange(charstr[],charch[])/*将前缀表达式转化为后缀表达式*/{inti=0;/*str的索引*/intk=0;charc;/*字符串中取出的放在C中*/stackst;/*定义符号栈*/OpNodeop;OpNodeops;init(&st);/*初始化符号栈*/c=str[i++];while(c!='\0')/*对字符串进行扫描*/{if((c='0'&&c='9')||c=='.')/*如果字符为数字或小数点*/{while((c='0'&&c='9')||c=='.'){ch[k++]=c;/*将字符直接放入数组中*/c=str[i++];}ch[k++]='|';/*在其后面放入一个分隔符*/}if(c=='(')/*如果字符是左括号*/{op.op='(';op.level=-1;/*定义其优先级为-1*/push(&st,op);/*将左括号直接入栈*/}if(c==')')/*如果字符为右括号*/{op=top(&st);/*首先观察栈顶*/while(st.size!=0&&op.op!='(')/*如果不是左括号并且栈不为空*/{op=pop(&st);/*出栈并存入数组中*/ch[k++]=op.op;if(st.size0)/*再次检查栈是否为空，*/op=top(&st);elsebreak;/*为空就结束*/}pop(&st);/*去掉左括号*/}用两种方式实现表达式自动计算-7-if(c=='+'||c=='-')/*如果是+-号*/{op.op=c;op.level=1;/*优先级为1*/if(st.size==0){push(&st,op);/*如果此时栈为空直接入栈*/}else{ops=top(&st);/*观察栈顶*/while(ops.level=op.level)/*如果栈顶优先级高*/{ops=pop(&st);ch[k++]=ops.op;/*将栈顶元素取出存入数组中*/if(st.size0)ops=top(&st);/*进行判空操作，栈为空结束*/elsebreak;}push(&st,op);/*此时栈顶优先级低，入栈*/}}if(c=='*'||c=='/'||c=='%')/*如果是*/进行*/{op.op=c;op.level=2;/*优先级为1*/if(st.size==0){push(&st,op);/*如果此时栈为空直接入栈*/}else{ops=top(&st);/*观察栈顶*/while(ops.level=op.level)/*如果栈顶优先级高*/{ops=pop(&st);/*将栈顶元素取出存入数组中*/ch[k++]=ops.op;if(st.size0)ops=top(&st);/*进行判空操作，栈为空结束*/elsebreak;}push(&st,op);/*此时栈顶优先级低，入栈*/用两种方式实现表达式自动计算-8-}}c=str[i++];/*索引自加检索下一个字符*/}while(st.size!=0)/*最后判断栈如果不为空*/{ops=pop(&st);/*取出栈内元素存入数组中*/ch[k++]=ops.op;}ch[k]='\0';/*将\0作为结尾存入数组*/}doubleCalResult(charexp[])/*后缀表达式的计算*/{charc;numstacknumst;/*建立数值栈*/doubled1,d2,dr;intk=0;/*后缀表达式的索引*/inti=0;/*将字符转化为浮点数的索引*/char*s;chartrans[100];/*存字符表示的一段数字*/init2(&numst);/*实现数值栈*/c=exp[k++];while(c!='\0')/*开始扫描后缀表达式*/{if(c=='+'||c=='-'||c=='*'||c=='/'||c=='%')/*如果是操作符*/{switch(c){case'+':/*如果是加法操作*/d2=pop2(&numst);d1=pop2(&numst);dr=d1+d2;/*相加后入栈*/push2(&numst,dr);break;case'-':/*如果是减法操作*/d2=pop2(&numst);d1=pop2(&numst);dr=d1-d2;/*相减后入栈*/push2(&numst,d