论坛 › 数据结构与算法 › 栈、逆波兰计算器

奥普瓯江 发表于 2021-11-2 16:45:11

栈、逆波兰计算器

原理：

备注：
        输入方式有待改进，还有就是比小甲鱼视频中多用了一个栈F

代码：

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

typedef double Elemtype;


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

void InitStack(SqStack **E);   //初始化栈E
void PushStack(SqStack **E, Elemtype T);   //进栈
Elemtype PopStack(SqStack *E);   //出栈
Elemtype NumStack(SqStack *E);


Elemtype NumStack(SqStack *E)       //
{
    Elemtype A = 0, B = 0;
    for(int i = 1; E->top != E->base; i = i * 10)
    {
      A = i * PopStack(E);
      B += A;
    }
    return B;
}
Elemtype PopStack(SqStack *E)   //出栈
{
    E->top--;
    E->stacksize++;
    return *(E->top);
}

void PushStack(SqStack **E, Elemtype T)   //进栈
{
    if((*E)->top - (*E)->base >= (*E)->stacksize)       //如果栈内空间不够
    {
      (*E)->base = (Elemtype *)realloc((*E)->base, ((*E)->stacksize + MAXSIZE) * sizeof(Elemtype ));
      (*E)->top = (*E)->base + (*E)->stacksize;
      (*E)->stacksize = (*E)->stacksize + MAXSIZE;
    }
    *((*E)->top) = T;
    (*E)->top++;
    (*E)->stacksize--;
}

void InitStack(SqStack **E)   //初始化栈E
{
    *E = (SqStack *)malloc(sizeof(SqStack ));
    (*E)->base = (Elemtype *)malloc(MAXSIZE * sizeof(Elemtype));
    (*E)->top = (*E)->base;
    (*E)->stacksize = MAXSIZE;
}


int main()
{
    SqStack *T, *F; //创建栈
    char N;
    Elemtype G, A, X, Z;
    InitStack(&T);
    InitStack(&F);


    scanf("%s", N);   //分割符我用的是@一开始想用数组输入

    for(int i = 0; N != '#'; i++)
    {
      if((N >= '0' && N <= '9') || N == '.')
      {
            while(N >= '0' && N <= '9')
            {
                PushStack(&F,N - '0');
                i++;
            }
            G = NumStack(F);

            if(N == '.')
            {
                i++;
                for(int j = 10; N >= '0' && N <= '9'; j = j*10)
                {
                  A = N - '0';
                  G += A / j;
                  //G += ( N - '0') / j;
                  i++;
                }
            }
            PushStack(&T, G);
      }
      switch(N)
      {
            case '+':{
                Z = PopStack(T);
                X = PopStack(T);
                PushStack(&T, X + Z);       //这里和出栈要调换顺许不然会出现错误
            }
            break;
             case '-':{
                Z = PopStack(T);
                X = PopStack(T);
                PushStack(&T, X - Z);
            }
            break;
             case '*':{
                Z = PopStack(T);
                X = PopStack(T);
                PushStack(&T, X * Z);
            }
            break;
            case '/':{
                Z = PopStack(T);
                X = PopStack(T);
                if(Z != 0)
                {
                  PushStack(&T, X / Z);
                }
                else
                {
                  printf("除数为0根据出发原理出发被除数不能为0\n");
                }
            }
            break;
            default:{
                break;
            }
      }
    }
    printf("%f", PopStack(T));


    return 0;
}

没飞色武 发表于 2021-12-5 14:26:25

兄弟代码有问题，不然你试试（14-2）/(6-2)*(4-1)#

奥普瓯江 发表于 2021-12-8 17:02:47

没飞色武 发表于 2021-12-5 14:26
兄弟代码有问题，不然你试试（14-2）/(6-2)*(4-1)#

没有错啊 最后得数是9.000000
这个程序是以后缀表达式输入然后计算的不是以中缀表达式输入计算的输入方式是以下面的形式输入
14@2@-@6@2@-@/@4@1@-@*#

我对编程有待学习所以先弄了个这样输入，如果弄成空格的会好些，我暂时没有改进他。

查看完整版本: 栈、逆波兰计算器