简单的中缀转前缀表达式并计算的程序

#include <stdio.h> #include <stdlib.h> #include<math.h> #define Max 100 typedef char ElementType; typedef double ElementType1;//用于计算前缀表达式 typedef struct stk { ElementType data; struct stk* next; }STK; STK* CreateStack() { STK*s; s=(STK*)malloc(sizeof(STK)); s->next=NULL; return s; } int isEmpty(STK*s) { return (s->next==NULL); } void Push(STK *s , ElementType e) { STK * t; t=(STK*)malloc(sizeof(STK)); t->data=e; t->next=s->next; s->next=t; } int Pop(STK*s,ElementType *e) { STK*t; if(!isEmpty(s)) { t=s->next; *e=t->data; s->next=t->next; free(t); return 1;//表示弹出成功 } else return 0;//返回0表示栈空 } int GetTop(STK*s,ElementType *e) { if(isEmpty(s)) return 0;//获取失败 else{ STK* t; t=s->next; *e=t->data; return 1; } } void trans(char *mid,char *rexp) { char temp[Max]; char exp[Max]; char e; int j=0,count=0; int k=0;// int p=0; int i=0; STK*s; s=CreateStack();//构建符号栈 while(*mid!='\0')//从右至左扫描 { mid++; count++; } --mid;--count;//移到右边第一个字符 for(;count>=0;count--) { temp[k]=*mid; mid--;k++; } temp[k]='\0';//将mid逆序保存在temp中用于扫描 while(temp[p]!='\0') { switch(temp[p]) { case ')': Push(s,temp[p]); p++; break; case '(': Pop(s,&e);//弹出栈顶符号 while(e!=')')//在遇到‘）’之前将符号都弹出 { exp[j++]=e; Pop(s,&e); } p++;//继续检查下一个字符 break; case '+': case '-'://遇到符号的时候，查看栈顶元素优先级，优先级比它高的都弹出 while(!isEmpty(s))//比较优先级,能比较的前提是栈不空 { GetTop(s,&e); if(e=='*'||e=='/')//优先级高的话 { exp[j++]=e; Pop(s,&e); } else break; }//弹出所有优先级高的之后压栈 Push(s,temp[p]); p++; break; case '*': case '/'://这两个是优先级最高的 Push(s,temp[p]); p++; break; default: while(temp[p]>='0'&&temp[p]<='9') { exp[j++]=temp[p]; p++; } exp[j++]='#';//分割数字 } } //将剩下的符号写入 while(!isEmpty(s)) { Pop(s,&e); exp[j++]=e; } exp[j--]='\0'; //将字符串逆序保存 for(i=0;j>=0;j--) { rexp[i]=exp[j]; i++; } rexp[i]='\0'; free(s); } typedef struct stk1 { ElementType1 data; struct stk1* next; }STK1; STK1* CreateStack1() { STK1*s; s=(STK1*)malloc(sizeof(STK1)); s->next=NULL; return s; } int isEmpty1(STK1*s) { return s->next==NULL; } void Push1(STK1*s,ElementType1 e) { STK1*t; t=(STK1*)malloc(sizeof(STK1)); t->data=e; t->next=s->next; s->next=t; } int Pop1(STK1*s,ElementType1 *e) { if(!isEmpty1(s)) { STK1 *t; t=s->next; *e=t->data; s->next=t->next; free(t); return 1; } else return 0; } int GetTop1(STK1*s,ElementType1 *e) { if(!isEmpty1(s)) { STK1*t; t=s->next; *e=t->data; return 1; } else return 0; } double compute(char exp[]) { STK1*s; s=CreateStack1(); double a,b,c,d=0;double temp=0; //逆序扫描，所以先把顺序调整一下; int i=0,j=0; double comput=0; char invers[Max]; while(exp[i]!='\0') { i++; } i--; for(;i>=0;i--) { invers[j]=exp[i]; j++; } invers[j]='\0'; j=0;//复位 while(invers[j]!='\0') { switch(invers[j]) { case '+': Pop1(s,&a); Pop1(s,&b); c=a+b; Push1(s,c); j++; break; case '-': Pop1(s,&a); Pop1(s,&b); c=a-b; Push1(s,c); j++; break; case '*': Pop1(s,&a); Pop1(s,&b); c=a*b; Push1(s,c); j++; break; case '/': Pop1(s,&a); Pop1(s,&b); if(b==0) { printf("除数不能为0!"); exit(0); break; } else{ c=a/b; Push1(s,c); } j++; break; default: if(invers[j]>='0'&&invers[j]<='9') { d=0; comput=0; temp=0; while(invers[j]>='0'&&invers[j]<='9') { d=invers[j]-'0'; d=d*pow(10,comput)+temp; temp=d; comput++; j++; } Push1(s,d); } else { j++;//若为其他符号则跳过 } break; } } Pop1(s,&a); return a; } int main() { char *mid ="(20+5)*3-5"; char exp[Max]; trans(mid,exp); printf("%s",exp); double a; a=compute(exp); printf("\n 结果是%f",a); return 0; }

trans函数用于中缀转换前缀。利用了STK 符号栈 compute函数用于根据前缀表达式求值，利用了STK1数字栈，考虑到除法问题，data类型是double

最难处理的还是字符转数字那部分，不仔细思考有些用例就过不去了。