数据结构实验之栈二：一般算术表达式转换成后缀式

 

Time Limit: 1000ms   Memory limit: 65536K  有疑问？点这里^_^

题目描述

对于一个基于二元运算符的算术表达式，转换为对应的后缀式，并输出之。

输入

输入一个算术表达式，以‘#’字符作为结束标志。

输出

输出该表达式转换所得到的后缀式。

示例输入

a*b+(c-d/e)*f#

示例输出

ab*cde/-f*+

提示

       所谓 后缀式表达式 即是：计算机内部对算式的处理先后顺序式！

      此题写了半个小时哈，数据结构课本里的代码实在是难看。故，本人只是参看了算法，自己手敲的代码，运用栈的思想，

      我的代码需要注意的地方是：当遇到 ' ) '时，该怎么搞？！！

      本人的一贯做法，对于栈只是我用来存储的数组，每次我都是用一个e的下表指针来进行数据处理，遇到该出栈的数据，

      我就把它给赋值掉，或者改变指针的位置，访问不到那个数据哈！

      将中缀式转换为后缀式，需要考虑运算符的优先性。比如：a+b*c 不能转换为：ab+c*,这是错误的。

应该转换成：abc*+  这样才是对的。*的优先级大于+，所以意味着先做*运算，再做+运算。

 

#include 
        
         #include 
         
          char a[1000];char s[1000];int main(){    int i, j, e, k;    int len;    while(scanf("%s", a)!=EOF )    {        len = strlen(a);        memset(s, '\0', sizeof(s));        e = 0;        i = 0;        while( i < len-1 ) //去掉#字符的长度        {            if( a[i]>='a' && a[i]<='z') //如果是字符的话            {                printf("%c", a[i] );            }            else //如果是运算符            {                if(e==0) //此时栈为空                {                    s[e++] = a[i]; //入栈                }                else if( e>0 ) //如果栈里已有运算符出现了                {                    if(a[i] == '(') //如果当前读到的是'('                    {                        s[e++] = a[i]; //进栈 //貌似不会影响什么                    }                    if(a[i] == '+') //如果遇到的是+，运算优先级低（+-*/ 均可在其前面运算）                    {                        if( s[e-1]=='(' ) // 如果前面是'('                        {                            s[e++] = a[i]; //继续压进栈                        }                        else if(s[e-1]=='*' || s[e-1]=='/' ||s[e-1]=='+' || s[e-1]=='-' )                        {                            printf("%c", s[e-1] ); //如果是这些字符，直接输出，它们的优先级都>=(+)                            s[e-1] = a[i];                        }                    }                    if(a[i] == '-') //如果当前遇到的运算符是-                    {                        if( s[e-1]=='(' ) //判断前面是不是'('                        {                            s[e++] = a[i]; //如果是 直接将当前运算符压进栈                        }                        else if(s[e-1]=='-' || s[e-1]=='*' || s[e-1]=='/' || s[e-1]=='+' )                        {                            printf("%c", s[e-1] ); //如果是这些运算符的话                            s[e-1] = a[i];  // 说明前面的运算符不比后面的 低级，也就是说前面的可以输出                        }                    }                    if( a[i] == '*') // 他如果当前遇到的是*                    {                        if(s[e-1]=='+' || s[e-1]=='-' || s[e-1]=='(' ) //如果遇到的是这些字符                        {                            s[e++] = a[i];  //因为它们比较低级或者是'(',不能输出它们，将*压进栈                        }                        else if(s[e-1]=='*' || s[e-1]=='/' ) // 如果是这些运算符，>=(*)的优先级                        {                            printf("%c", s[e-1] ); // 可以输出                            s[e-1] = a[i];                        }                    }                    if( a[i] == '/') // 和*运算符的做法一致                    {                        if(s[e-1]=='+' || s[e-1]=='-' || s[e-1]=='(' )                        {                            s[e++] = a[i] ;                        }                        else if(s[e-1]=='*' || s[e-1]=='/' )                        {                            printf("%c", s[e-1] );                            s[e-1] = a[i];                        }                    }                    if( a[i] == ')') // 如果是右括号呢？？？                    {                        for(j=e-1; j>=0; j-- )                        {                            if(s[j]=='(')                            {                                e = j;                                break;                            }                            else                            {                                printf("%c", s[j] ); //逆序 从右括号的位置 一直输出到 左括号的位置                                                     //但是左右括号不输出                            }                        }                    }                }            }            i++;        }        for(k=e-1; k>=0; k--)        {            printf("%c", s[k] );        }        printf("\n");    }    return 0;}
         
        

　 　

          

        STL 的写法：

              

#include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             using namespace std;int main(){ string s; int len; int i, j; cin>>s; len=s.size(); stack
             
              q; for(i=0; i
              
               ='a' && s[i]<='z') { cout<
              
             
            
           
          
         
        
       

　　

 

       一开始使用switch语句写的，结果运行错误，读者朋友可以给我指正哈！

       此乃bug版本，哈哈哈哈哈哈哈哈哈哈！！！

#include 
       
        #include 
        
         char a[1000];char s[1000]; void main(){    int i, j, e, k;    int len;    while(scanf("%s", a)!=EOF)    {        len = strlen(a);        memset(s, 0, sizeof(s));        e = 0;        i = 0;        while( i < len )        {            if( a[i]>='a' && a[i]<='z')            {                printf("%c", a[i] );            }            else            {                if(e==0)                {                    s[e++] = a[i];                }                else if(e>0)                {                    switch( a[i] )                    {                        case '(':                            {                                s[e++] = a[i];                            }                        case '+':                            {                                if( s[e-1]=='(' )                                {                                    s[e++] = a[i];                                }                                else if(s[e-1]=='*' || s[e-1]=='/' ||s[e-1]=='+' || s[e-1]=='-' )                                {                                    printf("%c", s[e-1] );                                    s[e-1] = a[i];                                }                            }                        case '-':                            {                                if( s[e-1]=='(' )                                {                                    s[e++] = a[i];                                }                                else if(s[e-1]=='-' || s[e-1]=='*' || s[e-1]=='/' || s[e-1]=='+' )                                {                                    printf("%c", s[e-1] );                                    s[e-1] = a[i];                                 }                            }                        case '*':                            {                                if(s[e-1]=='+' || s[e-1]=='-' || s[e-1]=='(' )                                {                                    s[e++] = a[i];                                }                                else if(s[e-1]=='*' || s[e-1]=='/' )                                {                                    printf("%c", s[e-1] );                                    s[e-1] = a[i];                                }                            }                        case '/':                            {                                if(s[e-1]=='+' || s[e-1]=='-' || s[e-1]=='(' )                                {                                    s[e++] = a[i] ;                                }                                else if(s[e-1]=='*' || s[e-1]=='/' )                                {                                    printf("%c", s[e-1] );                                    s[e-1] = a[i];                                }                            }                        case ')':                            {                                for(j=e-1; j>=0; j-- )                                {                                    if(s[j]=='(')                                    {                                        e = j;                                        break;                                    }                                    else                                    {                                        printf("%c", s[j] );                                    }                                }                            }                    }                }            }            i++;        }        for(k=e-1; k>=0; k--)        {            printf("%c", s[k] );        }        printf("\n");    }}