C语言利用栈实现将中缀表达式转换为后缀表达式（即逆波兰式）

素颜马尾好姑娘i 2022-08-05 07:49 126阅读 0赞

输入计算表达式如：（1-3）\*4+10/5

输出的逆波兰式：1  3  -  4  \* 10  5  /   +

码代码时脸上洋溢着的神秘的微笑![微笑][smile.gif]

#include <stdio.h>
    #include <stdlib.h>
    #include <ctype.h>
    
    #define Stack_Init_Size 20
    #define Stack_Increasement 10
    
    typedef char Elemtype;
    typedef struct{
        Elemtype *base;
        Elemtype *top;
        int stacksize;
    }sqStack;
    
    void initStack(sqStack *s)
    {
        s->base=(Elemtype *)malloc(Stack_Init_Size*sizeof(Elemtype));
        if(!s->base)
        {
            return;
        }
        s->top=s->base;
        s->stacksize=Stack_Init_Size;
    }
    
    void push(sqStack *s,Elemtype e)
    {
        if(s->top-s->base>=s->stacksize)
        {
            s->base=(Elemtype *)realloc(s->base,(Stack_Increasement+s->stacksize)*sizeof(Elemtype));
            if(!s->base)
            {
                return;
            }
        }
        *(s->top)=e;
        s->top++;
    }
    
    void pop(sqStack *s,Elemtype *e)
    {
        if(s->top == s->base)
        {
            return;
        }
        s->top--;
        *e=*(s->top);
    }
    
    int stackLen(sqStack s)
    {
        return (s.top-s.base);
    }
    
    int isEmpty(sqStack s)
    {
        return (s.base==s.top);
    }
    
    int main()
    {
        sqStack s;
        initStack(&s);
        char c,e;
        printf("请输入所要计算的中缀表达式，以#结束！\n");
        scanf("%c",&c);
        while(c!='#')
        {
            while(isdigit(c))
            {
                printf("%c",c);
                scanf("%c",&c);  //如果此刻输入#，则外层以#为结束条件的循环会无法结束，因为后面有读入的语句，此时读入的#会被“覆盖”，所以外层循环内的要判断读入的c是否是#
                if(c>'9'||c<'0')
                {
                    printf(" ");
                }
            }  //保证输出的多位数的形式正确  如123不会输出1 2 3
            if(')'==c)
            {
                pop(&s,&e);
                while( '(' != e )
                {
                    printf("%c ",e);
                    pop(&s,&e);
                }
            }
            else if('+'==c ||'-'==c)
            {
                if(isEmpty(s))
                {
                    push(&s,c);
                }
                else
                {
                    do
                    {
                        pop(&s,&e);
                        if( '(' == e )
                        {
                           push(&s,e);
                        }
                        else
                        {
                            printf("%c ",e);
                        }
                    }while(!isEmpty(s) && '('!=e);
                    push(&s,c);
                }
            }
            else if( '*' == c || '/' == c || '(' == c )
            {
                 push(&s,c);
            }
            else if('#'==c)
            {
                break;
            }
            else
            {
                printf("\n出错：输入格式错误！\n");
                return -1;
            }
            scanf("%c",&c);
        }
        while(!isEmpty(s))
        {
            pop(&s,&e);
            printf("%c ",e);
        }
    	printf("\n");
        return 0;
    }

[smile.gif]: /images/20220731/91eaf84bbaa849f3a7b170c2b1408294.png