栈的应用---逆波兰表达式

中缀表达式 —>> 后缀表达式
stack.h

#define _CRT_SECURE_N0_WARNINGS 1
#pragma once

#define  Max_size  100
#include <stdio.h>
#include <assert.h>
#include <string.h>

typedef int StackDataType;

typedef struct Stack{ 
    StackDataType arr[Max_size];
    int top;
}Stack;

//基本操作
void StackInit(Stack* pStack)
{
    pStack->top = 0;
}

void StackDestroy(Stack* pStack)
{
    pStack->top = 0;
}

void StackPush(Stack* pStack, StackDataType data)
{
    //判断栈内是否有空间存放数据
    assert(pStack->top < Max_size);
    //进行压栈
    pStack->arr[pStack->top++] = data;
}

void StackPop(Stack* pStack)
{
    //判断栈不为空
    assert(pStack->top > 0);
    //进行出栈
    pStack->top--;
}

StackDataType StackTop(Stack* pStack)
{
    //判断栈不为空
    //返回栈顶元素
    return pStack->arr[pStack->top-1];
}

int StackSize(Stack* pStack)
{
    return pStack->top;
}

int StackFull(Stack* pStack)
{
    return pStack->top >= Max_size;
}

int StackEmpty(Stack* pStack)
{
    return pStack->top <=0;
}

//----------------------------
//逆波兰表达式（RPN）  后缀表达式
//12*(3+4)-6+8/2  ------> 12 3 4 + * 6 - 8 2 / +

typedef enum{
    ADD,SUB,MUL,DIV,DATA
}OPERATOR;

typedef struct Cell{
    OPERATOR _op;//操作是数字？还是操作符
    int data;//数字是具体值 操作符为0
}Cell;

int CalcRPN(Cell *RPN,int size)
{
    int i = 0;

    Stack stack;
    StackInit(&stack);

    for (; i < size; ++i)
    {
        if (DATA == RPN[i]._op)
            StackPush(&stack, RPN[i].data);
        else{
            int left = 0, right = 0;//定义初始化左右操作数

            right = StackTop(&stack);
            StackPop(&stack);
            
            left = StackTop(&stack);
            StackPop(&stack);

            switch (RPN[i]._op)
            {
            case ADD:
                StackPush(&stack, left + right);
                break;
            case SUB:
                StackPush(&stack, left - right);
                break;
            case MUL:
                StackPush(&stack, left * right);
                break;
            case DIV:
                if (0 == right)
                {
                    printf("除数为0，非法！\n");
                    return 0;
                }
                StackPush(&stack, left / right);
                break;
            }
        }
    }
    return StackTop(&stack);
}

main.c

#define _CRT_SECURE_N0_WARNINGS 1

#include "stack.h"

int main()
{
    //逆波兰表达式

    Cell RPN[] = { { DATA, 12 }, { DATA, 3 }, { DATA, 4 }, { ADD, 0 }, { MUL, 0 },
    { DATA, 6 }, { SUB, 0 }, { DATA, 8 }, { DATA, 2 }, { DIV, 0 }, { ADD, 0 } };

    printf("%d\n", CalcRPN(RPN,  sizeof(RPN) / sizeof(RPN[0]) ) );

    return 0;
}

运行结果：