算术表达式的转换

分手后的思念是犯贱 2022-09-24 12:30 174阅读 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*+

## 提示 ##

很想吐槽一下做这个题的艰辛，起码提交了十几次。我觉着这个题的难处在于求前缀和后缀式的时候，优先级的处理的区别。求前缀式时，当前运算符优先级大于等于栈顶元素，当前运算符即入栈；而求后缀式时，当前运算符优先级要大于栈顶元素才能入栈！

<span style="font-size:18px;">#include<stdio.h>
    #include<stdlib.h>
    #include<malloc.h>
    #include<string.h>
    #define maxsize 1000
    int count;
    typedef char Elemtype;
    typedef struct
    {
        Elemtype *top;
        Elemtype *base;
        int stacksize;
    }qstack;
    //初始化栈
    int Initstack(qstack &s)
    {
        s.base=(Elemtype *)malloc(maxsize*sizeof(Elemtype));
        s.top=s.base;
        s.stacksize=maxsize;
        return 0;
    }
    //进栈和查找（后缀式）
    int PACstack(qstack &s,char e)
    {
            if((e>='a'&&e<='z')||(e>='A'&&e<='Z')||(e>='0'&&e<='9'))//为字符直接输出
            {
                printf("%c",e);
            }
            else//不为字符时
            {
                if(e=='(')//为左括号
                {
                    *(++s.top)=e;
                }
                else if(e==')')//为右括号
                {
                    while(*(s.top)!='(')
                    {
                        printf("%c",*(s.top));
                        s.top--;
                    }
                    s.top--;
                }
                else if(e=='+'||e=='-')//为加减
                {
                     if(*(s.top)=='('||*(s.top)=='#')
                    {
                          *(++s.top)=e;
                    }
                    else
                    {
                        while(*(s.top)!='('&&*(s.top)!='#')
                        {
                            printf("%c",*(s.top--));
                        }
                        *(++s.top)=e;
                    }
                }
                else if(e=='*'||e=='/')//为乘除
                {
                    if(*s.top=='*'||*(s.top)=='/')
                    {
                         while(*(s.top)!='+'&&*(s.top)!='-'&&*(s.top)!='('&&*(s.top)!='#')
                        {
                            printf("%c",*(s.top--));
                        }
                        *(++s.top)=e;
                    }
                     else
                     {
                         *(++s.top)=e;
                     }
                }
                else if(e=='#')//为‘#’
                {
                    while(s.top!=s.base)
                    {
                        printf("%c",*(s.top));
                        s.top--;
                    }
                }
            }
    }
    //进栈和查找（前缀式）
    void FPACstack(qstack &s1,qstack &s2,char e)
    {
        count--;
        if(count==-2)//判断循环结束，将栈2中的元素全部给栈1
        {
           while(s2.top>s2.base)
            {
               *(++s1.top)=*(s2.top);
                s2.top--;
            }
        }
        else//未结束时
        {
            if(e=='#'&&s1.top==s1.base)
            {
                *(s1.top)=e;
            }
            else if((e>='a'&&e<='z')||(e>='A'&&e<='Z')||(e>='0'&&e<='9'))//为字符时
            {
                *(++s1.top)=e;
            }
            else if(e==')')//为右括号进栈
            {
                *(++s2.top)=e;
            }
            else if(e=='(')//为左括号
            {
                while(*(s2.top)!=')')
                    {
                      *(++s1.top)=*(s2.top);
                      s2.top--;
                    }
                  s2.top=s2.top-1;
            }
            else if(e=='+'||e=='-')//为加减
            {
                if(*(s2.top)=='+'||*(s2.top)=='-'||*(s2.top)==')'||*(s2.top)=='#')
                    {
                        *(++s2.top)=e;
                    }
                else if(*(s2.top)=='*'||*(s2.top)=='/')
                {
                    while(*(s2.top)!='+'&&*(s2.top)!='-'&&*(s2.top)!=')'&&*(s2.top)!='#')
                    {
                        *(++s1.top)=*(s2.top--);
                    }
                    *(++s2.top)=e;
                }
            }
            else if(e=='*'||e=='/')//为乘除
            {
                *(++s2.top)=e;
            }
        }
    }
    //出栈
    void Putstack(qstack &s)
    {
        while(s.top>s.base)
        {
            printf("%c",*(s.top));
            s.top--;
        }
    }
    int main()
    {
        char b[1000];
        int len,j,i;
        char p;
        qstack s,s1,s2;
        Initstack (s);//
        *(s.top)='#';//s的栈底初始化为'#'
        Initstack (s1);//字符栈
        Initstack (s2);//操作符栈
        *(s2.top)='#';//s2的栈底初始化为'#'
        for(j=0; ;j++)
        {
            scanf("%c",&b[j]);
            if(b[j]=='#')
            {
                break;
            }
        }
        count=j;
        for(i=j;i>=0;i--)//求前缀式
        {
            FPACstack(s1,s2,b[i]);
        }
        FPACstack(s1,s2,p);
        Putstack(s1);
        printf("\n");
        for(i=0;i<j;i++)//求中缀式
        {
            if(b[i]!='('&&b[i]!=')')
            {printf("%c",b[i]);}
        }
         printf("\n");
        for(i=0;i<j+1;i++)//求后缀式
        {
            if(b[i]=='#')
            {
                PACstack(s,b[i]);
                break;
            }
            else
            PACstack(s,b[i]);
        }
        printf("\n");
        return 0;
    }
    
    </span>