中缀转后缀表达式计算报告

1、用两种方式实现表达式自动计算目 录一、设计思想.01二、算法流程图.02三、源代码.04四、运行结果.14五、遇到的问题及解决.16六、心得体会.16一、设计思想（1）中缀表达式转后缀表达式并计算 创建一个数组存储输入的计算表达式。另创建一个数组储存将要生成的后缀表达式。创建一个栈储存操作符。对已存储的表达式数组扫描。判断当前节点，如果是操作数或.，直接加入后缀表达式中，如果是操作符，则比较前一个操作符与当前操作符的优先级。如果前一个操作符的优先级较高，则将前一个操作符加入后缀表达式中，否则将操作符压入操作符栈。如果遇到左括号(，直接入栈；如果遇到右括号),则在操作符栈中反向搜索，直到遇到匹配

2、的左括号为止，将中间的操作符依次加到后缀表达式中。当执行完以上操作，发现栈中仍有剩余操作符，则将操作符依次加到后缀表达式中。此时中缀表达式已经转换成了后缀表达式。对后缀表达式进行计算。如果后缀表达式为大于0小于9的字符，则将它转换成浮点型数据并存入数栈中。如果遇到操作符，则从数栈中提取两个数，进行相应的运算。依次进行下去，当没有运算符是，运算结束得到最后的结果。（2）直接表达式求值创建一个数组存储输入的计算表达式。创建两个栈，一个字符型的栈，一个双精度型的栈。分别用来存储字符和数。对已存储的表达式数组扫描。判断当前节点，如果是操作数和.，将字符型的操作数转换为浮点型的数后存入操作数栈。如果是操

3、作符则判断操作符的优先级。如果字符栈中已存储符号的优先级小于要存入的字符的优先级，则直接让字符入操作符栈。如果字符栈中已存储符号的优先级大于或等于要存入的字符的优先级，则取出操作符栈中的一个字符和操作数栈中的两个数进行计算，然后将结果存入操作数栈中，同上进行下去，直到字符栈中已存储符号的优先级小于要存入的字符的优先级时，将操作符存入操作符栈中。当遇到左括号(，将左括号直接存入操作符栈中。当遇到右括号)，则在操作符栈中反向搜索，并且每搜到一个字符就在操作数栈中取两个数进行相应的计算。然后，将运算结果存入到操作符栈中。如此进行下去，直到遇到左括号结束。将左括号从栈中取出。最后，如果操作符栈中还有符

4、号，就从操作符栈顶开始将操作符取出并从操作数栈顶开始取出两个数字进行计算，将结果存入操作数栈中。重复上述操作直到操作符栈中没有操作符，得到运算结果。2、 算法流程图第一种算法:先将中缀表达式转化为后缀表达式，然后计算后缀表达式流程图为：图1 中缀表达式转化为后缀表达式再计算的流程图第二种算法:直接表达式计算出结果的流程图为：图2 直接计算出结果的流程图三、源代码1.下面给出的是用先将中缀表达式转化为后缀表达式，然后计算后缀表达式算法实现的程序的源代码：#include<stdio.h> #include<stdlib.h>#include<string.h>

5、typedef struct /*定义操作符类型*/ char op; /*字符*/ int level; /*字符优先级*/OpNode;typedef struct /*定义操作符栈类型*/ OpNode op100; int top; int size; /*栈内元素的个数*/ OpStack; void init(OpStack *st) /*操作符栈初始化函数*/ st->size=0; st->top=0;OpNode pop(OpStack *a) /*操作符栈出栈函数*/ if (a->size=0) /*如果栈为空则结束操作*/ exit(-1); a-&g

6、t;size-; return a->op-(a->top); /*取出栈顶元素*/void push(OpStack *a,OpNode op) /*操作符栈入栈函数*/ a->size+; a->op(a->top)+=op;OpNode peek(OpStack *a) /*操作符栈看栈顶函数*/ if (a->size=0) /*如果栈为空则结束操作*/ printf("OpStack is emptyn"); exit(-1); return a->op(a->top)-1; /*只得到栈顶元素而不删除*/typed

