基于逆波兰式法的数学表达式计算算法
基于逆波兰式法的数学表达式计算算法
我在上一篇文章中给出了计算规则,但没有举例,这里我举一个具体的例子做说明,方便大家理解。
上篇文章的地址: 里面有Delphi7版的源代码和按此方法开发的表达式计算器。
这里先给出运算符的优先级,表中0级优先级最低,7级最高,如下:
优先级 运算符 说明
下面举一个简单的例子,计算表达式:2+(8+4^2)*3
主要分两步,第一步生成逆波兰表达式,第二步计算逆波兰表达式,如下:
0 #
表达式结束符
1 (
左括弧
2 ,
函数参数连接符
3 + -
加减
4 * /
乘除
5 @ ~
正负
6 !% ^
阶乘,百分数,求幂
7 )
右括弧
第一、生成逆波兰表达式
首先构建一个存储器,另一个符号栈,存储器是从左向右储存数据,而符号栈则遵守后进先出的原则,计算表达式按从左至右的顺序扫描。
* 读入一个数据(重点注意:数值与函数名非单个字符,需要做判断处理) 1. 如果是左单目运算符或者函数名,直接入符号栈;比如 正负号 ~ @ max sin 2. 如果是右单目运算符,直接入存储器栈;比如 阶乘!与百分号%
3. 如果是运输量,则直接写入存储器;检查符号栈顶是否有单目运算符,有的话则全部出栈,并写入存储器;
4. 如果是左括号"(",则直接入符号栈; 5. 如果是右括号")",则弹出符号栈数据,写入存储器,一直到左括号弹出(左括弧直接丢弃,不写入存储器),再检查栈顶是否为左单目运算符或者函数名,是的话继续弹出,直到遇到双目运算符;
6. 如果是双目运算符,则与栈顶符号比较优先级,若大于栈顶优先级,则入栈;否则弹出栈顶符号并写入存储器,直到栈顶符号的运算优先级较小为止; 7.如果是函数参数的连接逗号“,”时,则弹出符号栈数据,直到遇到左括弧 ( 或者逗号,为止,再将逗号,入符号栈;
8.如果是结束符(表示表达式已全部读完),则符号栈全部弹出并写入存储器,否则继续按以上规则读取下一个数据;
下面将逐步介绍逆波兰式生成过程:
表达式按从左至右扫描,标记为红色的字符为当前步骤扫描的字符: 0预处理:为表达式添加一个结束标示符“#”,扫描时按双目运算符考虑, ○
处理后表达式为:2+(8+4^2)*3#
12+(8+4^2)*3#:扫描“2”,按规则3,将运算量 2压入存储器,如下: ○存储器:
2
符号栈:暂空
关于逆波兰表达式在程序设计中的应用_专业资料。本文从应用的角度探讨了如何从...中的数学表 达式转换 成相应的逆波兰表 示 的算法 以及逆波兰表 达式 的运...
逆波兰表达式及其算法实现_IT/计算机_专业资料。逆...它 L uka siew icz 提出了另一种数学式表示法 ...1 逆波兰表达式的规则特征 中缀表达式的计算必须考虑...
逆波兰表达式 计算器 实验报告_理学_高等教育_教育...相关的两个运 算对象之间,所以,这种表示法也称为...*数学库函数*/ #include<stdlib.h>/*系统函数,...
表达式计算算法之逆波兰式_IT/计算机_专业资料。本文介绍了表达式计算的一种算法,后缀表达式计算算法,该算法可以计算中缀表达式的值...
逆波兰表达式在VB中的算法设计与实现_专业资料。在计算机中执行算术表达式的计算... 2014年统计法基础知识精讲90份文档 2014年执业医师资格考试 口腔执业医师实践...
波兰数学家 Jan Lukasiewicz 提出了另一种数学表示法...个对象 进行计算, 这个过程正好符合了计算机计算的...将一个 逆波兰式 倒转回 中缀表达式 的算法: 这个...
一.实验目的 1. 深入理解算符优先分析法 2. 掌握 FirstVt 和 LastVt 集合的...3、逆波兰式计算的实验设计思想及算法 读入一个逆波兰算术表达式 sym=当前输入...
【课题】若某算术表达式采用后置法表示(即逆波兰表达式) ,请编程计算该表达式 ...算法)设计与功能模块: ADT(数据结构与算法)设计与功能模块: 数据结构与算法 ...
C语言之逆波兰表达式完整代码(附算法)_计算机软件及应用_IT/计算机_专业资料。...不过 S2 应做一下逆序处理。便可以按照逆波 兰式的计算方法计算了! ...
布尔表达式翻译为逆波兰式的算法实现_计算机软件及应用_IT/计算机_专业资料。...的属性文法,用递归下降分析法实现对布尔表 达式的翻译,给出翻译的逆波兰式结果...
热门文档