栈、队列：中缀表达式转后缀表达式

奥普瓯江

原理：


备注：


代码：

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100

typedef char Elemtype;

typedef struct
{
    Elemtype *base;
    Elemtype *top;
    int stacksize;

}SqStack;


void InitStack(SqStack **E);                         //初始化栈
void PushStack(SqStack **E, Elemtype N);                //进栈
Elemtype PopStack(SqStack *E);                        //出栈
void DeleStack(SqStack **E);                            //释放被占用内存地址
int NeedStack(SqStack *E);                         //把字符转换成数字
void OvHappy(SqStack **E, Elemtype N);             //字符输出

void OvHappy(SqStack **E, Elemtype N)               //字符输出
{
    Elemtype temp;
     if((*E)->base == (*E)->top)
    {
        PushStack(&(*E), N);
    }
    else
    {
        while(1)
        {
            if((*E)->base == (*E)->top)
            {
                PushStack(&(*E), N);
                return ;
            }
            else
            {
                temp = PopStack(*E);
            }


            switch(N)
            {
                case '+' :{

                     if(temp == '+' || temp == '-' || temp == '*' || temp == '/')
                    {
                        printf("%c", temp);
                    }
                    else if(temp == '(')
                    {
                        PushStack(&(*E), temp);
                        PushStack(&(*E), N);
                        return;
                    }
                }
                break;
                case '-' :{
                      if(temp == '+' || temp == '-' || temp == '*' || temp == '/')
                    {
                        printf("%c", temp);
                    }
                    else if(temp == '(')
                    {
                        PushStack(&(*E), temp);
                        PushStack(&(*E), N);
                        return;
                    }
                }
                break;
                case '*' :{
                     if(temp == '*' || temp == '/' )
                    {
                        printf("%c", temp);
                    }
                    else  if(temp == '+' || temp == '-' )
                    {
                        PushStack(&(*E), temp);
                        PushStack(&(*E), N);
                        return;
                    }
                    else if(temp == '(')
                    {
                        PushStack(&(*E), temp);
                        PushStack(&(*E), N);
                        return;
                    }
                }
                break;
                case '/' :{
                     if(temp == '*' || temp == '/' )
                    {
                        printf("%c", temp);
                    }
                    else  if(temp == '+' || temp == '-' )
                    {
                        PushStack(&(*E), temp);
                        PushStack(&(*E), N);
                        return;
                    }
                    else if(temp == '(')
                    {
                        PushStack(&(*E), temp);
                        PushStack(&(*E), N);
                        return;
                    }
                }
                break;
                case '(' :{
                       PushStack(&(*E), temp);
                       PushStack(&(*E), N);
                       return;
                }
                break;
                case ')' :{
                    while(temp != '(')
                    {
                        printf("%c", temp);
                        temp = PopStack(*E);
                    }
                    return;
                }
                break;
            }

        }
    }
}

int NeedStack(SqStack *E)                         //把字符转换成数字
{
    int a = 0, b = 0;
    int i;
    for(i = 1; E->top != E->base; i *= 10)
    {
        a = (int)PopStack(E) - '0';
        b += a * i;
    }
    return b;
}

void DeleStack(SqStack **E)                            //释放被占用内存地址
{
    free((*E)->base);
    free(*E);
}

Elemtype PopStack(SqStack *E)                         //出栈
{
    E->top--;
    E->stacksize++;
    return *(E->top);
}
void InitStack(SqStack **E)                    //初始化栈
{
    *E = (SqStack *)malloc(sizeof(Elemtype ));
    if(!(*E))
    {
        printf("初始化*E内存分配错误\n");
        exit(0);
    }
    (*E)->base = (Elemtype *)malloc(MAXSIZE * sizeof(Elemtype ));
    if(!(*E)->base)
    {
        printf("初始化(*E)->base内存分配错误\n");
        exit(0);
    }
    (*E)->top = (*E)->base;
    (*E)->stacksize = MAXSIZE;
}

void PushStack(SqStack **E, Elemtype N)         //进栈
{
    if((*E)->top - (*E)->base >= (*E)->stacksize)       //检查栈是否不够了如果不够了就要增加栈的大小
    {
        (*E)->base = (Elemtype *)realloc((*E)->base, ((*E)->stacksize + MAXSIZE) * sizeof(Elemtype ));      //从新
        if(!(*E)->base)
        {
            printf("扩容内存分配错误\n");
            exit(0);
        }
        (*E)->top = (*E)->base + (*E)->stacksize;
        (*E)->stacksize = (*E)->stacksize + MAXSIZE;
    }
    *((*E)->top) = N;
    (*E)->top++;
    (*E)->stacksize--;
}

int main()
{
    char C;
    char N[100];
    int i;
    SqStack *L, *G;
    InitStack(&L);          //数字转换栈
    InitStack(&G);          //符号储存

    for(i = 0; (C = getchar()) != '#'; i++)     //输入
    {
        N[i] = C;
        N[i + 1] = '\0';
    }


    for(i = 0; N[i] != '\0'; i++)
    {
        if(N[i] >= '0' && N[i] <= '9')
        {
            while(N[i] >= '0' && N[i] <= '9')
            {
                PushStack(&L, N[i]);
                i++;
            }
            printf("%d", NeedStack(L));
        }

        //从新建立一个函数

        if(N[i] == '+'|| N[i] == '-' || N[i] == '*' || N[i] == '/' || N[i] == '(' || N[i] == ')')
        {
             OvHappy(&G, N[i]);
        }
        if(N[i+1] == '\0' && G->top != G->base)
        {
            printf("%c", PopStack(G));
        }
    }
    //输出
    return 0;
}