`
美丽的小岛
  • 浏览: 310881 次
  • 性别: Icon_minigender_1
  • 来自: 大连
社区版块
存档分类
最新评论

后缀表达式学习

阅读更多

昨天笔试,遇到一个后缀表达式,忘记了,用了很多时间回忆,才得以解决,今天决定去查一查。


一、定义
上网查一查:中缀表达式是我们从小就用的一个表达式,从百度百科中拿来了三者的定义(来源于百度百科):
中缀表达式(或中缀记法)是一个通用的算术或逻辑公式表示方法, 操作符是以中缀形式处于操作数的中间(例:3 + 4),中缀表达式是人们常用的算术表示方法。
后缀表达式:不包含括号,运算符放在两个运算对象的后面,所有的计算按运算符出现的顺序,严格从左向右进行(不再考虑运算符的优先规则,如:(2 + 1) * 3 ,即2 1 + 3 *
前缀表达式:不含括号的算术表达式,而且它是将运算符写在前面,操作数写在后面的表达式,为纪念其发明者波兰数学家Jan Lukasiewicz也称为“波兰式”。例如,- 1 + 2 3,它等价于1-(2+3)。
对于中缀表达式,它有很多括号,而前后缀则没有,如果叫计算机去计算中缀表达式,这是很困难的事情,这样不只遍历一次了。


二、三者与二叉树关系
这三个表达式与二叉树的遍历很有联系:
前缀表达式<------>前序遍历;
中缀表达式<------>中序遍历;
后缀表达式<------>后序遍历;
其实有时候,我们可以用二叉树作为中间的工具,对于平时看到中序表达式,根据它的运算法则去构那一棵二叉树。
根据中缀表达式生成二叉树(by donhao 引用【2】)
中缀表达式:a + b * (c - d) - e / f
中序遍历为:左儿子、右儿子、根节点
按照操作符的优先级,其二叉树生成过程为:
1. c-d的优先级高,根是-操作符,c和d分别为左右儿子
       -
     |    |
     c  d
2.接下来是乘法,根是*操作符,b和1中的内容分别是左右儿子
       *
   |       |
  b        -
          |  |
         c d
3.接下来是触发,根是/操作符,e和f分别是左右儿子
            /
          |  |
         e f
4.接下来是加法,根是+操作符,a和2中的内容分别是左右儿子
      +  
 |        |
a         *
       |       |
       b        -
                |  |
               c d
还包括3中的那棵树。
5.  接下来是减法,根是-操作符,4中的两棵树分别是左右儿子
                 -
    |                           |
   +                           /
 |     |                     |    |
a         *                e    f
       |        |
       b        -
                |  |
               c d   
根据二叉树前序遍历得到前缀表达式
前序遍历为:根节点、左儿子、右儿子
得到前缀表达式为:- + a * b - cd / ef
根据二叉树后序遍历得到后缀表达式
后序遍历为:左儿子、右儿子、根节点
得到后缀表达式为:abcd - * + ef / -

 

三、如何计算后缀表达式
输入:后缀表达式P
处理:栈S,功能用来存入操作数与计算的中间量,类型是数值就得了。从左向右逐个逐个字符扫描P的字符串,如果遇到操数放入S中;遇到运算符,就从S中取出栈顶的两个操作数计算,计算的结果再压入栈中。重复这样的工作,到最后S中只有一个值了,这个值就是所求。
输出:S中最后一个值

 

四、中缀表达式到后缀表达式转换(引用【1】)
如下图的模型:


Graphical illustration of algorithm, using a three way railroad junction. The input is processed one symbol at a time, if a variable or number is found it is copied direct to the output b), d), f), h). If the symbol is an operator it is pushed onto the operator stack c), e), however, if its precedence is less than that of the operator at the top of the stack or the precedences are equal and the operator is left associative then that operator is popped off the stack and added to the output g). Finally remaining operators are popped off the stack and added to the output.
注:
Graphical illustration of algorithm:算法示意图
 precedence:优先级
 associative:结合
operator:运算符

 

中缀到后缀的详细例子:


 

 

五、总结

中缀表达式转换成后缀表达(by xiazdong 引用【3】)
此方法需要遵循几个规则:
(1)如果读入操作数,则直接放入输出字符串;
(2)如果读入一般运算符如+-*/,则放入堆栈,但是放入堆栈之前必须要检查栈顶,并确定栈顶运算符的优先级比放入的运算符的优先级低;如果放入的优先级较低,则需要将栈顶的运算符放入输出字符串;
(3)如果读入(,因为左括号优先级最高,因此放入栈中,但是注意,当左括号放入栈中后,则优先级最低;
(4)如果读入),则将栈中运算符取出放入输出字符串,直到取出(为止,注意:()不输出到输出字符串;
(5)顺序读完表达式,如果栈中还有操作符,则弹出,并放入输出字符串;
  
计算后缀表达
规则如下:
(1)如果是操作数,则放入栈中;
(2)如果是操作符,则取出栈中两个操作数,进行运算后,将结果放入栈中;
(3)直到最后栈中只有一个元素,此元素就是计算结果;

 

引用:
【1】http://en.wikipedia.org/wiki/Shunting-yard_algorithm
【2】http://blog.csdn.net/donhao/article/details/5677523
【3】http://blog.csdn.net/xiazdong/article/details/7272693


 
 

  • 大小: 25.5 KB
  • 大小: 17.5 KB
  • 大小: 91.9 KB
分享到:
评论

相关推荐

    堆栈,后缀表达式

    后缀表达式,又称逆波兰表示法,是数学表达式的一种表示形式,它将运算符放在操作数之后,显著地简化了表达式的求值过程。堆栈作为一种数据结构,是后缀表达式求值的核心工具。本文将深入探讨后缀表达式与堆栈的相关...

    java堆栈的应用--中缀表达式转换成后缀表达式和计算

    在本项目中,“java堆栈的应用--中缀表达式转换成后缀表达式和计算”具体涉及到了两个主要知识点:中缀表达式的转换与后缀表达式的计算。 1. **中缀表达式**:这是我们常见的数学表达式形式,如 `2 + 3 * 4`,其中...

    后缀表达式计算求值实例

    后缀表达式,又称逆波兰表示法,是一种数学表达式的一种表示方式,它在计算机科学中有着广泛的应用,尤其是在编译原理和算法设计中。在后缀表达式中,操作符位于其操作数之后,这与我们常见的中缀表达式(如2 + 3 * ...

    获取键盘输入一个中缀表达式,将它转换成后缀表达式,并输出结果

    ### 获取键盘输入一个中缀表达式,将它转换成后缀表达式,并输出结果 #### 知识点一:中缀表达式与...通过以上内容的学习,可以系统地理解如何将中缀表达式转换为后缀表达式,并能根据具体需求编写相应的程序实现。

    利用后缀表达式计算中缀表达式的值.数据结构

    中缀表达式与后缀表达式在计算机科学和程序设计中是两种常见的表达数学计算的方式。中缀表达式,如我们常见的算术表达式,其特点是运算符位于操作数之间,例如"A+B";而后缀表达式,又称为逆波兰表示法,运算符紧跟...

    后缀表达式计算器代码

    通过这个项目,学习者不仅可以深入理解栈数据结构的应用,还能掌握QT GUI编程的基本技巧,同时增强对C++编程和后缀表达式计算的理解。这个代码实例对于初学者来说是一个很好的实践项目,可以锻炼他们的编程能力和...

    前缀表达式、中缀表达式和后缀表达式 - 乘月归 - 博客园.pdf

    前缀表达式、中缀表达式和后缀表达式是编程中常见的三种表达式表示方法,它们在计算机程序设计和算法中扮演着重要的角色。中缀表达式是最常见的一种,例如在普通的算术运算中就广泛使用。而后缀表达式和前缀表达式则...

    后缀表达式的实现

    后缀表达式,又称逆波兰表示法,是数学和计算机科学中用于表示算术表达式的一种方式。在后缀表达式中,运算符放在它们的操作数之后,这与我们常用的中缀表达式(运算符在操作数之间)不同。这种表示法在计算和解析...

    算术表达式翻译成对应的后缀表达式

    本项目是一个基于Yacc(Yet Another Compiler-Compiler)的程序,用于将用户输入的中缀算术表达式转化为等价的后缀表达式,也被称为逆波兰表示法。Yacc是一种自顶向下、递归下降的解析器生成器,通常与词法分析器...

    编译原理后缀表达式实验

    通过这个实验,学习者可以深入理解编译原理的基本概念,熟悉词法分析和语法分析的过程,同时掌握后缀表达式在实际问题中的应用。此外,实现错误恢复机制还能提升对程序异常处理的理解,增强代码健壮性。

    包含中缀表达式转后缀表达式以及后缀表达式求值

    后缀表达式,也称为逆波兰表示法,是一种在计算表达式时避免使用括号的表示方式。在后缀表达式中,运算符位于其操作数之后,这使得表达式的计算变得更为简单,特别适用于算法实现。这个压缩包文件"SuffixToValue-...

    中缀表达式变后缀表达式的求值

    然而,在计算机处理时,后缀表达式(也称为逆波兰表示法)更易于计算,因为它消除了括号的需求并利用栈来解析运算顺序。后缀表达式将操作符放在它们的操作数之后,例如,上述中缀表达式在后缀表示法中为 \(2 3 4 \...

    堆栈实现后缀表达式算法

    后缀表达式,又称逆波兰表示法,是一种不使用括号的数学表达式表示方法,主要依靠运算符的优先级和结合性来决定计算顺序。在这个堆栈实现后缀表达式算法的项目中,我们将在WinForm平台上构建一个能够处理这种表达式...

    将中缀表达式换成后缀表达式

    通过这段代码,学生不仅可以学习到如何处理中缀表达式和后缀表达式之间的转换,还能深入了解栈数据结构的应用,同时掌握C语言编程技巧,包括字符串处理、文件操作以及基本的数据结构实现。这种实践对于计算机科学的...

    编译原理实验(后缀表达式Postfix)

    虽然在这个简单的后缀表达式转换中,我们可能不会直接构建完整的AST,但理解这些概念对于深入学习编译原理至关重要。 总之,通过完成“编译原理实验(后缀表达式Postfix)”,学生将能够掌握基本的编译原理技术,...

    C 语言 后缀表达式求值-1.cpp.rar

    通过对比学习这两个源码,学生可以深入理解后缀表达式求值的多种方法,并提高编程能力。 总的来说,理解和实现后缀表达式求值不仅是对C语言的掌握,也是对数据结构和算法应用的锻炼,对于提升编程思维和问题解决...

    将原表达式转换成后缀表达式——表达式求值问题

    在这个特定的问题中,我们关注的是“表达式求值”问题,特别是如何将原表达式转换为后缀表达式,也称为逆波兰表示法(Reverse Polish Notation, RPN),然后用C语言来实现这个过程。C语言是一种通用的、中级编程语言...

    中缀表达式转后缀表达式

    而后缀表达式,也称为逆波兰表示法,将运算符置于操作数之后,如2 3 4 * +,它在计算时无需括号,通过栈数据结构即可方便地求解。这种转换和计算方法在计算机程序设计中具有较高的效率和简洁性。 本项目的目标是...

    c语言实现中缀表达式向后缀表达式转换

    ### C语言实现中缀表达式向后缀表达式转换 #### 概述 在计算机科学领域,表达式的处理是一项基础而重要的任务。表达式通常有三种形式:前缀(波兰)、中缀(标准数学表达式)和后缀(逆波兰)。本篇文章将详细探讨...

    后缀表达式求值(源程序,开发文档)

    理解并实现后缀表达式求值不仅对学习编程和算法设计有所帮助,也是理解和实现编译器、解释器的基础步骤。这个压缩包资源对于学习者来说是一个宝贵的实践平台,能深入理解数据结构和算法在实际问题中的应用。

Global site tag (gtag.js) - Google Analytics