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

1、 数据结构作业报告 逆波兰式的计算 一 题目内容 逆波兰式也叫后缀表达式(将运算符写在HYPERLINK http:/baike./v485684.htm?ch=ch.bk.innerlink操作数之后) 如：我们平时写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、缀表达式，运算符置于两个操作数之后。运算实应从前往后依次读出两个运算数，与这两个运算数之后的运算符进行计算，然后再从前往后提取两个操作数，再从之后提取对应的运算符，直到计算完毕。这与栈的功能相一致，建立一个栈结构，将表达式的各个字符依次读取，若是数字则放入栈中，若是操作符则从栈中提取两个数字进行运算，将运算结果加入到栈中，直至运算完毕。三程序描述首先定义相关数值，建立栈结构的数据类型typedef structSElemType *base;SElemType *top;int stacksize;SqStack;之后是各个对栈的操作函数 Status InitStack(SqStack &S

3、)S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;/建立空栈Status Push(SqStack &S,SElemType e)if(S.top-S.base=S.stacksize)S.base=(SElemType*)malloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemTYpe);if(!S.base)exi

4、t(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;return OK;/将栈顶元素输出到元素e之中Status Pop(SqStack &S,SElemType e) if(S.top=S.base)return ERROR;e=*-S.top;return OK;/将元素e加入到栈之中程序最重要的操作函数如下（进行计算操作）：char CalVal_InverPoland(char Buffer)Stack Opnd;InitStack(Opnd);int i=0;char c;ElemTyp

5、e e1,e2;while(Bufferi!=#) if(!IsOperator(Bufferi)Push(Opnd,Bufferi);elsePop(Opnd,e2);Pop(Opnd,e1);c=Cal(e1,Bufferi,e2);Push(Opnd,c);i+;return c;while循环中是对表达式各字符的判断和计算过程，如果是数字则加入栈中，是操作符则从栈中提取两数据进行计算，之后将计算结果加入到栈中，直至遇到表达式结束标志#则结束运算，栈中数字则为计算结果。Status IsOpertor(char c)char *p=#+-*/;while(*p)if(*p=c)retur

6、n TRUE;p+;return FALSE;/数字操作符判断函数char Cal(char c1,char op,char c2)int x,x1,x2;char ch10;ch0=c1;ch1=0;x1=atoi(ch);ch0=c2;ch1=0;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);return ch0;/计算函数如计算1+6-4，则逆波兰式式为16+4-，输入

7、16+4-#，计算结果应为3，运行结果如下四源代码#include #include #include #include #define SElemType char#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef int Status;#define OVERFLOW -1#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0typedef structSElemType *base;SElemType *top;int stacksize;SqStack;Stat

8、us InitStack(SqStack &S)S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;Status Push(SqStack &S,SElemType e)if(S.top-S.base=S.stacksize)S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemT

9、ype);if(!S.base)exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;return OK;Status Pop(SqStack &S,SElemType &e) if(S.top=S.base)return ERROR;e=*-S.top;return OK;Status IsOperator(char c)char *p=#+-*/;while(*p)if(*p=c)return TRUE;p+;return FALSE;char Cal(char c1,char op,ch

10、ar c2)int x,x1,x2;char ch10;ch0=c1;ch1=0;x1=atoi(ch);ch0=c2;ch1=0;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);return ch0;char CalVal_InverPoland(char Buffer)SqStack Opnd;InitStack(Opnd);int i=0;char c;SElemType e1,e2;while(Bufferi!=#) if(!IsOperator(Bufferi)Push(Op