c语言后缀表达式计算

1、一、设计思想计算算数表达式并求值，采取的共有两种方法：1. 先将算数表达式转化为后缀表达式，然后对后缀表达式进行计算。2. 对算数表达式进行直接的计算。第一种算法这种解决方案又分为两步：1. 将表达式先转化为后缀表达式的字符串数组2. 利用后缀表达式进行计算在转化过程中，第一，建立一个存符号的栈，和一个字符串数组，用来存放转化以后的表达式然后，对于得到的用户输入的字符串进行逐个的扫描，如果是数组或者小数点，则直接存放到数组中，并且在后面加入一个分隔符，如果是操作符，则和栈中的已存的进行比较，如果比栈中的操作符的优先级高，则直接入栈，如果优先级低或相等，则栈中元素出栈，存到字符串中， 然后再次检

2、查栈顶，直到栈中元素的优先级低于扫描操作符，则此操作符入栈，然后扫描下一个字符，直到遇到字符串的结束符号0 ，扫描结束。 数组中存的就是后缀表达式。得到后缀表达式后，进行计算， 要用到数值栈。首先要将字符表示的数字转化为浮点小数，然后进行扫描，遇到数值，放入栈中，遇到操作符，就从栈中取出两个数，进行计算后再放入栈中，扫描下一个，最后的计算结果就存到了栈中，直接取出栈内元素，就是计算的最后结果。第二种算发首先要建立两个栈，一个用来存放操作符，一个用来存放数值。开始对用户输入的字符串进行扫描，如果是数字字符或者小数点，则将字符转化为浮点数存到数栈里，如果是操作符，则观察符号栈， 如果栈顶元素的优先

3、级低于观察的操作符，则操作符入栈， 如果栈顶元素的优先级高于或者等于观察的操作符，则从数值栈中取出两个浮点数，从符号栈中取出栈顶的操作符，然后进行相应的数值计算，所得的结果再存到数值栈中，重复这样的操作，直到符号栈中栈顶元素的优先级低于观察的操作符，则此操作符入栈， 然后对下一个字符进行扫描。如果是左括号，则不进行优先级的比较，直接入栈，入栈后优先级为-1 。如果是右括号，则从数值栈中取两个操作数，符号栈中取出一个符号，然后进行计算后得数放入数栈中，不断进行此类操作，直到从栈中取出的是左括号为止，左括号去掉，扫描下一个。扫描结束后，计算也结束了， 计算的结果就存放在数值栈中，最后把数值栈中的数

4、取出，就是所得的计算结果。容错的算法简要：括号匹配：当扫描到左括号是，左括号直接入栈，扫描到右括号时，则左括号出栈，如果栈为空，则右括号多，如果最后栈中还有括号，则左括号多。给出错误提示。除数不为0：当扫描到 /时，就判断其后面的数字是否为0，如果为0 报错。取余运算：取余运算时，操作数判断是否为整数，不为整数报错。二、算法流程图第一种算法 : 先将表达式转化为后缀表达式，然后计算其主函数流程图为：得到用户输入存在错误调用容错函数返回计算结果无错返回直接计算的结果调用函数得到后缀表达调用直接计图 1 主函数算法流程图其中将中缀表达式转化为后缀表达式的主要流程为：如果是数字如果是操作符取得字符优

5、先级高于栈顶直接放入字符数组中与栈顶比较直接入栈如果是括号左括号判断哪类括号优先级不高于栈顶出栈存入数组中直接入栈右括号从栈中取取出不为图 2 中缀转化为后缀算法流程图后缀表达式的计算，实现的流程图为：得到后缀表达式数字字符操作符判断符号类型转化为浮点数入栈从数栈取 2 个数做相应计从数栈中取出计算结图 3 后缀表达式计算算法流程图下面介绍直接计算出结果的算法的实现：得到中缀表达式从字符串中取出一个字符数字字符操作符判断字符类型转化为浮点数入栈括号高于栈顶与栈顶比较直接入栈左括号括号类型低于栈顶直接入栈右括号取出栈顶两个从栈中取出操作符放入数作相应计算YESNO丢弃（是否为（栈空符号栈是栈非空

6、2 个数计算，将数值栈取栈顶符号与图 4 直接计算中缀表达式算法流程图三、源代码下面给出的是用先转后缀再计算和直接计算的算法实现的程序的源代码：#include/*导入需要用到的各种包*/#include#includetypedef struct/*定义结构体用来存储操作符*/char op;int level;/*/*存储字符 */存储优先级*/OpNode;typedef structOpNode op100;int top;int size; stack;void init(stack *st)/*/*/*表示栈内元素的个数定义符号栈 */初始化栈 */*/st-size=0;st-t

