SDUTOJ 2484 算術表達式的轉換（棧）

SDUTOJ 2484 算術表達式的轉換（棧）

算術表達式的轉換

Time Limit: 1000MS Memory limit: 65536K

題目描述

小明在學習了數據結構之後，突然想起了以前沒有解決的算術表達式轉化成後綴式的問題，今天他想解決一下。 因為有了數據結構的基礎小明很快就解出了這個問題，但是他突然想到怎麼求出算術表達式的前綴式和中綴式呢？小明很困惑。聰明的你幫他解決吧。

輸入

輸入一算術表達式，以\'#\'字符作為結束標志。（數據保證無空格,只有一組輸入）

輸出

輸出該表達式轉換所得到的前綴式 中綴式 後綴式。分三行輸出，順序是前綴式 中綴式 後綴式。

示例輸入

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

示例輸出

+*ab*-c/def
a*b+c-d/e*f
ab*cde/-f*+

提示

只要明白了算術表達式的前綴式，中綴式，後綴式是怎麼得到的就可以寫出來了，只是用數組模擬棧很麻煩...

來源

示例程序

#include
#include
#include
#include
#include

using namespace std;

int bijiao(char ch)
{
    if(ch=='+'||ch=='-')
    {
        return 1;
    }
    if(ch=='*'||ch=='/')
    {
        return 2;
    }
    if(ch=='(')
    {
        return 3;
    }
}

void qian(char str[])
{
    char a[10100];
    char b[10010];
    char q[11000];
    int pp = 0;
    int k = 0;
    int h = 0;
    int len = strlen(str);
    for(int i=len-2; i>=0; i--)
    {
        a[k++] = str[i];
    }
    a[k] = '#';
    //a[k] = '\0';
    for(int i=0; a[i]!='#'; i++)
    {
        if((a[i]>='a' && a[i]<='z') || (a[i]>='A' && a[i] <='Z'))
        {
            b[h++] = a[i];
        }
        else
        {
            if(a[i] == ')')
            {
                q[++pp] = a[i];
            }
            else if(a[i] == '(')
            {
                for(; q[pp]!=')'; pp--)
                {
                    b[h++] = q[pp];
                }
                pp--;
            }
            else
            {
                if(bijiao(a[i]) < bijiao(q[pp]))
                {
                    if(q[pp] == ')')
                    {
                        q[++pp] = a[i];
                    }
                    else
                    {
                        b[h++] = q[pp];
                        q[pp] = a[i];
                    }
                }
                else
                {
                    q[++pp] = a[i];
                }
            }
        }
    }
    while(pp!=0)
    {
        b[h++] = q[pp];
        pp--;
    }
    for(int i=h-1; i>=0; i--)
    {
        printf("%c",b[i]);
    }
    printf("\n");
}

void zhong(char str[])
{
    for(int i=0; str[i]!='#'; i++)
    {
        if(str[i]!='(' && str[i]!=')')
        {
            printf("%c",str[i]);
        }
    }
    printf("\n");
}

void hou(char str[])
{
    char qq[100100];
    int p = 0;
    for(int i=0; str[i]!='#'; i++)
    {
        if((str[i]>='A' && str[i]<='Z') || (str[i]>='a' && str[i]<='z'))
        {
            printf("%c",str[i]);
        }
        else
        {
            if(p == 0)
            {
                qq[++p] = str[i];
            }
            else if(str[i] == '(')
            {
                qq[++p] = str[i];
            }
            else if(str[i] == ')')
            {
                for(; qq[p]!='('; p--)
                {
                    printf("%c",qq[p]);
                }
                p--;
            }
            else
            {
                if(bijiao(str[i]) <= bijiao(qq[p]))
                {
                    if(qq[p] == '(')
                    {
                        qq[++p] = str[i];
                    }
                    else
                    {
                        printf("%c",qq[p]);
                        qq[p] = str[i];
                    }
                }
                else
                {
                    qq[++p] = str[i];
                }
            }
        }
    }
    while(p!=0)
    {
        printf("%c",qq[p]);
        p--;
    }
    printf("\n");
}

int main()
{
    char str[10010];
    while(scanf("%s",str)!=EOF)
    {
        //printf("str = %s\n",str);
        qian(str);
        zhong(str);
        hou(str);
    }
    return 0;
}