//搭建⼀个栈
#include <stdio.h>
#include <stdlib.h>
//输⼊输出
//更灵活 malloc动态申请空间
#define STACKSIZE 100
//初始化的栈它多⼤啊
//要是满了IC
#define INCREASESIZE 20
typedef struct Cstack
{
    char *top;
    char *base;
    int StackSize;
} Cstack;
//初始化⼀个栈

void InitCstack(Cstack *c)
{
 //分配空间
    c->base = (char*)malloc(STACKSIZE*sizeof(char));
    c->top = c->base;
    c->StackSize = STACKSIZE;
}
//有元素我们就压栈
//写压栈函数
void Push(Cstack *c,char e)
{
 //压之前要看看栈满不满啊
    if(c->top - c->base == c->StackSize)
    {
        //加空间
        c->base = (char*)realloc(c->base, (INCREASESIZE + c->StackSize)*sizeof(char));
        //c->top 现在还原了
        //还要指回去
        c->top = c->base + c->StackSize;
        c->StackSize = c->StackSize + INCREASESIZE;
    }
    //那现在我们栈就相当完美了
    //那就压栈呗
    *(c->top) = e;
    (c->top)++;
}
//你能压你就要弹栈
void Pop(Cstack *c, char *e)
{
    //你说这个栈它是个空的你弹个屁啊！
    if(c->top == c->base)
    {
        printf("栈已经空了\n");
        return;
    }
    else
    {      
        c->top--;
        *e = *(c->top);
    }
}
//-----------------------------------------------------------------------------
//下⾯是数栈了
typedef struct Nstack
{
    double *top;
    double *base;
    int StackSize;
} Nstack;
//初始化⼀个栈

void InitCstackN(Nstack *c)
{
 //分配空间啊
    c->base = (double*)malloc(STACKSIZE*sizeof(double));
    c->top = c->base;
    c->StackSize = STACKSIZE;
}
//有元素我们就压栈呗
//写压栈函数
void PushN(Nstack *c,double e)
{
 //压之前要看看栈满不满啊
    if(c->top - c->base == c->StackSize)
    {
    //加空间呗
        c->base = (double*)realloc(c->base, (INCREASESIZE + c->StackSize)*sizeof(double));
    //c->top 现在还原了
    //还要让⼈家指回去啊
        c->top = c->base + c->StackSize;
    //别忘了你加量了啊
        c->StackSize = c->StackSize + INCREASESIZE;
    }
 //那现在我们栈就相当完美了
 //那就压栈呗
    *(c->top) = e;
    (c->top)++;
}
//你能压你就要弹栈
void PopN(Nstack *c, double *e)
{
 //你说这个栈它是个空的你弹个屁啊！
    if(c->top == c->base)
    {
        printf("栈已经空了\n");
        return;
    }
    else
    {
        c->top--;
        *e = *(c->top);
    }
}