7、ef 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) /*数值栈

8、入栈函数*/ a->size+; a->num(a->top)+=num;int main() /*主函数*/ void change (char str,char exp); /*声明要用到的各个函数*/ double CalResult(char exp); /*声明后缀表达式的计算函数*/ char str100,exp100; /*str存放算术表达式，exp存放对应的后缀表达式*/ printf("算术表达式为:"); gets(str); change(str,exp); /*调用函数将中缀转化为后缀*/ printf("后缀表达式为

9、:%sn",exp); printf("运算结果为： %fn",CalResult(exp); /*调用函数计算后缀表达式*/void change (char str,char exp) /*将中缀表达式转化为后缀表达式*/int i=0; /*str的索引*/int k=0;char c; /*存放字符串中取出的字符*/OpStack opst; /*定义操作符栈*/OpNode op;OpNode optemp;init(&opst); /*初始化操作符栈*/c=stri+; while (c!='0') /*对字符串进行扫描*/if

10、 ( (c>='0'&&c<='9')|c='.') /*如果字符为数字或小数点*/ while ( (c>='0'&&c<='9')|c='.') expk+=c; /*将字符直接放入数组中*/ c=stri+; expk+='|' /*在其后面放入一个分隔符*/if (c='(') /*如果字符是左括号*/ if(stri='-') expk+='0'expk+='|&

11、#39; /*输入负数处理*/ op.op='(' op.level=-1; /*入栈后优先级为-1*/ push(&opst,op); /*左括号直接入栈*/ if (c=')') /*如果字符为右括号*/ op=peek(&opst); /*首先观察栈顶*/while(op.level!=-1) /*如果不是左括号*/op=pop(&opst); /*出栈并存入数组中*/ expk+=op.op; op=peek(&opst); pop(&opst);/*去掉左括号*/if (c='+'|c='

12、-') /*如果是+或-*/ op.op=c;op.level=1; /*优先级为1*/ if (opst.size=0)push(&opst,op); /*如果此时栈为空直接入栈*/else optemp=peek(&opst); /*观察栈顶*/ while (optemp.level>=op.level) /*如果栈顶优先级高*/ optemp=pop(&opst); expk+=optemp.op; /*将栈顶元素取出存入数组中*/ if (opst.size>0) /*进行判空操作，栈为空结束*/ optemp=peek(&opst

13、); else break; push(&opst,op); /*此时栈顶优先级低，入栈*/if(c='*'|c='/'|c='%') /*如果是 * 或 / 或 % */op.op=c; op.level=2; /*优先级为2*/ if (opst.size=0)push(&opst,op); /*如果此时栈为空直接入栈*/else optemp=peek(&opst); /*观察栈顶*/ while (optemp.level>=op.level) /*如果栈顶优先级高*/ optemp=pop(&ops

14、t); /*将栈顶元素取出存入数组中*/ expk+=optemp.op; if (opst.size>0) optemp=peek(&opst); /*进行判空操作，栈为空结束*/ else break; push(&opst,op); /*此时栈顶优先级低，入栈*/c=stri+; /*索引自加检索下一个字符*/ while(opst.size!=0) /*最后判断栈如果不为空*/ optemp=pop(&opst); /*取出栈内元素存入数组中*/expk+=optemp.op; expk='0' /*将0作为结尾存入数组*/double C

15、alResult(char exp) /*后缀表达式的计算*/ char c; NumStack numst; /*建立数值栈*/ double d1,d2,dr; int k=0; /*exp的索引*/ char trans100; /*存字符表示的一段数字*/ int i=0; /*trans的索引*/ init2 (&numst); /*初始化数值栈*/ c=expk+; while (c!='0') /*开始扫描后缀表达式*/ if (c>='0'&&c<='9'|c='.') /*如果

16、是字符表示的数字*/ while(c>='0'&&c<='9'|c='.')transi+=c; /*将字符存入数组进行下一个的扫描*/c=expk+; transi+='0' /*将表示数字的字符串结束*/ i=0;d1=atof(trans); /*利用函数将字符串转化为浮点数*/push2(&numst,d1); if(c='+'|c='-'|c='*'|c='/'|c='%') /*如果是操作符*/ swit

17、ch(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,dr); break; case '*' : /*如果是乘法操作*/ d2=pop2(&numst)

18、; 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); /*类型

19、转化并取余后入栈*/ push2(&numst,dr); break; c=expk+; return pop2(&numst); /*最后结果将在数值栈中，取出作为返回值*/2.下面给出的是用中缀表达式直接进行入栈计算算法实现的程序的源代码#include<stdio.h> #include<stdlib.h>#include<string.h>typedef struct /*定义操作符类型*/char op; /*字符*/int level; /*字符优先级*/OpNode;typedef struct /*定义操作符栈类型*/ OpN

20、ode op100; int top; int size; /*栈内元素的个数*/ OpStack; void init(OpStack *st) /*操作符栈初始化函数*/ st->size=0; st->top=0;OpNode pop(OpStack *a) /*操作符栈出栈函数*/ if (a->size=0) /*如果栈为空则结束操作*/ exit(-1); a->size-; return a->op-(a->top); /*取出栈顶元素*/void push(OpStack *a,OpNode op) /*操作符栈入栈函数*/ a->si

21、ze+; a->op(a->top)+=op;OpNode peek(OpStack *a) /*操作符栈看栈顶函数*/ if (a->size=0) /*如果栈为空则结束操作*/ printf("OpStack is emptyn"); exit(-1); return a->op(a->top)-1; /*只得到栈顶元素而不删除*/typedef struct /*定义数值栈类型*/ double num100; int top; /*栈顶下标*/ int size; NumStack;void init2(NumStack *st) /*

22、数值栈初始化函数*/ 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;int main() /*主函数*/ double Directcalresult(char str); ch