7、op=0;OpNode pop(stack *a)/ *出栈 */if (a-size=0)/*如果栈为空结束操作*/exit(-1);a-size-;return a-op-(a-top);/*取出栈顶元素*/void push(stack *a,OpNode op)/*入栈函数*/a-size+;a-op(a-top)+=op;OpNode top(stack *a)/*观察栈顶函数*/if (a-size=0)/*如果栈为空结束操作*/printf(stack is emptyn);exit(-1);return a-op(a-top)-1;/*只得到栈顶的值而不出栈*/typedef

8、struct/*定义数值栈*/double num100;int top;/*栈顶指针*/int size; numstack;void init2(numstack *st)/*初始化数值栈*/st-size=0;st-top=0;double pop2(numstack *a)/*数值栈出栈*/if (a-size=0)/*出栈前的判空*/exit(-1);a-size-;return a-num-(a-top);/*得到栈顶的值 */void push2(numstack *a,double num)/*入栈 */a-size+;a-num(a-top)+=num;void main()

9、/*主函数 */void change (char str,char exp);/*声明要用到的各个函数*/double CalResult(char exp);/*声明后缀表达式的计算函数*/double Directcalresult(char str);int check(char str,char chestr100);char str100,exp100,chestr100;/*str存储原算术表达式，exp 存储对应的printf(算术表达式为 :n);后缀表达式 ,chestr存储容错字符 */gets(str);if(check(str,chestr)/*调用容错函数*/pri

10、ntf(表达式错在： n);printf(%sn,str);printf(chestr);/*根据输入情况指出错误的地方*/exit(-1);change(str,exp);/*调用函数将中缀转化为后缀*/printf(后缀表达式为:%sn,exp);printf(运算结果为：%fn,CalResult(exp);/*调用函数计算后缀表达式*/printf(直接运算的结果为: %fn,Directcalresult(str);/*调用直接计算函数*/void change (char str,char ch)/*将前缀表达式转化为后缀表达式*/int i=0;/*str的索引 */int k=

11、0;char c;/*字符串中取出的放在C中*/stack st;/*定义符号栈*/OpNode op;OpNode ops;init(&st);/*初始化符号栈*/c=stri+;while (c!=0)/*对字符串进行扫描*/if ( (c=0&c=0&c0)/*再次检查栈是否为空，*/op=top(&st);elsebreak;/*为空就结束 */pop(&st);/*去掉左括号 */if (c=+|c=-)/*如果是 +- 号 */=c;=1;/*优先级为1*/if =0)push(&st,op);/*如果此时栈为空直接入栈*/elseops=top(&st);/*观察栈顶 */whi

12、le =/*如果栈顶优先级高*/ops=pop(&st);chk+=;/*将栈顶元素取出存入数组中*/if 0)ops=top(&st);/*进行判空操作，栈为空结束*/elsebreak;push(&st,op);/*此时栈顶优先级低，入栈*/if(c=*|c=/|c=%)/*如果是 */ 进行 */=c;=2;/*优先级为1*/if =0)push(&st,op);/*如果此时栈为空直接入栈*/elseops=top(&st);/*观察栈顶 */while =/*如果栈顶优先级高*/ops=pop(&st);/*将栈顶元素取出存入数组中*/chk+=;if 0)ops=top(&st);/

13、*进行判空操作，栈为空结束*/elsebreak;push(&st,op);/*此时栈顶优先级低，入栈*/c=stri+;/*索引自加检索下一个字符*/while!=0)/*最后判断栈如果不为空*/ops=pop(&st);/*取出栈内元素存入数组中*/chk+=;chk=0;/*将 0 作为结尾存入数组*/double CalResult(char exp)/*后缀表达式的计算*/char c;numstack numst;/*建立数值栈 */double d1,d2,dr;int k=0;/*后缀表达式的索引*/int i=0;/*将字符转化为浮点数的索引*/char *s;char tr

14、ans100;/*存字符表示的一段数字*/init2 (&numst);/*实现数值栈 */c=expk+;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,

