当前位置: 首页 > article >正文

栈应用——逆波兰算法

个人主页:【😊个人主页】
系列专栏:【❤️数据结构与算法】
学习名言:传屐朝寻药,分灯夜读书

系列文章目录

第一章 ❤️ 学前知识
第二章 ❤️ 单向链表
第三章 ❤️ 递归
第四章 ❤️ 顺序栈
第五章 ❤️ 队列


文章目录

  • 系列文章目录
  • 前言
  • 中缀表达式?
  • 后缀表达式
  • 逆波兰表达式(中缀表达式转后缀表达式)
  • 为啥要使用逆波兰表达式
  • 实现原理
  • 代码实现


前言

在我们进行数字运算时我们会根据优先级自然的将结果算出来如同喝水一样,这是因为我们在学习算数开始就已经对这种运算方式习以为常了,但只能分辨出0和1的计算机又是如何进行运算的呢?🤔🤔🤔

中缀表达式?

例如a+b,运算符在两个操作数的中间。这是我们一直习惯使用的表达式形式

后缀表达式

例如a b + ,运算符在两个操作数的后面。这是一种利于计算机处理的表达形式

逆波兰表达式(中缀表达式转后缀表达式)

逆波兰表达式又叫做后缀表达式。在通常的表达式中,二元运算符总是置于与之相关的两个运算对象之间,这种表示法也称为中缀表示。波兰逻辑学家J.Lukasiewicz于1929年提出了另一种表示表达式的方法,按此方法,每一运算符都置于其运算对象之后,故称为后缀表示。

为啥要使用逆波兰表达式

逆波兰表达式是一种十分有用的表达式,它将复杂表达式转换为可以依靠简单的操作得到计算结果的表达式。例如(a+b)(c+d)转换为ab+cd+
去除原来表达式中的括号,因为括号只指示运算顺序,不是实际参与计算的元素。
使得运算顺序有规律可寻,计算机能编写出代码完成计算。
在这里插入图片描述

实现原理

