后缀表达式转化为前缀表达式并求值.docx

#include #include #include #define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define OK 1#define OVERFLOW -2#define ERROR 0#define TRUE 1#define FALSE 0typedef int Selemtype;typedef int Status;#define MAX 50char string1MAX; /定义两个字符串分别存放中缀表达式和后缀表达式char string2MAX;int result;typedef structSelemtype *base; /在构造之前和销毁之后，base的值为NULLSelemtype *top; /栈顶指针int stacksize; /当前分配的存储空间，以元素为单位SqStack;Status InitStack(SqStack *S);Status Push(SqStack *S,Selemtype e);Status Pop(SqStack *S,Selemtype e);Status InitStack(SqStack *S) /构造一个空栈S S-base=(Selemtype*)malloc(STACK_INIT_SIZE*sizeof(Selemtype);if(!S-base) return OVERFLOW; /存储分配失败S-top=S-base;S-stacksize=STACK_INIT_SIZE; return OK;Status Push(SqStack *S,Selemtype e) /插入元素e为新的栈顶元素if(S-top-S-base=S-stacksize) /栈满，追加存储空间 S-base=(Selemtype*)realloc(S-base,(S-stacksize+STACKINCREMENT)*sizeof(Selemtype); if(!S-base) return OVERFLOW; /存储分配失败S-top=S-base+S-stacksize;S-stacksize+=STACKINCREMENT;*S-top+=e;return OK;Status Pop(SqStack *S,Selemtype e) /若栈不空值，则删除S的栈顶元素，用e返回其值，并返回OK,否则返回ERRORif(S-top=S-base) return ERROR;e=*-S-top;return OK;Status StackEmpty(SqStack *S) /若栈S为空，则返回TRUE,否则返回FALSE if(S-top=S-base) return TRUE; else return FALSE;Selemtype GetTop(SqStack *S) /取栈顶元素并用e返回其值 Selemtype e;if(S-top=S-base) return ERROR;e=*(S-top-1);return e;void transform(char str1,char str2) /将中缀表达式转换为后缀表达式 SqStack Op; InitStack(&Op); /定义一个空栈 用来存放运算符 Push(&Op,#); Selemtype top; /取得运算符栈的栈顶元素赋值给top Selemtype e=NULL; /出栈的栈顶元素赋值给e int i=0,j=0,m;char a;m=strlen(str1); for(i=0;im;i+)a=str1i;if(0=str1i&str1i=9) /如果是操作数直接放在后缀表达式中str2j=str1i;j+;elsestr2j= ;j+;switch(a) case (: Push(&Op,a); break; case *: case /: top=GetTop(&Op);if(top=*)|(top=/) Pop(&Op,e);str2j=top;j+; /比其高，现将栈顶运算符出栈，再进栈。Push(&Op,a);elsePush(&Op,a); break; case +: case -: top=GetTop(&Op); if(top=+|top=-|top=*|top=/) Pop(&Op,e); str2j=top;j+; Push(&Op,a); else Push(&Op,a); break; case ): top=GetTop(&Op); Pop(&Op,e); while(top!=() str2j=top;j+;top=GetTop(&Op);Pop(&Op,e); break;top=GetTop(&Op);Pop(&Op,e); while(top!=#) str2j=top;j+;top=GetTop(&Op); Pop(&Op,e); str2j=top; printf(转化后的后缀表达式为:%sn,str2); Selemtype counttem(char str) /计算后缀表达式的值SqStack S;InitStack(&S);int len;len=strlen(str);Selemtype A10;int m,n,p,e=NULL,k,E;int i,j,l,ch,zh; /zh为字符型转化为的整形数 for(i=0;ilen;i+)if(0stri&stri=9)k=i;j=0;while(0=strk&strk=9) /将字符型的一串数字转化为整形Aj=strk-48;j+;k+;ch=Aj-1; E=1;for(l=1;lj;l+) E=10*E;zh=Aj-l-1*E;ch+=zh;Push(&S,ch);i=k-1;else if(stri=+|stri=-|stri=*|stri=/) m=GetTop(&S);Pop(&S,e);n=GetTop(&S);Pop(&S,e);switch (stri)case+:p=m+n; break;case-:p=n-m; break;case*:p=n*m; break;case/:p=n/m; break;Push(&S,p);else if(stri= ) else if(stri=#) result=GetTop(&S); printf(表达式的运算结果为：%dn,result);return res