对逆波兰式计算的程序设计

《对逆波兰式计算的程序设计》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构作业报告逆波兰式的计算一题目内容逆波兰式也叫后缀表达式(将运算符写在操作数之后)　　如：我们平时写a+b，这是中缀表达式，写成后缀表达式就是：ab+　　(a+b)*c-(a+b)/e的后缀表达式为：　　(a+b)*c-(a+b)/e　　→((a+b)*c)((a+b)/e)-　　→((a+b)c*)((a+b)e/)-　　→(ab+c*)(ab+e/)-　　→ab+c*ab+e/-计算给出的逆波兰式（假设条件：逆波兰表达式由单字母变量和双目四则运算符构成，以’#‘作为结束标志）。二题目分析逆波兰式即后缀表达式，运算符置于两个操作数之后。运算实应从前往后依次读出两个运算数，与这两个运

2、算数之后的运算符进行计算，然后再从前往后提取两个操作数，再从之后提取对应的运算符，直到计算完毕。这与栈的功能相一致，建立一个栈结构，将表达式的各个字符依次读取，若是数字则放入栈中，，若是操作符则从栈中提取两个数字进行运算，将运算结果加入到栈中，直至运算完毕。三程序描述首先定义相关数值，建立栈结构的数据类型typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;之后是各个对栈的操作函数StatusInitStack(SqStack&S){S.base=(SElemType*)malloc(STACK_INIT_SIZE

3、*sizeof(SElemType));if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}//建立空栈StatusPush(SqStack&S,SElemTypee){if(S.top-S.base>=S.stacksize){S.base=(SElemType*)malloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemTYpe));if(!S.base)exit(OVERFLOW);S.top=S.base+S.stacksize;

4、S.stacksize+=STACKINCREMENT;}*S.top++=e;returnOK;}//将栈顶元素输出到元素e之中StatusPop(SqStack&S,SElemTypee){if(S.top==S.base)returnERROR;e=*--S.top;returnOK;}//将元素e加入到栈之中程序最重要的操作函数如下（进行计算操作）：charCalVal_InverPoland(charBuffer[]){StackOpnd;InitStack(Opnd);inti=0;charc;ElemTypee1,e2;while(Buffer[i]!='#'){if(!Is

5、Operator(Buffer[i])){Push(Opnd,Buffer[i]);}else{Pop(Opnd,e2);Pop(Opnd,e1);c=Cal(e1,Buffer[i],e2);Push(Opnd,c);}i++;}returnc;}while循环中是对表达式各字符的判断和计算过程，如果是数字则加入栈中，是操作符则从栈中提取两数据进行计算，之后将计算结果加入到栈中，直至遇到表达式结束标志’#’则结束运算，栈中数字则为计算结果。StatusIsOpertor(charc){char*p="#+-*/";while(*p){if(*p==c)returnTRUE;p++;}re

6、turnFALSE;}//数字操作符判断函数charCal(charc1,charop,charc2){intx,x1,x2;charch[10];ch[0]=c1;ch[1]='';x1=atoi(ch);ch[0]=c2;ch[1]='';x2=atoi(ch);switch(op){case'+':x=x1+x2;break;case'-':x=x1-x2;break;case'*':x=x1*x2;break;case'/':x=x1/x2;break;default:break;}itoa(x,ch,10);returnch[0];}//计算函数如计算‘1+6-4’，则逆

7、波兰式式为‘16+4-’，输入‘16+4-#’，计算结果应为3，运行结果如下四源代码#include#include#include#include#defineSElemTypechar#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10typedefintStatus;#defineOVER