【数据结构】超详细讲解:算术表达式转化为后缀表达式、前缀表达式、表达式树的构建

勤奋不是嘴上说说而已,而是实际的行动,在勤奋的苦度中持之以恒,永不退却。业精于勤,荒于嬉;行成于思,毁于随。在人生的仕途上,我们毫不迟疑地选择勤奋,她是几乎于世界上一切成就的催产婆。只要我们拥着勤奋去思考,拥着勤奋的手去耕耘,用抱勤奋的心去对待工作,浪迹红尘而坚韧不拔,那么,我们的生命就会绽放火花,让人生的时光更加的闪亮而精彩。

导读:本篇文章讲解 【数据结构】超详细讲解:算术表达式转化为后缀表达式、前缀表达式、表达式树的构建,希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com,来源:原文

在这里插入图片描述

  • 作者:努力学习的大一在校计算机专业学生,热爱学习和创作。目前在学习和分享:算法、数据结构、Java等相关知识。
  • 博主主页: @是瑶瑶子啦
  • 所属专栏: 【数据结构】:该专栏专注于数据结构知识,持续更新,每一篇内容优质,浅显易懂,不失深度!
  • 近期目标:写好专栏的每一篇文章

在这里插入图片描述

一、什么是中缀表达式、后缀表达式、前缀表达式

  • 中缀表达式:
    中缀表达式是我们常见的数学表达式,其中运算符放置在两个操作数中间,例如:3 + 4 * 2。在中缀表达式中,还可以包含括号,用于改变运算符的优先级。

  • 后缀表达式:
    后缀表达式(也称为逆波兰表达式)是一种将运算符放置在操作数后面的表达式,例如:3 4 2 * 1 5 – 2 ^ / +。在后缀表达式中,所有操作符的优先级相同,而括号则不再需要。

  • 前缀表达式:
    前缀表达式(也称为波兰表达式)是一种将运算符放置在操作数前面的表达式,例如:+ / * 3 4 2 ^ – 1 5 2。前缀表达式和后缀表达式的计算方式相同,只是运算符的位置不同。

其中,后缀表达式和前缀表达式都是一种无歧义的表示方法,可以通过栈来快速计算。在计算机科学中,后缀表达式比较常用,因为它可以通过栈来轻松地实现表达式的计算。

一般我们所讲“算术表达式”,没有特别强调时,都是指的“中缀表达式”,也就是最常见的那种

通过后缀表达式进行计算可以按照以下步骤进行:

  1. 创建一个空栈,用于存储数字。
  2. 从左到右扫描后缀表达式的每个元素。
  3. 如果当前元素是数字,则将其压入栈中。
  4. 如果当前元素是操作符,则依次弹出栈顶的两个数字,进行相应的运算,并将结果压入栈中。
  5. 当后缀表达式扫描完毕后,栈中的唯一元素就是表达式的最终结果。

以下是一个示例,计算后缀表达式 “3 4 2 * 1 5 - 2 ^ / +”:

后缀表达式 操作
3 压栈 3
4 压栈 3 4
2 压栈 3 4 2
* 弹栈计算并压栈 3 8
1 压栈 3 8 1
5 压栈 3 8 1 5
弹栈计算并压栈 3 8 -4
2 压栈 3 8 -4 2
^ 弹栈计算并压栈 3 8 16
/ 弹栈计算并压栈 0.1875
+ 弹栈计算并压栈 3.1875

因此,后缀表达式 “3 4 2 * 1 5 – 2 ^ / +” 的计算结果为 3.1875。

二、中缀转后缀

要将算术表达式转换为逆波兰表达式,可以按照以下步骤进行:

  1. 创建一个空的栈,用于存储操作符。
  2. 从左到右扫描中缀表达式的每个元素。
  3. 如果当前元素是操作数,则直接输出到逆波兰表达式中。
  4. 如果当前元素是操作符,则进行如下操作:
    • 如果该操作符为左括号 “(”,则将其压入栈中。
    • 如果该操作符为右括号 “)”,则将栈中的操作符弹出并输出,直到遇到左括号为止。
    • 如果该操作符为其他操作符,则根据其优先级和结合性,依次将栈中比它优先级高或等于它的操作符弹出并输出,然后将该操作符压入栈中。
  5. 当中缀表达式扫描完毕后,如果栈中还有操作符,则依次弹出并输出。

最终输出的结果就是逆波兰表达式。

算术表达式 a+b*(c+d/e) 转化为后缀表达式的过程如下:

