#include<stdio.h> #include<string.h> typedef struct{char s[20][20];int top;}SQ; void copystr(char *a,char *b) {     int i=0;     do     {         b[i]=a[i];         i++;     }     while(a[i]!='\0');     b[i]='\0'; } void voidSQ(SQ *s) {     s->top=-1; } int ifempty(SQ *s) {     return(s->top==-1); } void push(SQ *S,char *c) {     if(S->top==19)         printf("over flow\n");     else     {         S->top++;         copystr(c,S->s[S->top]);     } } char *pop(SQ *S) {     if(ifempty(S))     {         printf("over flow!\n");         return(NULL);     }     else         return(S->s[S->top--]); } int judge(char *c) {     if(c[1]=='\0')         switch(c[0])     {         case '+':return(3);         case '-':return(3);         case '*':return(2);         case '/':return(2);         default:return(1);     }     else         return(1); } void write(char *a,char *b,char *c) {     strcat(a,c);     strcat(a,b); } int seek(char *c,int start) {     int signal=1;     for(start=start++;c[start]!='\0'&&signal!=0;start++)     {         if(c[start]==')')             signal--;         else if(c[start]=='(')             signal++;     }     if(signal==0)         return(start-1);     else     {         printf("输入无效式子\n");         return(-1);     } } void FB(SQ *A,SQ *B) {     for(;!ifempty(A);)     {         push(B,A->s[A->top]);         pop(A);     } } char *rewrite(char *A) {     SQ front;     SQ back;     int i,j,k,flag=0;     char *result;     char mid[20];     voidSQ(&front);     voidSQ(&back);     for(i=0;A[i]!='\0';)     {         if(A[i]=='(')         {             j=seek(A,i);             for(k=i+1;k<j;k++)             {                 mid[k-i-1]=A[k];             }             mid[j-i-1]='\0';             copystr(rewrite(mid),mid);             push(&back,mid);             i=j+1;         }         else if(A[i]!='(')         {             mid[0]=A[i];             mid[1]='\0';             push(&back,mid);             i++;         }     }     FB(&back,&front);     for(;front.top>=2;)     {         flag=0;         for(i=0;i<=front.top;i++)         {             if(judge(front.s[i])==2)             {                 flag=1;                 break;             }         }         if(flag==1)         {             for(;front.top>=2;)             {                 if(judge(front.s[front.top])==1&&judge(front.s[front.top-1])==2&&judge(front.s[front.top-2])==1)                 {                     write(front.s[front.top],front.s[front.top-1],front.s[front.top-2]);                     push(&back,front.s[front.top]);                      pop(&front);                     pop(&front);                      pop(&front);                 }                 else                 {                     push(&back,front.s[front.top]);                     pop(&front);                 }             }             FB(&front,&back);             FB(&back,&front);         }         else         {             for(;front.top>=2;)             {                 if(judge(front.s[front.top])==1&&judge(front.s[front.top-1])==3&&judge(front.s[front.top-2])==1)                 {                     write(front.s[front.top],front.s[front.top-1],front.s[front.top-2]);                     push(&back,front.s[front.top]);                      pop(&front);                     pop(&front);                      pop(&front);                 }                 else                 {                     push(&back,front.s[front.top]);                     pop(&front);                 }             }             FB(&front,&back);             FB(&back,&front);         }     }     result=front.s[front.top];     return(result); } typedef struct{char c[20];int top;}sq; int execute(char a,char b,char c) {     switch(a)     {     case('+'):return((c-48)+(b-48));     case('-'):return((c-48)-(b-48));     case('*'):return((c-48)*(b-48));     case('/'):return((c-48)/(b-48));     } } void voidsq(sq *s) {     s->top=-1; } int ifsqempty(sq *s) {     return(s->top==-1); } void pushsq(sq *s,char x) {     if(s->top==19)         printf("over flow!\n");     else     {         s->top=s->top+1;         s->c[s->top]=x;     } } void popsq(sq *s) {     if(ifsqempty(s))         printf("over flow!\n");     else         s->top--; } int just(char c) {        switch(c)     {         case ('+'):return(0);         case ('-'):return(0);         case ('*'):return(0);         case ('/'):return(0);         default:return(1);     } } void restread(sq *a,sq *b) {     for(;!ifsqempty(a);)     {         pushsq(b,a->c[a->top]);         popsq(a);     } } int calculate(char *c) {     sq rest,read;     int i,re;     voidsq(&rest);     voidsq(&read);     for(i=0;c[i]!='\0';i++)         pushsq(&read,c[i]);     for(;read.top>=2;)     {         for(;read.top>=2;)         {             if(just(read.c[read.top])==0&&just(read.c[read.top-1])==1&&just(read.c[read.top-2]) ==1)             {                 re=execute(read.c[read.top],read.c[read.top-1],read.c[read.top-2]);                 pushsq(&rest,re+48);                 popsq(&read);                 popsq(&read);                  popsq(&read);             }             else             {                 pushsq(&rest,read.c[read.top]);                 popsq(&read);             }         }         restread(&read,&rest);         restread(&rest,&read);     }     return(read.c[0]-48); } void main() {     char re[20];     char a[20];     printf("请输入算式：\n");     scanf("%s",a);     copystr(rewrite(a),re);     printf("逆波兰式：\n%s\n",re);     printf("求值结果：\n%d\n",calculate(re)); }