23、ar str100; /*str存放算术表达式*/ printf("算术表达式为:"); gets(str); printf("直接运算的结果为: %fn",Directcalresult(str); /*调用直接计算函数*/double Directcalresult(char str) /*表达式的直接计算出结果*/ double calculate(double od1,double od2,OpNode op); OpStack opst; /*建立符号栈*/ NumStack numst; /*建立数值栈*/ int index=0; /*st

24、r的索引*/ int len=strlen(str); char c; char trans100; /*存放数值的一段字符*/ int i=0; /*trans的索引*/ double d; OpNode op; /*存放当前扫描的操作符*/ OpNode optemp; double oda,odb,odr; double result; /*作为返回值返回结果*/ init (&opst); /*初始化两个栈*/ init2(&numst); while(index<len) /*开始对用户输入的表达式进行扫描*/ c=strindex+; if(c>=

25、9;0'&&c<='9'|c='.') /*如果是数字字符或小数点*/ while(c>='0'&&c<='9'|c='.') transi+=c; /*将其存入数组扫描下一个*/ c=strindex+; transi+='0' /*扫描完一个数结束数组*/ i=0; /*索引归0*/ d=atof(trans); push2(&numst,d); /*转化为浮点数入栈*/ if(c='+'|c='-'

26、;) /*如果是+-*/ op.level=1; /*优先级设为1*/ op.op=c;if(opst.size=0) push(&opst,op); /*栈为空直接入栈*/ else optemp=peek(&opst); while (optemp.level>=op.level) /*栈顶优先级高*/ optemp=pop(&opst); /*取出操作数和操作符计算*/ odb=pop2(&numst); oda=pop2(&numst); odr=calculate(oda,odb,optemp); push2(&numst,odr

27、); /*结算结果入栈*/ if(opst.size>0) optemp=peek(&opst); /*如果栈空结束*/ else break; push(&opst,op); /*操作符入栈*/ if(c='*'|c='/'|c='%') /*如果是* / %计算*/ op.level=2; /*定义优先级为2*/ op.op=c; if(opst.size=0) push(&opst,op); /*栈空直接入栈*/ else optemp=peek(&opst); while (optemp.level&

28、gt;=op.level) /*栈顶优先级高*/ optemp=pop(&opst); /*取出操作数和操作符计算*/ odb=pop2(&numst); oda=pop2(&numst); odr=calculate(oda,odb,optemp); push2(&numst,odr); /*结算结果入栈*/ if(opst.size>0) optemp=peek(&opst); else break; /*如果栈空结束*/ optemp=peek(&opst); push(&opst,op); /*操作符入栈*/ if(c=&#

29、39;(') /*如果是左括号*/ if(strindex='-') push2(&numst,0); /*输入负数处理*/ op.level=-1; op.op=c; push(&opst,op); /*直接入栈优先级定位-1*/ if(c=')') /*如果是右括号*/ while(op.op!='(') /*遇到左括号结束*/ optemp=pop(&opst); odb=pop2(&numst); /*从数栈中取两个数，从符号栈里取操作符*/ oda=pop2(&numst); odr=ca

30、lculate(oda,odb,optemp); /*计算出结果入栈*/ push2(&numst,odr); if (opst.size>0) op=peek(&opst); else break; /*如果栈空结束*/ pop(&opst); /*取出左括号*/ op=peek(&opst); while(1) optemp=pop(&opst); odb=pop2(&numst); /*从数栈中取两个数，从符号栈里取操作符*/ oda=pop2(&numst); odr=calculate(oda,odb,optemp); /

31、*计算出结果入栈*/ push2(&numst,odr); if (opst.size>0)op=peek(&opst); /*如果栈空结束*/ else break; result =pop2(&numst); /*最后的结果在数值栈中返回*/ return result;double calculate(double od1,double od2,OpNode op) /*已知操作符和操作数的计算*/ switch(op.op) case '+' : return od1+od2; case '-' : return od1-o

32、d2; /*判断操作符是哪个执行相应计算*/ case '*' : return od1*od2; case '/' : return od1/od2; case '%' : return (double)(int)od1%(int)od2);return 0; /*如果上面的都没有执行返回0*/四、运行结果图3为先将中缀表达式转化为后缀表达式，然后计算后缀表达式的结果图4为直接计算表达式的结果五、遇到的问题及解决这部分我主要遇到了如下几个问题，其内容与解决方法如下所列：l C语言中没有string类型，所以不能直接声明string类型的变量来存

33、储输入的表达式，也不能直接声明一个字符串数组来存储截取的数字字符串。解决方法：声明一个char类型的数组或者一个指向char数组的指针变量，用来存储输入的表达式字符串。也可以使用char类型的数组来存储截取下来的数字字符串，具体存储方法如下：如果数字式单个字符，直接存入数组，然后在其后添加分隔符，如果是一系列的数字，则在字符数组中采用连续地址存储，同样后面添加分隔符，和其他字符分割开来，这样，就可以把数字字符存入到字符数组中了。l 将字符表示的数字转化为浮点数解决方法：在本程序中数值是用一串字符表示的，在计算的过程中就要把字符串转化成对应的浮点数，要解决这个问题，首先查找C语言的库函数，其中找到一个可以将字符串转化为浮点数的函数atof()。l 后缀表达式正确但结果不对解决方法：出现这种情况，首先确定后缀表达式是正确的，但在后缀表达式的计算时