y33.cpp

利用堆栈进行中缀表达式转后缀表达式的转换。

#include<stdio.h>
#include <string.h>
#define max 100
char expression[max],result[max];

int m(char c)
{
    switch(c)
    {
     case '+':return(0);break;
     case '-':return(1);break;
     case '*':return(2);break;
     case '/':return(3);break;
     case '(':return(4);break;
     case ')':return(5);break;
     case '#':return(6);
     }
}
     
void scan(char expression[max])
{
     int i,top1,top2,a,b,k,j;
     char ovs[max][max];
     char ops[max],ex[max];
     char f[7][7]={{'>','>','<','<','<','>','>'},
                   {'>','>','<','<','<','>','>'},
                   {'>','>','>','>','<','>','>'},
                   {'>','>','>','>','<','>','>'},
                   {'<','<','<','<','<','=','x'},
                   {'>','>','>','>','x','>','>'},
                   {'<','<','<','<','<','x','='}
                  };
     strcat(expression,"#");
     ops[0]='#';
     top1=0;
     top2=1;
     for(i=0;i<strlen(expression);i++)
     { j=0;
       while(expression[i]>='0' && expression[i]<='9')
       {ex[j]=expression[i];j++;i++;}
       if(j!=0){ex[j]=' ';ex[j+1]='\0';strcpy(ovs[top1],ex);top1++;}


       {a=m(ops[top2-1]);
        b=m(expression[i]);
        while(f[a][b]=='>')
        {
         top1--;
         strcat(ovs[top1-1],ovs[top1]);
         k=strlen(ovs[top1-1]);
         top2--;
         ovs[top1-1][k]=ops[top2];
         ovs[top1-1][k+1]='\0';
         a=m(ops[top2-1]);
        b=m(expression[i]);
        }
         if(f[a][b]=='=')top2--;
         else {ops[top2]=expression[i];top2++;}
        }
       }

     strcpy(result,ovs[0]);
}
int main()
{
    printf("input a expression:");
    gets(expression);
    scan(expression);
    puts(result);
}