算术表达式的转换

分手后的思念是犯贱 2022-08-10 08:41 151阅读 0赞

## 算术表达式的转换 ##

##### 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<stdio.h>    
    #include<stdlib.h>    
    #include<string.h>    
    #define Max  1000    
    struct node    
    {    
    char data[Max];    
    int top;    
    };    
    int cmp(char  c)    
    {    
    if(c=='+'||c=='-')    
    return 1;    
    if(c=='*'||c=='/')    
    return 2;    
    if(c=='('||c==')')    
    return 3;    
    }    
    int main()    
    {    
    int i,j,n,m,k,t;    
    char a[1000];    
    struct node *S1,*S2;    
    S1=(struct node *)malloc(sizeof(struct node));    
    S2=(struct node *)malloc(sizeof(struct node));    
    a[0]=getchar();    
    i=0;    
    while(a[i]!='#')    
    {    
    i++;    
    a[i]=getchar();    
    }    
    S1->top=-1;    
    S2->top=-1;    
    for(j=i-1;j>=0;j--)    
    {    
    if(a[j]!='('&&a[j]!=')'&&a[j]!='+'&&a[j]!='-'&&a[j]!='*'&&a[j]!='/')    
    {    
    S2->top++;    
    S2->data[S2->top]=a[j];    
    }    
    else    
    {    
    if(S1->top==-1||a[j]==')')    
    {    
    S1->top++;    
    S1->data[S1->top]=a[j];    
    }    
    else if(cmp(a[j])>cmp(S1->data[S1->top])||cmp(a[j])==cmp(S1->data[S1->top]))    
    {    
    if(a[j]!='(')    
    {    
    S1->top++;    
    S1->data[S1->top]=a[j];    
    }    
    else    
    {    
    while(S1->top>-1&&S1->data[S1->top]!=')')    
    {    
    S2->top++;    
    S2->data[S2->top]=S1->data[S1->top];    
    S1->top--;    
    }    
    S1->top--;    
    }    
    }    
    else    
    {    
    while(S1->top>-1&&S1->data[S1->top]!=')')    
    {    
    S2->top++;    
    S2->data[S2->top]=S1->data[S1->top];    
    S1->top--;    
    }    
    S1->top++;    
    S1->data[S1->top]=a[j];    
    }    
    }    
    }    
    for(j=0;j<=S1->top;j++)    
    printf("%c",S1->data[j]);    
    for(j=S2->top;j>=0;j--)    
    printf("%c",S2->data[j]);    
    printf("\n");    
    for(j=0;j<i;j++)    
    if(a[j]!=')'&&a[j]!='(')    
    printf("%c",a[j]);    
    printf("\n");    
    S1->top=-1;    
    S2->top=-1;    
    for(j=0;j<i;j++)    
    {    
    if(a[j]!='('&&a[j]!=')'&&a[j]!='+'&&a[j]!='-'&&a[j]!='*'&&a[j]!='/')    
    {    
    S2->top++;    
    S2->data[S2->top]=a[j];    
    }    
    else    
    {    
    if(S1->top==-1||a[j]=='(')    
    {    
    S1->top++;    
    S1->data[S1->top]=a[j];    
    }    
    else if(a[j]==')')    
    {    
    while(S1->top>-1&&S1->data[S1->top]!='(')    
    {    
    S2->top++;    
    S2->data[S2->top]=S1->data[S1->top];    
    S1->top--;    
    }    
    if(S1->top>-1)    
    S1->top--;    
    }    
    else if(cmp(a[j])>cmp(S1->data[S1->top])||S1->data[S1->top]=='(')    
    {    
    S1->top++;    
    S1->data[S1->top]=a[j];    
    }    
    else    
    {    
    while(S1->top>-1&&cmp(a[j])<=cmp(S1->data[S1->top])&&S1->data[S1->top]!='(')    
    {    
    S2->top++;    
    S2->data[S2->top]=S1->data[S1->top];    
    S1->top--;    
    }    
    S1->top++;    
    S1->data[S1->top]=a[j];    
    }    
    }    
    }    
    for(j=0;j<=S2->top;j++)    
    printf("%c",S2->data[j]);    
    for(j=S1->top;j>=0;j--)    
    printf("%c",S1->data[j]);    
    printf("\n");    
    }