数据结构.栈的C语言实现及中缀表达式转为后缀表达式

从今天开始，打算好好把学习数据结构的过程记录下来，学完后要复盘。
1.栈的定义

typedef char EleType;
typedef struct
{
   
    EleType *top;
    EleType *base;
    int stackSize;
} sqStack;

2.操作：
初始化

void iniStack(sqStack *p)
{
   
    p->base = (EleType *)malloc(iniStackSize * sizeof(EleType));
    if (!p->base)
        exit(0);
    p->top = p->base;
    p->stackSize = iniStackSize;
}

入栈

void pushStack(sqStack *p, EleType ele)
{
   
    if (p->top - p->base >= p->stackSize)
    {
    //realloc的地址是连续的
        p->base = (EleType *)realloc(p->base, (p->stackSize + stackSizeIncrement) * sizeof(EleType));
        if (!p->base)
            exit(0);
        p->top = p->base + p->stackSize; //再分配的内存可能变动地方，所以新的top地址会发生改变
        p->stackSize = p->stackSize + stackSizeIncrement;
    }
    *(p->top) = ele;
    (p->top)++;
}

出栈

void popStack(sqStack *p, EleType &ele) //传入EleType类型数据即可，引用是为了改变参数的值
{
   
    if (p->top == p->base)
        return;
    (p->top)--;
    ele = *(p->top);
}

是否为空

bool ifStackEmpty(sqStack *p)
{
   
    if (p->top == p->base)
        return true;
    else
        return false;
}

完整实现代码

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#define iniStackSize 20
#define stackSizeIncrement 10
#define maxBuffer 10

typedef char EleType;
typedef struct
{
   
    EleType *top;
    EleType *base;
    int stackSize;
} sqStack;

//栈初始化
void iniStack(sqStack *p)
{
   
    p->base = (EleType *)malloc(iniStackSize * sizeof(EleType));
    if (!p->base)
        exit(0);
    p->top = p->base;
    p->stackSize = iniStackSize;
}

//判断是否是空栈
bool ifStackEmpty(sqStack *p)
{
   
    if (p->top == p->base)
        return true;
    else
        return false;
}

//入栈
void pushStack(sqStack *p, EleType ele)
{
   
    if (p->top - p->base >= p->stackSize)
    {
    //realloc的地址是连续的
        p->base = (EleType *)realloc(p->base, (p->stackSize + stackSizeIncrement) * sizeof(EleType));
        if (!p->base)
            exit(0);
        p->top = p->base + p->stackSize; //再分配的内存可能变动地方，所以新的top地址会发生改变
        p->stackSize = p->stackSize + stackSizeIncrement;
    }
    *(p->top) = ele;
    (p->top)++;
}

//出栈
void popStack(sqStack *p, EleType &ele) //传入EleType类型数据即可，引用是为了改变参数的值
{
   
    if (p->top == p->base)
        return;
    (p->top)--;
    ele = *(p->top);
}

//打印栈的数据，从表尾到表头
void displayStack(sqStack &p)
{
   
    int len = p.stackSize;
    for (int i = 1; i <= len; ++i)
        printf("%d\n", *(p.top - i));
}

int main()
{
   
    sqStack A;
    iniStack(&A);
    pushStack(&A,'e');
    char m;
    popStack(&A,m);
    printf("%c",m);
    return 0;
}

3.中缀表达式转换为后缀表达式

//中缀表达式转换为后缀表达式
//输入中缀表达式，在下一行打印后缀表达式，并在最后输出结果

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#define iniStackSize 20
#define stackSizeIncrement 10
#define maxBuffer 10

typedef char EleType;
typedef struct
{
   
    EleType *top;
    EleType *base;
    int stackSize;
} sqStack;

//栈初始化
void iniStack(sqStack *p)
{
   
    p->base = (EleType *)malloc(iniStackSize * sizeof(EleType));
    if (!p->base)
        exit(0);
    p->top = p->base;
    p->stackSize = iniStackSize;
}

//判断是否是空栈
bool ifStackEmpty(sqStack *p)
{
   
    if (p->top == p->base)
        return true;
    else
        return false;
}

//入栈
void pushStack(sqStack *p, EleType ele)
{
   
    if (p->top - p->base >= p->stackSize)
    {
    //realloc的地址是连续的
        p->base = (EleType *)realloc(p->base, (p->stackSize + stackSizeIncrement) * sizeof(EleType));
        if (!p->base)
            exit(0);
        p->top = p->base + p->stackSize; //再分配的内存可能变动地方，所以新的top地址会发生改变
        p->stackSize = p->stackSize + stackSizeIncrement;
    }
    *(p->top) = ele;
    (p->top)++;
}

//出栈
void popStack(sqStack *p, EleType &ele) //传入EleType类型数据即可，引用是为了改变参数的值
{
   
    if (p->top == p->base)
        return;
    (p->top)--;
    ele = *(p->top);
}

//打印栈的数据，从表尾到表头
void displayStack(sqStack &p)
{
   
    int len = p.stackSize;
    for (int i = 1; i <= len; ++i)
        printf("%d\n", *(p.top - i));
}

int main()
{
   
    sqStack A;
    iniStack(&A);
    //从键盘输入逆波兰表达式(数字间加一个空格，以#结束)，把最终的结果存储在栈中
    char c;
    char e;
    scanf("%c", &c);
    while (c != '#')
    {
   
        while (c >= '0' && c <= '9') //数字直接输出
        {
   
            //printf("数字部分\n");
            printf("%c", c);
            scanf("%c", &c);
            if (c < '0' || c > '9')
            {
   
                printf(" ");
                break;
            }
        }
        if(c=='#')
        break;
        //printf("\nbreak\n");
        if (c == '(' || c == '*' || c == '/') //优先级比较高的乘号、除号、左括号直接入栈
            pushStack(&A, c);
        if (c == ')') //遇到右括号，就输出栈里的内容，直到遇到左括号
        {
   
            //printf("右括号部分\n");
            popStack(&A, c);
            while (c != '(')
            {
   
                printf("%c", c);
                popStack(&A, c); //左括号最后被弹出栈了，但没有被输出
            }
        }
        if (c == '+' || c == '-') //1->2->3->4->5
        {
   
            if (ifStackEmpty(&A)) //1如果是空栈就推入栈
                {
   
                    pushStack(&A, c);
                    //printf("元素压入了栈内\n");
                }
            else //2如果不是空栈
            {
   
                do //3就推出栈内符号并打印
                {
   
                    //printf("3就推出栈内符号并打印\n");
                    popStack(&A, e);
                    if (e != '(')
                        printf("%c", e);
                    else
                        pushStack(&A, e);                //左括号要保留
                } while ((e!='(')&&(!ifStackEmpty(&A))); //4直到栈为空或者遇到左括号
                pushStack(&A, c);                        //5再推入栈
            }
        }
        scanf("%c", &c);
    }
    while(!ifStackEmpty(&A))
    {
   
        popStack(&A,e);
        printf("%c",e);
    }
    return 0;
}

欢迎讨论！