试卷征集
加入会员
操作视频

为四则运算式“6+(8-2)*2÷3”转逆波兰表达“682-2*3÷+”设计算法,编程实现。
分析:在数学运算表达式中,运算符总是置于与之相关的两个运算对象之间,在计算结果时,要考虑括号、运算符号的优先性。为了程序实现的方便,波兰逻辑学家J.Lukasiewicz提出了另一种表示法,将运算符置于其运算对象之后,没有括号,不用考虑运算符号的优先性。这种表达式称为后缀表达式,又叫逆波兰表达式。
如表达式“682-2*3÷+”是四则运算式“6+(8-2)*2÷3”的逆波兰表达式。为了处理方便,规定表达式中的数均为小于10的正整数,运算符为+、-、*、÷。
(1)抽象建模
设计两个栈bds、fh,栈bds用来存放表达式,栈fh用来暂时存放运算符。从左往右扫描四则运算式,遇到数字时,入栈bds;遇到运算符号时,根据运算符号的优先级设计进栈与出栈。
四则运算式“6+(8-2)*2÷3”转换规则的模拟过程如表所示:

结合表格的操作过程,用栈bds和栈fh记录每个操作后的栈内情况(见图),那么在操作2中栈fh里有内容为
+(-
+(-
(请从栈底到栈顶顺序书写)。

(2)设计算法
基于问题的抽象与建模,解决该问题的主要算法描述如下:
从左往右遍历四则运算式s(设中间变量为ch):
1)当ch是数字,直接入栈bds;
2)当ch是运算符:
a.若ch为左括号时,直接入栈fh;
b.若ch为右括号时,则将栈fh元素弹出,压入栈bds,直到遇到左括号(左括号只
弹出,不压入栈bds);
c.若ch为其它运算符时,如果运算符ch优先级大于栈fh中栈顶元素的优先级(或栈fh为空),直接入栈fh;否则,将栈fh元素依次弹出,并压入栈bds,直到运算符ch优先级大于栈fh中栈顶元素的优先级(或栈fh为空);
3)将栈bds中元素依次出栈,即为该四则运算s的后缀表达式。
(3)编写程序
实现上述功能的Python代码如下,请在横线处填入合适代码。

【考点】栈的应用
【答案】+(-
【解答】
【点评】
声明:本试题解析著作权属菁优网所有,未经书面同意,不得复制发布。
发布:2024/11/29 21:0:1组卷:19引用:2难度:0.3
相似题
  • 1.一个序列的出栈顺序为1,2,3,4,5,则该序列的入栈顺序不可能为(  )

    发布:2024/11/25 7:0:1组卷:9引用:1难度:0.5
  • 2.数字1,2,3依次进栈,则不可能的出栈顺序是(  )

    发布:2024/11/28 22:30:1组卷:8引用:3难度:0.5
  • 3.一个栈的入栈序列为1,2,3,4,5,其出栈序列为s1,s2,s3,s4,s5。若s2是3,则s1不可能是(  )

    发布:2024/12/10 20:0:2组卷:16引用:5难度:0.5
深圳市菁优智慧教育股份有限公司
粤ICP备10006842号公网安备44030502001846号
©2010-2025 jyeoo.com 版权所有
APP开发者:深圳市菁优智慧教育股份有限公司| 应用名称:菁优网 | 应用版本:5.0.7 |隐私协议|第三方SDK|用户服务条款
广播电视节目制作经营许可证|出版物经营许可证|网站地图
本网部分资源来源于会员上传,除本网组织的资源外,版权归原作者所有,如有侵犯版权,请立刻和本网联系并提供证据,本网将在三个工作日内改正