数据结构（二）栈与队列---栈的应用：四则运算实现

注：我们这里使用链栈来实现，当然前面的顺序栈同样可以实现，而且更加容易理解。这里我们使用链栈来练习

前缀表达式、中缀表达式、后缀表达式都是四则运算的表达方式,用以四则运算表达式求值

中缀表达式就是常见的运算表达式，如(3+4)×5-6

前缀表达式又称波兰式，前缀表达式的运算符位于操作数之前

比如:- × + 3 4 5 6

后缀表达式又称逆波兰表达式,与前缀表达式相似，只是运算符位于操作数之后

比如:3 4 + 5 × 6 -

//栈中数据类型
typedef struct Data
{
    int flag;    //1为字符，2为浮点数
    union 
    {
        double num;
        char sign;
    }number;
}data;

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define STACK_INIT_SIZE 100    //定义栈的初始大小
#define STACK_INCR_SIZE 10    //定义栈的增长大小

#define MAXSIZE 100    //中缀表达式的长度

typedef struct Data
{
    int flag;    //1为字符，2为浮点数
    union 
    {
        double num;
        char sign;
    }number;
}data;

typedef data ElemType;
typedef int Status;

typedef struct
{
    ElemType *base;    //栈底指针
    ElemType *top;    //栈顶指针
    int stackSize;    //最大容量，这是可修改的
}sqStack;



//四个基础操作
Status InitStack(sqStack *s);    //初始化操作，建立一个空栈
Status ClearStack(sqStack *s);    //将栈清空
Status StackEmpty(sqStack s);    //若栈存在，返回true，否则返回false
int StackLength(sqStack s);        //返回栈S的元素个数

Status GetTop(sqStack s, ElemType *e);    //若是栈存在且非空，用e返回S的栈顶元素
Status Push(sqStack *s, ElemType e);    // 若是栈存在，则插入新的元素e到栈S中并成为栈顶元素
Status Pop(sqStack *s, ElemType *e);    //若是栈存在且非空，删除栈顶元素，并用e返回其值
Status DestroyStack(sqStack *s);        //若是栈存在，则销毁他

void PrintStack(sqStack s);    //打印所有数据，测试用，会依次将数据出栈


//初始化操作，建立一个空栈
Status InitStack(sqStack *s)
{
    s->base = (ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType));
    if (!s->base)
        return ERROR;
    s->top = s->base;    //最开始，栈顶就是栈底
    s->stackSize = STACK_INIT_SIZE;
    return OK;
}

//将栈清空,将栈顶指针移动到栈底即可，容量大小不要修改，数据不需要清空，数据入栈会覆盖
Status ClearStack(sqStack *s)
{
    if (s == NULL)
        return ERROR;
    s->top = s->base;
    return OK;
}

//若栈存在，返回true，否则返回false
Status StackEmpty(sqStack s)
{
    if (s.base == s.top)
        return TRUE;
    return FALSE;
}

//返回栈S的元素个数
int StackLength(sqStack s)
{
    int length = s.top - s.base;    //指针之间运算，是按照其中数据大小字节来算的
    return length;
}

//若是栈存在且非空，用e返回S的栈顶元素,注意：只是获取栈顶数据，不出栈
Status GetTop(sqStack s, ElemType *e)
{
    if (!e || StackEmpty(s) || !s.base)
        return ERROR;
    *e = *(s.top - 1);
    return OK;
}

//入栈操作：若是栈存在，则插入新的元素e到栈S中并成为栈顶元素
Status Push(sqStack *s, ElemType e)
{
    ElemType* newStack;
    if (!s->base)
        return ERROR;

    if (s->top-s->base>=s->stackSize)    //栈满，需要再分配
    {
        newStack = (ElemType *)realloc(s->base, (s->stackSize + STACK_INCR_SIZE)*sizeof(ElemType));    //重新分配大小
        if (!newStack)    //若是分配失败，会返回NULL
        {
            free(s->base);
            exit(0);    //分配失败，直接退出
        }
        s->base = newStack;
        //分配后需要将栈顶指针进行移动到新的位置
        s->top = s->base + s->stackSize;
    }
    *(s->top) = e;
    s->top++;
    return OK;
}

//若是栈存在且非空，删除栈顶元素（只需要将栈顶指针下移即可），并用e返回其值
Status Pop(sqStack *s, ElemType *e)
{
    if (!s->base || !e || StackEmpty(*s))
        return ERROR;
    *e = *(--s->top);
    return OK;
}

//若是栈存在，则销毁他（直接将栈底指针释放即可，置为空）
Status DestroyStack(sqStack *s)
{
    if (!s->base)    //若是栈存在
    {
        s->stackSize = 0;
        free(s->base);
        s->base = s->top = NULL;
    }
    return OK;
}

//打印数据
void PrintStack(sqStack s)
{
    data d;
    int len = StackLength(s);
    for (int i = 0; i < len;i++)
    {
        Pop(&s, &d);
        if (d.flag == 1)
            printf("%c", d.number.sign);
        else
            printf("%lf", d.number.num);
    }
}