逆波兰算法

发布时间:2020-03-25 12:06:07 作者:WZM3558862
来源:网络 阅读:639

这里先给出运算符的优先级,表中0级优先级最低,7级最高,如下:

优先级0123   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


符号栈:暂空


22+8+4^2*3#扫描“+”,按规则6,将加号压入符号栈,如下:

2

+


推荐阅读:
  1. C++解逆波兰表达式
  2. 栈的应用   逆波兰式

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

存储器 表达式 百分号

上一篇:香港服务器机房有什么优点?

下一篇:3d矢量绕任意轴转动公式

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》