中缀表达式 操作 后缀表达式
a 输出 a
+ 压栈 + a
b 输出 + a b
* 压栈 + * a b
( 压栈 + * ( a b
c 输出 + * ( a b c
+ 压栈 + *( + a b c
d 输出 + * ( + a b c d
/ 压栈 + * ( + / a b c d
e 输出 + * ( + / a b c d e
) 弹栈输出 + * a b c d e /
结束 弹栈输出 a b c d e / + * +

因此,算术表达式 a+b*(c+d/e) 转化为后缀表达式为 a b c d e / + * +

三、中缀转前缀

  1. 将中缀表达式翻转。
  2. 将所有括号方向翻转,即左括号变为右括号,右括号变为左括号。
  3. 将翻转后的中缀表达式转化为后缀表达式
  4. 再次将后缀表达式翻转,得到前缀表达式。

例如,将中缀表达式 a+b*c-d/e 转化为前缀表达式的过程如下:

  1. 将中缀表达式翻转:e/d-c*b+a
  2. 将翻转后的中缀表达式转化为后缀表达式:ed/ cb* – a+
  3. 再次将后缀表达式翻转,得到前缀表达式:+a -*c/b de

因此,中缀表达式 a+b*c-d/e 转化为前缀表达式为 +a -*c/b de。

四、使用表达式树

将算术表达式转换为二叉树的过程可以使用表达式树的方法实现,具体步骤如下:

  1. 将算术表达式转化为后缀表达式。
  2. 从左到右扫描后缀表达式的每个元素:
    • 如果当前元素是操作数,则创建一个只包含该操作数的节点,并将该节点压入栈中。
    • 如果当前元素是操作符,则创建一个只包含该操作符的节点,并从栈中弹出两个节点作为其左右子节点,再将该节点压入栈中。
  3. 最后栈中唯一的节点即为根节点,整个树的结构已经建立完成。

例如,将算术表达式 a+b*(c+d/e) 转化为二叉树的过程如下:

  1. 将算术表达式转化为后缀表达式:abcde/+*+
  2. 从左到右扫描后缀表达式的每个元素:
    • a:创建一个只包含 a 的节点,并将该节点压入栈中。
    • b:创建一个只包含 b 的节点,并将该节点压入栈中。
    • c:创建一个只包含 c 的节点,并将该节点压入栈中。
    • d:创建一个只包含 d 的节点,并将该节点压入栈中。
    • e:创建一个只包含 e 的节点,并将该节点压入栈中。
    • /:创建一个只包含 / 的节点,并从栈中弹出两个节点 e 和 d 作为其左右子节点,再将该节点压入栈中。
    • +:创建一个只包含 + 的节点,并从栈中弹出两个节点 c 和 / 作为其左右子节点,再将该节点压入栈中。
    • *:创建一个只包含 * 的节点,并从栈中弹出两个节点 b 和 + 作为其左右子节点,再将该节点压入栈中。
    • +:创建一个只包含 + 的节点,并从栈中弹出两个节点 a 和 * 作为其左右子节点,再将该节点压入栈中。
  3. 根节点为最后剩余在栈中的节点 +。

因此,算术表达式 a+b*(c+d/e) 转化为的二叉树如下:

      +
     / \
    a   *
       / \
      b   +
         / \
        c   /
           / \
          d   e

转换完成后,该二叉树的前序遍历对应前缀表达式中序对应中缀表达式后序遍历对应后缀表达式

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

文章由半码博客整理,本文链接:https://www.bmabk.com/index.php/post/142431.html

(0)

及时掌握行业动态,欢迎加入几百人的后端技术交流群:


相关推荐

  • 【已解决】Error creating document instance. Cause: com.sun.org.apache.xerces.internal.impl.io.MalformedBy

    导读:本篇文章讲解 【已解决】Error creating document instance. Cause: com.sun.org.apache.xerces.internal.impl.io.MalformedBy,希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com

    技术随笔 2023年2月1日
    0042
  • 106.Java 中的 finally 一定会执行吗

    勤奋不是嘴上说说而已,而是实际的行动,在勤奋的苦度中持之以恒,永不退却。业精于勤,荒于嬉;行成于思,毁于随。在人生的仕途上,我们毫不迟疑地选择勤奋,她是几乎于世界上一切成就的催产婆。只要我们拥着勤奋去思考,拥着勤奋的手去耕耘,用抱勤奋的心去对待工作,浪迹红尘而坚韧不拔,那么,我们的生命就会绽放火花,让人生的时光更加的闪亮而精彩。

    导读:本篇文章讲解 106.Java 中的 finally 一定会执行吗,希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com,来源:原文

    技术随笔 2023年5月5日
    0038
  • 2022 年超详细过程步骤讲解 CentOS 7 安装Maven。以及Mavne配置文件的修改

    追求适度,才能走向成功;人在顶峰,迈步就是下坡;身在低谷,抬足既是登高;弦,绷得太紧会断;人,思虑过度会疯;水至清无鱼,人至真无友,山至高无树;适度,不是中庸,而是一种明智的生活态度。

    导读:本篇文章讲解 2022 年超详细过程步骤讲解 CentOS 7 安装Maven。以及Mavne配置文件的修改,希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com,来源:原文

    技术随笔 2023年4月9日
    0069
  • JavaWeb简单实例——Filter链

    梦想不抛弃苦心追求的人,只要不停止追求,你们会沐浴在梦想的光辉之中。再美好的梦想与目标,再完美的计划和方案,如果不能尽快在行动中落实,最终只能是纸上谈兵,空想一番。只要瞄准了大方向,坚持不懈地做下去,才能够扫除挡在梦想前面的障碍,实现美好的人生蓝图。JavaWeb简单实例——Filter链,希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com,来源:原文

    技术随笔 2023年7月27日
    0067
  • 【Hadoop—14】MapReduce:OutputFormat『 TextOutputFormat | 自定义OutputFormat』

    导读:本篇文章讲解 【Hadoop—14】MapReduce:OutputFormat『 TextOutputFormat | 自定义OutputFormat』,希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com

    技术随笔 2023年1月29日
    0045
  • SpringBoot笔记:SpringBoot集成MinIO分布式文件系统

    导读:本篇文章讲解 SpringBoot笔记:SpringBoot集成MinIO分布式文件系统,希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com

    技术随笔 2023年1月11日
    0045
  • Mybatisplus使用easycode

    导读:本篇文章讲解 Mybatisplus使用easycode,希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com

    技术随笔 2023年2月2日
    0029
  • 【算法】for循环输出九九乘法表

    导读:本篇文章讲解 【算法】for循环输出九九乘法表,希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com

    技术随笔 2023年2月22日
    00135
  • Servlet文件上传下载

    导读:本篇文章讲解 Servlet文件上传下载,希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com

    技术随笔 2023年1月23日
    0030
  • 结构体传参-C语言

    导读:本篇文章讲解 结构体传参-C语言,希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com

    技术随笔 2023年2月8日
    0062

发表回复

登录后才能评论