一、如果输入的是操作数,则直接追加入。当输入的是 运算符 或者 分界符时压入栈中
1. 如果是左括号 ‘(’, 则 直接压入栈中,等待下一个最近的 右括号 与之配对。
2. 如果是右括号 ‘)',则说明有一对括号已经配对(在表达式输入无误的情况下)。那我们就不将它压栈,而是直接将它丢弃😶‍🌫️,然后出栈,得到元素d,将d依次运算。一直循环,直到出栈元素d 是 左括号 ( ,我们同样丢弃他。
(3)如果是运算符
1.如果栈顶元素不是运算符,则二者没有可比性,则直接将此运算符压栈。 例如栈顶是左括号 ( ,或者栈为空。
2.如果栈顶元素是运算符 ,则比较进入的运算符和栈顶运算符的优先级。如果进入运算符 > 栈顶运算符 ,则直接将此运算符压栈。
如果不满足,则将栈顶运算符出栈,再试图将运算符压栈,如果如果依然不满足 ,继续将新的栈顶运算符弹出 ,直到该运算符可以压入栈中为止。
也就是说,如果在栈中,有2个相邻的元素都是运算符,则他们必须满足:下层运算符的优先级一定小于上层元素的优先级,才能相邻。
最后,如果栈中还有元素,则依次弹出追加到d后,就得到了后缀表达式。

代码实现

#include <ctype.h>
#define STACK_INIT_SIZE 20 //栈的初始化空间大小
#define STACKINCREMENT        10 //每次增加的栈空间大小
#define MAXBUFFER                10 //缓冲区大小
typedef double ElemType;
typedef struct
{
    int stackSize;
    ElemType* base;//指向栈底的指针
    ElemType* top;//指向栈顶的指针

}sqStack;
void initStack(sqStack* s)
{
    s->base = (ElemType*)malloc(STACK_INIT_SIZE * sizeof(ElemType));
    if (!s->base)
    {
        exit(0);
    }
    s->top = s->base;
    s->stackSize = STACK_INIT_SIZE;
}
void Push(sqStack* s, ElemType e)//进栈
{
    if (s->top - s->base >= s->stackSize)
    {
        s->base = (ElemType*)realloc(s->base, (s->stackSize + STACKINCREMENT) * sizeof(ElemType));
        if (!s->base)
        {
            exit(0);
        }

        s->top = s->base + s->stackSize;
        s->stackSize = s->stackSize + STACK_INIT_SIZE;//大小要更新,不然会误认为容量不够又继续申请内存
    }

    *(s->top) = e;//把e对应的元素压入栈顶
    s->top++;//栈顶上移
}
void Pop(sqStack* s, ElemType* e)//出栈
{
    if (s->top == s->base)//判断栈是不是空
    {
        return;
    }
    *e = *--(s->top);
}
int stackLen(sqStack s)//计算栈的当前容量,s.stackSize
{
    return (s.top - s.base);
}
int main()
{
    char c;
    sqStack s;
    int i = 0;
    double d, e;//临时变量
    char str[MAXBUFFER];//小数存放缓冲区
    initStack(&s);
    printf("请输入逆波兰表达式,数据与运算符之间用空格隔开,按#键结束!\n");
    scanf("%c", &c);
    while (c != '#')
    {
        while (isdigit(c) || c == '.')//判断c是数字,头文件ctype.h,过滤数字和点以外的数据
        {
            str[i++] = c;
            str[i] = '\0';//给不知道下一个是否还要字符的位置赋结束符,以免不知道多长
            if (i >= MAXBUFFER)//字符串溢出
            {
                printf("\n出错:输入的单个数据过长!\n");
                return -1;
            }
            scanf("%c", &c);//继续输入数据
            if (c == ' ')//输入空格,代表单个数据输入结束
            {
                d = atof(str);//把字符串str转化为浮点数
                Push(&s, d);
                i = 0;//i初始化,进入下一个循环
                break;
            }

        }
        switch (c)
        {
        case '+'://两个出栈,并相加
            Pop(&s, &e);//出栈第一个数,给e
            Pop(&s, &d);//出栈第二个数,给d
            Push(&s, d + e);
            break;

        case '-'://两个出栈,并相减
            Pop(&s, &e);//出栈第一个数,给e
            Pop(&s, &d);//出栈第二个数,给d
            Push(&s, d - e);
            break;

        case '*'://两个出栈,并相乘
            Pop(&s, &e);//出栈第一个数,给e
            Pop(&s, &d);//出栈第二个数,给d
            Push(&s, d * e);
            break;

        case '/'://两个出栈,并相除
            Pop(&s, &e);//出栈第一个数,给e
            Pop(&s, &d);//出栈第二个数,给d
            if (e != 0)
            {
                Push(&s, d / e);
            }
            else
            {
                printf("\n错误:除数为零!\n");
                return -1;
            }
            break;
        }

        scanf("%c", &c);
    }
    Pop(&s, &d);//最终的结算结果放在d里
    printf("计算结果为:%f\n", d);
    return 0;
}

http://www.kler.cn/a/2157.html

相关文章:

  • IDEA遇到EasyConnect中的网络资源无法访问的问题
  • C语言基础六:循环结构及面试上机题
  • 06-标准库开发-STM32-SPI通信协议软件实现
  • Linux 输入输出重定向 相关命令详解
  • 【Notepad++】---设置背景为护眼色(豆沙绿)最新最详细
  • 【电子元器件】音频功放种类
  • 华为MetaERP最佳的免费开源平替方案:Odoo生产制造功能简介
  • 【Java进阶篇】——反射机制
  • 蓝桥杯刷题第十三天
  • ChatGPT和百度文心一言写用例,谁更强?
  • 移除元素(双指针)
  • 《剑指Offer》笔记题解思路技巧优化——精心编写(1)
  • “你要多弄弄算法”
  • 南京邮电大学数据库第三次课后作业
  • 什么是推挽输出,开漏输出?
  • 【嵌入式硬件芯片开发笔记】HART协议调制解调芯片AD5700配置流程
  • Qt优秀开源项目之十七:QtPromise
  • PostgreSQL学习总结(12)—— PostgreSQL 内置函数汇总
  • 第十七天 JavaScript、Vue详细总结
  • 队列实现及leetcode相关OJ题
  • Redis 如何实现库存扣减操作和防止被超卖?
  • 【业务安全-02】业务逻辑漏洞之越权操作
  • 测试老鸟都在用的接口抓包常用工具以及接口测试工具都有哪些?
  • 【C++】二叉搜索树
  • WebService简单入门
  • python+django+vue全家桶鲜花商城售卖系统