数据结构 栈的应用三（后缀表达式）

//栈的应用--后缀表达式
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include"linkstack.h"

/*
遍历后缀表达式中的数字和符号
对于数字：进栈
对于符号：
    从栈中弹出右操作数
    从栈中弹出左操作数
    根据符号进行运算
    将运算结果压入栈中
遍历结束：栈中的唯一数字为计算结果

*/

//是否是数字
int IsNumber(char ch){
    if (ch<='9'&&ch>='0')
    {
        return 0;
    }
    return 1;
}

//是否是运算符
int IsOperator(char ch){
    if (ch=='+'||ch=='-'||ch=='*'||ch=='/')
    {
        return 0;
    }
    return 1;
}

//计算数据
int Express(int left,int right,char choperator){
    int ret = 0;
    switch (choperator)
    {
    case '+':
        ret = left + right;
        break;
    case '-':
        ret = left - right;
        break;
    case '*':
        ret = left * right;
        break;
    case '/':
        ret = left / right;
        break;
    default:
        break;
    }
    return ret;
}

//字符转数字
int GetNumber(char ch){
    if (ch<='9'&&ch>='0')
    {
        return (int)ch - (int)'0';
    }
    return 0;
}

void Test(){
    //定义后缀表达式
    char *str = "831-5*+";
    int ret = 0;
    //创建一个链表栈
    LinkStack* stack = LinkStack_Create();
    if (stack==NULL)
    {
        printf("链表创建失败");
    }
    //遍历字符串
    while (*str){
        //判断是否是数字
        if (IsNumber(*str)==0)
        {
            //直接进栈
            //注意：进栈的直接就是数字  不再是指针
            int numx= GetNumber(*str);
            //这里的指针就相当于一个占位符了   指向下一个节点在栈中已经定义了
            LinkStack_Push(stack,(void *)numx);
        }
        else if (IsOperator(*str) == 0)
        {
            //判断是否是符号
            //从栈中弹出右操作数 
            int right = (int)LinkStack_Pop(stack);
            //从栈中弹出左操作数
            int left = (int)LinkStack_Pop(stack);
            //计算结果入栈
            LinkStack_Push(stack, (void *)Express(left, right, *str));
        }
        str++;
    }
    //弹出栈中的最终结果
    while (LinkStack_Size(stack)){
        printf("最终结果是%d
", (int)LinkStack_Pop(stack));
    }
    //销毁链表
    ret = LinkStack_Destroy(&stack);
    printf("
");
}

void main(){
    Test();
    system("pause");
}