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

朱雀 2022-03-28 10:36 165阅读 0赞

//栈的应用--后缀表达式
    #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\n", (int)LinkStack_Pop(stack));
        }
        //销毁链表
        ret = LinkStack_Destroy(&stack);
        printf("\n");
    }
    
    void main(){
        Test();
        system("pause");
    }

![644743-20160727144939013-2058899340.png][]

[644743-20160727144939013-2058899340.png]: /images/20220328/a4d9760486c645b3bf906e4c195e889c.png