论坛 › 数据结构与算法 › 栈、队列：中缀表达式转后缀表达式

奥普瓯江 发表于 2021-11-12 17:29:12

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

原理：


备注：


代码：

#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);
                  }
                  elseif(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);
                  }
                  elseif(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;
    int i;
    SqStack *L, *G;
    InitStack(&L);          //数字转换栈
    InitStack(&G);          //符号储存

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


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

      //从新建立一个函数

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

查看完整版本: 栈、队列：中缀表达式转后缀表达式