转载自:http://www-128.ibm.com/developerworks/cn/java/j-w3eva/index.html
编写代码对算术表达式求值的经典方法由 Donald Knuth 描述于 1962 年(请参阅 参考资料)。Knuth 将此概括为三个步骤:
- 对中缀表达式进行语法分析
- 中缀表达式到后缀表达式的转换
- 对后缀表达式求值
注意到我们谈到的这个经典算法有些简化:算术表达式只包含操作数、二元操作符和一种括号。此外,对于每个操作数和操作符,只用单个字符表示,使语法分析直观。
表达式表示法
算术表达式中最常见的表示法形式有 中缀、前缀和 后缀表示法。中缀表示法是书写表达式的常见方式,而前缀和后缀表示法主要用于计算机科学领域。
中缀表示法
中缀表示法是算术表达式的常规表示法。称它为 中缀表示法是因为每个操作符都位于其操作数的中间,这种表示法只适用于操作符恰好对应两个操作数的时候(在操作符是二元操作符如加、减、乘、除以及取模的情况下)。对以中缀表示法书写的表达式进行语法分析时,需要用括号和优先规则排除多义性。
Syntax: operand1 operator operand2
Example: (A+B)*C-D/(E+F)
|
前缀表示法
前缀表示法中,操作符写在操作数的前面。这种表示法经常用于计算机科学,特别是编译器设计方面。为纪念其发明家 ― Jan Lukasiewicz(请参阅 参考资料),这种表示法也称 波兰表示法。
Syntax : operator operand1 operand2
Example : -*+ABC/D+EF
|
后缀表示法
在后缀表示法中,操作符位于操作数后面。后缀表示法也称 逆波兰表示法(reverse Polish notation,RPN),因其使表达式求值变得轻松,所以被普遍使用。
Syntax : operand1 operand2 operator
Example : AB+C*DEF+/-
|
前缀和后缀表示法有三项公共特征:
- 操作数的顺序与等价的中缀表达式中操作数的顺序一致
- 不需要括号
- 操作符的优先级不相关
中缀表达式到后缀表达式的转换
要把表达式从中缀表达式的形式转换成用后缀表示法表示的等价表达式,必须了解操作符的优先级和结合性。 优先级或者说操作符的强度决定求值顺序;优先级高的操作符比优先级低的操作符先求值。 如果所有操作符优先级一样,那么求值顺序就取决于它们的 结合性。操作符的结合性定义了相同优先级操作符组合的顺序(从右至左或从左至右)。
Left associativity : A+B+C = (A+B)+C
Right associativity : A^B^C = A^(B^C)
|
转换过程包括用下面的算法读入中缀表达式的操作数、操作符和括号:
- 初始化一个空堆栈,将结果字符串变量置空。
- 从左到右读入中缀表达式,每次一个字符。
- 如果字符是操作数,将它添加到结果字符串。
- 如果字符是个操作符,弹出(pop)操作符,直至遇见开括号(opening parenthesis)、优先级较低的操作符或者同一优先级的右结合符号。把这个操作符压入(push)堆栈。
- 如果字符是个开括号,把它压入堆栈。
- 如果字符是个闭括号(closing parenthesis),在遇见开括号前,弹出所有操作符,然后把它们添加到结果字符串。
- 如果到达输入字符串的末尾,弹出所有操作符并添加到结果字符串。
后缀表达式求值
对后缀表达式求值比直接对中缀表达式求值简单。在后缀表达式中,不需要括号,而且操作符的优先级也不再起作用了。您可以用如下算法对后缀表达式求值:
- 初始化一个空堆栈
- 从左到右读入后缀表达式
- 如果字符是一个操作数,把它压入堆栈。
- 如果字符是个操作符,弹出两个操作数,执行恰当操作,然后把结果压入堆栈。如果您不能够弹出两个操作数,后缀表达式的语法就不正确。
- 到后缀表达式末尾,从堆栈中弹出结果。若后缀表达式格式正确,那么堆栈应该为空。
分享到:
相关推荐
实验题目: 基于栈的算术表达式求值算法 实验环境: 学习完了数据结构第三章内容栈和队列 实验目的: 1.掌握栈的定义及实现; 2.掌握利用栈求解算术表达式的方法。 实验内容: 通过修改完善教材中的算法...
表达式求值 算法 代码 报告 流程图表达式求值 算法 代码 报告 流程图表达式求值 算法 代码 报告 流程图
表达式求值的算法设计,很好的东西,比较容易实现的,希望大家能看看
1.通过修改完善课件案例 3.3 的算法,利用栈来实现算术表达式求值的算法。对算法中调 用的几个函数要给出其实现过程: (1) 函数 In(c):判断 c 是否为运算符; (2) 函数 Precede(t1,t2):判断运算符 t1 和 t2 的...
严蔚敏数据结构 表达式求值 c语言实现 符号优先级
数据结构栈实现表达式求值数据结构栈实现表达式求值数据结构栈实现表达式求值数据结构栈实现表达式求值
表达式求值,用二叉树来表示以后,进行遍历求解。
该程序很好实现了算术表达式求值,支持+、-、*、/,以=结束,符合正常表达式。
基于栈的算术表达式求值算法.rar
更改了一下中缀表达式转后缀表达式以及后缀表达式求值的算法,加入了对小数、负数的支持,注释完整,也可随时联系我。
C++实现表达式求值 本实验要求设计一个算术表达式求值的程序,该程序必须可以接受包含(,),+,-,*,/,%,和^(求幂运算符,a^b=ab )的中缀表达式,并求出结果。如果表达式正确,则输出表达式的结果;如果表达式非法...
掌握基于栈实现算术表达式求值的原理和算法。 使用VC++语言编写程序,根据数据结构中栈的的逻辑特性和物理存储结构,使用栈实现考虑算符优先的算术表达式求值算法,编译运行程序。
使用C实现栈,并实现算数表达式求值的算法
数据结构必做实验,通过两个栈实现中缀表达式求值
表达式求值是程序设计语言编译中的一个最基本问题,要求进行类的设计与实现,采用算符优先法实现表达式求值。具体要求如下: (1) 用顺序栈作为表达式求值过程中运算符栈和操作数栈的实现; (2) 用二维数组存储...
表达式求值 c++ 栈数据结构 简单四则运算
表达式求值,算符优先法。利用函数模板写的,突破了一般的只能运算个位数的算法。
C++四则运算表达式求值算法 C++四则运算表达式求值算法
使用JS实现表达式求值与幂运算算法:1)求以a为底的n次幂递归与非递归实现;2)快速乘法递归与非递归实现;3)表达式求值计算
实验步骤与源程序 实验步骤 我先从具体的问题中抽象出适当的数学模型,然后设计出相应的算法,其中,需要设 计一个函数来求后缀表达式,设计另外一个函数来求后缀表达式的值,最后,编写主函 数,串接程序,并调试...