산술 식 변환 2484 SDUT

산술 식 의 변환
Time Limit: 1000 ms Memory Limit: 65536 KiB
Submit Statistic Discuss
Problem Description
샤 오 밍 은 데이터 구 조 를 공부 한 후에 예전 에 해결 하지 못 했 던 산술 표현 식 이 접미사 식 으로 바 뀌 었 던 문제 가 갑자기 생각 났 다. 오늘 은 그 가 해결 하고 싶 어 한다.
   데이터 구조의 기초 가 있 기 때문에 샤 오 밍 은 곧 이 문 제 를 풀 었 다. 그러나 그 는 갑자기 산술 식 의 접두사 식 과 접두사 식 을 어떻게 구 해 야 할 지 생각 했다.샤 오 밍 은 매우 곤혹스럽다.똑똑 한 니 가 해결 해 줘.
Input
 산술 표현 식 을 입력 하 십시오. \ \ # \ 문 자 를 끝 표지 로 합 니 다.(데 이 터 는 빈 칸 이 없고 한 그룹 만 입력 할 수 있 습 니 다)
Output
 이 표현 식 을 출력 하여 얻 은 접두사 접두사 식 접 두 사 를 변환 합 니 다.세 줄 로 나 누 어 출력 하고 순 서 는 접두사 식 접두사 식 입 니 다.
Sample Input

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

Sample Output

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

Hint
 
Source
방법 1:

#include
#include
 
char a[1000],ls[1000], la[1000];
int cmp(char z)
{
    if(z == '+' || z == '-') return 1;
    if(z == '*' || z == '/') return 2;
    if(z == ')') return 3;
    if(z == '(') return 4;
}
 
int main()
{
    scanf("%s",a);
 
    int i = 0,k = 0, c = 0;
    int str  = strlen(a);
    str = str - 2;
    while(str >= 0)
    {
        if(a[str] >= 'a' && a[str] <= 'z')
        {
            la[c++] = a[str];
 
        }
        else
        {
            if(k == 0 )
            {
                ls[k++] = a[str];
            }
            else
            {
                if(cmp(ls[k-1]) <= cmp(a[str]))
                {
                    if(a[str] == '(')
                    {
                        k = k - 1;
                        for(; ls[k] != ')'; k--)
                        {
                            la[c++] = ls[k];
                        }
                    }
                    else
                    {
                        ls[k++] = a[str];
                    }
                }
                else
                {
                    if(ls[k-1] != ')')
                    {
                        la[c++] = ls[k-1];
                        ls[k-1] = a[str];
                    }
                    else
                        ls[k++] = a[str];
                }
            }
        }
        str--;
    }
    c = c- 1;
    for(i = 0; i < k; i++)
    {
        printf("%c",ls[i]);
    }
    for(; c >= 0; c--)
        printf("%c",la[c]);
    printf("
");
    for(i = 0; a[i] != '#'; i++)
    {
        if(a[i] != '(' && a[i] != ')')
        {
            printf("%c",a[i]);
        }
    }
    printf("
");
    k = 0;
    memset(ls,0,sizeof(ls));
    for(i = 0; a[i] != '#'; i++)
    {
        if(a[i] >= 'a' && a[i] <= 'z')
        {
            printf("%c",a[i]);
        }
        else
        {
            if(k == 0)
            {
                ls[k++] = a[i];
            }
            else
            {
                if(cmp(ls[k-1]) >= cmp(a[i]))
                {
                    if(ls[k-1]!= '(')
                    {
                        printf("%c",ls[k-1]);
                        ls[k-1] = a[i];
                    }
                    else
                    {
                        ls[k++] = a[i];
                    }
                }
                else
                {
                    if(a[i] == ')')
                    {
                        k = k-1;
                        for(; ls[k]!='('; k--)
                        {
                            printf("%c",ls[k]);
                        }
                    }
                    else
                    {
                        ls[k++] = a[i];
                    }
                }
            }
 
        }
    }
    k  = k - 1;
    while(k>=0)
    {
        printf("%c",ls[k]);
        k--;
    }
    printf("
");
 
    return 0;
}

방법 2:

#include 
#include 
struct node
{
    char s;
    struct node *l,*r;
};
char sa[100],sb[100],sc[100];
int p;
void first(struct node *q)
{
    if(q==NULL)
    {
        return ;
    }
    printf("%c",q->s);
    first(q->l);
    first(q->r);
}
void infix(struct node *q)
{
    if(q==NULL)
    {
        return ;
    }
    infix(q->l);
    printf("%c",q->s);
    infix(q->r);
}
void postfix(struct node *q)
{
    if(q==NULL)
    {
        return ;
    }
    postfix(q->l);
    postfix(q->r);
    printf("%c",q->s);
}
void h()
{
    int x=0,y=0;
    for(p=0; sa[p]!='#'; p++)
    {
        if(sa[p]>='a'&&sa[p]<='z')///     
        {
            sb[x]=sa[p];
            x++;
        }
        else if(sa[p]=='+'||sa[p]=='-')
        {
            while(y!=0&&sc[y-1]!='(')
            {
                sb[x]=sc[y-1];
                x++;
                y--;
            }
            sc[y]=sa[p];
            y++;
        }
        else if(sa[p]=='*'||sa[p]=='/')
        {
            while(y!=0&&(sc[y-1]=='*'||sc[y-1]=='/'))
            {
                sb[x]=sc[y-1];
                x++;
                y--;
            }
            sc[y]=sa[p];
            y++;
        }
        else if(sa[p]=='(')
        {
            sc[y]=sa[p];
            y++;
        }
        else if(sa[p]==')')
        {
            while(sc[y-1]!='(')
            {
                sb[x]=sc[y-1];
                x++;
                y--;
            }
            y--;
        }
    }
    while(y!=0)
    {
        sb[x]=sc[y-1];
        x++;
        y--;
    }
    sb[x]='\0';
}
int main()
{
    int d=0,i;
    scanf("%s",sa);
    h();
    struct node *po[100]={NULL},*pi;
    for(i=0;i
='a'&&sb[i]<='z')
        {
            pi=(struct node *)malloc(sizeof(struct node));
            pi->s=sb[i];
            pi->l=NULL;
            pi->r=NULL;
            po[d]=pi;
            d++;
        }
        else
        {
            pi=(struct node *)malloc(sizeof(struct node));
            pi->s=sb[i];
            pi->r=po[d-1];
            d--;
            pi->l=po[d-1];
            d--;
            po[d]=pi;
            d++;
        }
    }
    first(po[0]);
    printf("
");
    infix(po[0]);
    printf("
");
    postfix(po[0]);
    printf("
");
    return 0;
}