int main()
{
Cstack c;
InitCstack(&c);
char Temp_Save[40];
 (void)Temp_Save; //我们这回不打印了，我们把我们要打印的玩意给他存在这个数组⾥边
 int s = 0; //s是save数组的下标
(void)s;
 char ch; //从我的输⼊流⾥边读取⼀个字符呗
(void)ch;
 char e; //是⼀个接收变量——————⽤于和栈之间的连接
(void)e;
 //我们现在要开始了进⾏⼀个有意思转化-----将我们的复合表达式转化成我们计算机能看懂的表达式
 //思路——————如果是数字或者是⼩数点 咱们就让他直接显示在我们的平⾯上
 //-————————如果是+ — * / （ ） 要考虑⼊栈了
 //——————-——如果是* / （ 我们直接让他⼊栈
 //—————————如果是 ） 我们就⼀直让他弹栈知道弹到（， 并且把我们弹的元素⼀个⼀个打印出来，但是（ 我们不打
 //—————————如果是 + — 的话我们要弹栈⼀直弹到 （ 或者栈空就完了，千万别忘了把我们的+⽼哥给⼈家⼊栈⾥边去
 //—————————但是有可能第⼀个就是加号，这时候你要弹栈，空的弹尼玛
 //—————————结束符号设置成# 当我们检测到#的时候表示我们对表达式的读取完事了
 //—————————这个时候不管我们栈⾥有没有符号都要把栈给清空
printf("请输⼊你的表达式(你的表达式在数字和字符之间要输⼊空格，字符与字符之间不必输⼊并以#结尾)：");
ch = getchar();
printf("\n你的表达式转化为如下形式:");
while (ch != '#')
{
    if (ch == ' ')
    {
        
        Temp_Save[s] = ch;
        s++;
    }
    else if((ch >= '0' && ch <= '9') || ch == '.')
    {
    
        Temp_Save[s] = ch;
        s++;
    }
    else if(ch == '*' || ch == '/' || ch == '(')
    {
        Push(&c,ch);
    }
    else if(ch == ')')
    {
        Pop(&c,&e);
        while (e != '(')
        {
        
            Temp_Save[s] = e;
            s++;
            Pop(&c,&e);
        }
    }
    else if(ch == '+' || ch == '-')
    {
        if (c.base == c.top)
    {
        Push(&c, ch);
    }
    else
    { 
        Pop(&c,&e);
        if (e == '(')
        {
            Push(&c,e);
        }
        while (e != '(' && c.base != c.top ) //退出条件————————弹到了（，或者到了栈低
        {
            
            Temp_Save[s] = e;
            s++;
            Pop(&c, &e);
            if (e == '(')
            {
                Push(&c, e);
            }
        }
        if (c.base == c.top)
        {
        
            Temp_Save[s] = e;
            s++;
        }
        Push(&c,ch);
    }
    }
    ch = getchar();
}
while (c.base != c.top)
{
    Pop(&c, &e);
    
    Temp_Save[s] = e;
    s++;
}
Temp_Save[s] = '#';
for (int i = 0;i <= s ;i++ )
{
    printf("%c",Temp_Save[i]);
}
putchar('\n');
  //开始搞逆波兰表达式的求值了
  //—————————————————————————————————————————————
  //———————————————
  int j = 0; //这个j要实现类似于getcahr的功能
(void) j;
  //算法思路
  //——————————⾸先啊我们呢要⽤输⼊流读取
  //——————————如果读到的是数字那么我们就把这个数字或者⼩数点存到我们的转换数组⾥边去
  //——————————把这个转换数组⽤函数来转化成浮点数
  //——————————然后把这个浮点数存到我们的数栈⾥边去
  //——————————如果读到了+ - * /那么就要弹出两个数字，把他们进⾏相应的运算，然后压⼊栈
  //——————————以#结尾，当我们读到#时把栈⾥的⼀个元素给他弹出栈打印就完事了
  //——————————转化浮点数的函数为atof
  char Tran_Double_Num[20]; //把我们读的连续数字存到这个数组⾥边
  double val; //当我们录⼊数字操作完成的时候，把这个数给他赋值到val⾥边来
  char ch1; //读如字符
  double a, b; //对数栈进⾏压栈弹栈的操作需要的介值元素
  int i = 0; //TR数组的下标
Nstack N;
InitCstackN(&N);
ch1 = Temp_Save[j++];
while (ch1 != '#')
{
        while ((ch1 >= '0' && ch1 <= '9')|| ch1 == '.')
        {
            Tran_Double_Num[i] = ch1;
            i++;
            ch1 = Temp_Save[j++];
            if (ch1 == '.')
            {
            }
            else if(ch1 < '0' || ch1 > '9') //ch读如的玩意它不是数字了————————数字⼈家录⼊完事了
            {
            //——————转化
            val = atof(Tran_Double_Num);
            i = 0;
            for (int p = 0; p < 20;p++ )
            {
                Tran_Double_Num[p] = '\0';
            }
            PushN(&N, val);
            }
        }
        switch (ch1) //ch 可能为空格，运算符， #
        {
            case ' ': break;
            case '+':   PopN(&N,&a);
                        PopN(&N,&b);
                        PushN(&N, a + b);
                        break;
            case '-':   PopN(&N,&a);
                        PopN(&N,&b);
                        PushN(&N, b - a);
                        break;
            case '*':   PopN(&N,&a);
                        PopN(&N,&b);
                        PushN(&N, a * b);
                        break;
            case '/':   PopN(&N,&a);
                        PopN(&N,&b);
                        PushN(&N, b / a);
                        break;
        }
        if (ch1 == '#')
        {
            break;
        }
        ch1 = Temp_Save[j++];
}
PopN(&N, &a);
printf("%lf\n", a);
return 0;
}