15、dr);break;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,dr);break;case % :/*如果是取余操作*/d2=pop2(&numst);d1=pop2(&numst);dr=(double)(int)d1%(int)d2);/*类型转化并取余后入栈*/push2(&num

16、st,dr);break;if (c=0&c=0&c=9|c=.)transi+=c;/*将字符存入数组进行下一个的扫描*/c=expk+;transi+=0;/*将表示数字的字符串结束*/i=0;s=trans;/*将指针指向该数组*/d1=atof(s);/*利用函数将字符串转化为浮点数*/push2(&numst,d1);c=expk+;return pop2(&numst);/*最后结果将在数值栈中，取出作为返回值*/double Directcalresult(char str)/*表达式的直接计算出结果*/stack ms;/*建立符号栈 */numstack mns;/*建立数值

17、栈 */double calculate(double od1,double od2,OpNode op);int index=0;/*str的索引 */int len=strlen(str);char c;char trans100;/*存放数值的一段字符*/int i=0;/*trans的索引 */char * s;double d;OpNode tempn;/*存放当前扫描的操作符*/OpNode templn;double oda,odb,odr;double result;/*作为返回值返回结果*/init (&ms);/*实现两个栈 */init2(&mns);while(inde

18、x=0&c=0&c=/*栈顶优先级高 */templn=pop(&ms);/*取出操作数和操作符计算*/odb=pop2(&mns);oda=pop2(&mns);odr=calculate(oda,odb,templn);push2(&mns,odr);/*结算结果入栈 */if0)templn=top(&ms);/*如果栈空结束 */elsebreak;push(&ms,tempn);/*操作符入栈 */if(c=*|c=/|c=%)/*如果是 */% 操作 */=2;/*定义优先级为2*/=c;if=0)push(&ms,tempn);/*栈空直接入栈 */elsetempln=top(

19、&ms);while =/*栈顶优先级高 */templn=pop(&ms);/*取出操作数和操作符计算*/odb=pop2(&mns);oda=pop2(&mns);odr=calculate(oda,odb,templn);push2(&mns,odr);/*结算结果入栈*/if0)templn=top(&ms);elsebreak;/*如果栈空结束*/templn=top(&ms);push(&ms,tempn);/*操作符入栈 */if(c=()/*如果是左括号*/=-1;=c;/*直接入栈优先级定位-1*/push(&ms,tempn);if(c=)/*如果是右括号 */while!

20、=()/*遇到左括号结束*/templn=pop(&ms);odb=pop2(&mns);/*从数栈中取两个数，从符号栈里取操作符*/oda=pop2(&mns);odr=calculate(oda,odb,templn);/*计算出结果入栈*/push2(&mns,odr);if 0)tempn=top(&ms);elsebreak;/*如果栈空结束 */pop(&ms);/*取出左括号 */tempn=top(&ms);while(1)templn=pop(&ms);odb=pop2(&mns);/*从数栈中取两个数，从符号栈里取操作符*/oda=pop2(&mns);odr=calcul

21、ate(oda,odb,templn);/*计算出结果入栈*/push2(&mns,odr);if 0)tempn=top(&ms);/*如果栈空结束 */elsebreak;result =pop2(&mns);/*最后的结果在数值栈中返回*/return result;double calculate(double od1,double od2,OpNode op)/*已知操作符和操作数的计算*/switchcase + : return od1+od2;case - : return od1-od2;/*判断操作符是哪个执行相应计算*/case * : return od1*od2;ca

22、se / : return od1/od2;case % : return (double)(int)od1%(int)od2);return 0;/*如果上面的都没有执行返回0*/int check(char str,char chestr100)/*容错函数*/char c;char cdivide;int i=0;/*str的索引 */stack che;/*括号匹配用到的栈*/OpNode temp;int k=0;/*chestr的索引 */int isinteger(char integer100);/*%计算是判断是否是整数*/char s110;/*%操作时存储%左右的数字*/

23、char s210;int indexs1=0;/*s1s2的索引 */int indexs2=0;init (&che);int flag=0;/*0没有出错1有错*/int tag=0;c=stri;/*开始扫描 */int j;/*数组 chestr索引 */for(j=0;j0)pop(&che);/*栈不为空就取出一个左括号*/elseflag=1;printf(缺少左括号 n);/*否则提示有错*/chestri=;/*右括号下加 */if(c=/)/*判断除数是否为0*/j=0;cdivide=stri+1+j;/*取出除号后的数*/while(cdivide=0&cdivide

24、=0&stri-indexs1-1=0&stri+indexs2+10)/*如果最后栈不为空*/printf(缺少右括号 n);/*栈中还有没配对的左括号报错*/return flag;/*返回是否有错 */int isinteger(char integer100)/*判断数组内是否是整数*/int i=0;/*传过来的数组的索引*/char c;c=integeri+;while(c!=0)/*直到字符串最后扫描结束*/if(c=.)/*只要有一个字符为小数点就不是整数*/return 1;elsec=integeri+;/*扫描下一个 */return 0;四、运行结果在输入表达式没有错

25、误的情况下，可以得到两种算法的运算结果为：图 5 表达式正确时两种算法运行结果图如果表达式的输入有错误，运行结果分别如下：1. 除数为 0图 6 除数为 0 提示错误图2. 取余运算操作数不为整数：图 7 取余操作数不为整提示错误图3. 括号匹配的问题：图 8 缺少左括号提示错误图图 9 缺少右括号提示错误图五、遇到的问题及解决在编程的时候总是会有很多的意想不到的为题出现。这部分我主要遇到了如下两个问题，其内容与解决方法如下所列：将字符表示的数字转化为浮点数这个操作的主要目的就是数字是用一串字符表示的，在计算的过程中就要把字符串转化成对应的浮点数，要解决这个问题，首先查找C 语言的库函数， 其中找到一个可以将字符串转化为浮点数的函数atof()。那么就需要将数值的一串字符存入预定的数组中。利用循环到时可以得到要求，但是总