第12课 栈2——栈应用-【精彩三年】2024-2025学年高中信息技术选择性必修1课程探究与巩固Word教参（浙教版2019）

第12课　栈2——栈应用(见学生用书P94) ——3.3　栈，教材P82～90 1.掌握栈的基本操作，并能编程实现。　2.能使用栈的基本操作解决实际问题。 1．逆波兰表达式的实现 在数学运算表达式中，运算符总是置于与之相关的两个运算对象之间，在计算结果时，要考虑括号、运算符号的优先性。为了程序实现的方便，将运算符置于其运算对象之后，没有括号，不用考虑运算符的优先性。这种表达式称为后缀表达式，又叫逆波兰表达式，如表达式“6 8 2 － 2 * 3 / ＋”是“6＋(8－2)*2/3”的逆波兰表达式。 (1)转换为逆波兰表达式 ①算法描述： 四则运算式转后缀表达式设计算法，如“6 ＋ ( 8 － 2 ) * 2 / 3”转换后结果为“6 8 2 － 2 * 3 / ＋”。 用栈来存储运算符号，从左往右扫描四则运算式，遇到数字直接输出。 若栈为空或当前运算符号为“(” 时，入栈。 若栈非空：当栈顶为“(” 则当前运算符入栈；否则比较优先级，当前运算符大于栈顶元素则入栈，否则栈顶元素出栈输出，直至栈顶元素小于或等于当前运算符，当前运算符入栈 遇到右括号时，则栈顶元素依次出栈输出，直至遇到左括号，左括号出栈但不输出。 ②Python程序实现： # 四则运算式6 ＋ ( 8 － 2 ) * 2 / 3(中间有一个空格分开) ops_rule＝{'＋'： 1，'－'： 1，'*'： 2，'/'： 2} #运算规则的优先级 s＝input(”输入中缀表达式(格式如6 ＋ ( 8 － 2 ) * 2 / 3)：”) ss＝s.split()；ops＝[] for item in ss： if ”0”<＝item<＝”9”： 　print(item，” ”，end＝””) else： if len(ops)＝＝0： ops.append(item) else： if item＝＝”(”： ops.append(item) elif item＝＝”)”： while len(ops)>0： if ops[－1]＝＝”(”： ops.pop() break else： print(ops.pop()，” ”，end＝””) else： while len(ops)>＝0： 　　　　　　　　　　if len(ops)＝＝0： ops.append(item) break 　　　　　　　　else： if ops[－1]＝＝”(” or ops_rule[item]>ops_rule[ops[－1]]： ops.append(item) break else： print(ops.pop()，” ”，end＝””) while len(ops)>0： print(ops.pop()，” ”，end＝””) ③运行结果： 输入中缀表达式(格式如6 ＋ ( 8 － 2 ) * 2 / 3)：6 ＋ ( 8 － 2 ) * 2 / 3 6 8 2 － 2 * 3 / ＋ (2)利用逆波兰表达式计算 ①算法描述： 用一个栈存储数字，从左向右扫描表达式，遇到数字时，入栈；遇到运算符号时，把处于栈最上方的两个元素依次出栈，用运算符计算，并把计算结果压入栈中。 ②Python程序实现： a＝input('输入字符串：　输入字符串8，4，2，－，2，*，/2.0').split('，　') st＝['']*len(a) top＝－1 t＝0 for i in range(len(a))： if a[i] not in '＋－*/' ： 　　top＋＝1 　　st[top]＝a[i] else： if a[i]＝＝”＋”： t＝int(st[top－1])＋int(st[top]) elif a[i]＝＝”－”： t＝int(st[top－1])－int(st[top]) elif a[i]＝＝”*”： t＝int(st[top－1])*int(st[top]) else： t＝int(st[top－1])/int(st[top]) st[top－1]＝str(t) top－＝1 print(st[top]) ③运行结果： 输入字符串：8，4，2，－，2，*，/ 2.0 2．栈的链式存储结构 利用链式存储方式实现的栈称为链栈，可以用单链表方式实现，栈顶指针top为链栈的头指针。 　　已知逆波兰表达式为a b ＋ c * a b ＋ e / －，则对应的数学运算表达式为(　B　) A．(a＋b)－(c*a＋b)/e B．(a＋b)*c－(a＋b)/e C．(a＋b*c＋a)/b－e D．(a＋b*c)－(a＋b/e) 【解析】 逆波兰表达式中，a和b先入栈，碰到操作符＋，前两个操作数出栈，并把a＋b作为看成是一个操作数，入栈；与c*转换成(a＋b)*c，同时ab＋e/转换为(a＋b)/c，最终选项B正确。 变式1在利用栈来判断一个表达式的括号(只有小括号)是否匹配的过程中，当遇到表达式中的一个左括号时，就让其入栈，遇到一个右括号时，就对栈进行一次出栈操作；当栈最后为空，表示括号是配对的，否则是不配对的。现有表达式“(a＋b)*c＋((d－e)*f＋g)*h”，针对该表达式设计栈的大小至少为(　B　) A．1 B．2 C．3 D．4 【解析】 遇到第一个左括号入栈，遇到第一个右括号时，栈中的左括号出栈；遇到第二个和第三个左括号，依次入栈；遇到第二个右括号，依次出栈；遇到第三个右括号，又依次出栈。此时栈为空，表达式中的括号配对成功。整个过程中，栈中最多有2个左括号，所以栈的大小至少为2。 　　逆波兰表达式其实就是后缀表达式，即操作数在前，运算符在后，这种方式不需要单独考虑运算符的优先级，因此非常适合计算机实现表达式求值；而我们数学上常用的表达式是中缀表达式，那么如何将中缀表达式转换为后缀表达式呢？利用栈就可以实现。 (1)中缀表达式“(6＋(8－2)*3)/4”的后缀表达式为　6 8 2－3*＋4/　。 (2)根据注释在以下Python 程序段横线处填入合适的代码。 s＝input(”请输入中缀表达式(用空格分隔字符和运算符)：　”).split() stack，top，res＝[None]*5，－1，[] ops＝{”**”：2，”*”：1，”/”：1，”//”：1，”%”：1，”＋”：0，”－”：0}　　 #运算符优先级 for c in s： if ”0”<＝c<＝”9”：　#如果是数字，则直接输出 res.append(c) elif c in ops：　　　　#如果是运算符，则从栈顶开始让大于等于该运算符的元素出栈 　　while top！＝－1 and stack[top]！＝”(” and　ops[stack[top]]>ops[c]　：　#填空 res.append(stack[top])； top－＝1 top＋＝1；stack[top]＝c　　　　　 #当前运算符入栈 elif c＝＝”(”：　　 #如果是左括号，让当前运算符入栈 top＋＝1；stack[top]＝c elif c＝＝”)”：　 #如果是右括号，则从栈顶元素开始出栈，直到匹配到左括号 while top！＝－1 and stack[top]！＝”(”： res.append(stack[top])；top－＝1 　　#左括号也出栈，但不用输出 while top！＝－1： #把栈中剩余元素出栈 res.append(stack[top])；top－＝1 print(res) (3)上述程序段中加框处代码有误，请改正：　top－＝1　。 (4)程序运行后输入“(6＋(8－2)*3)/4”(不含引号)，当遍历到数字3(即c＝＝”3”)时，从栈顶到栈底的内容依次是　*＋(　。 【解析】 (1)后缀表达式，运算符放在运算对象之后。 (2)如果是运算符，则从栈顶开始让大于等于该运算符的元素出栈，条件“top！＝－1”判断是否栈空；条件“stack[top]！＝”(””没遇到左括号继续出栈；栈顶元素大于等于该运算符的元素出栈使用语句“ops[stack[top]]>ops[c]”。 (3)出栈没有删除列表元素，运行语句“res.pop()”，删除的不是当前栈顶元素，应使用“top－＝1”。 (4)( 6＋( 8－2 )*3 )/4 栈中元素：“(＋(－”，接着遇到“)”，出栈，栈中元素为“( ＋”，再入栈，栈中元素为“( ＋ *”；栈思维先进后出，答案为*＋(。 　　2023·余杭高中检测 自从学习了不同进制之后，小明设计了一个计算不同进制数的加法器，并用Python编程实现。输入一个加法算式，加数可以是十进制数、二进制数或者十六进制数，程序的功能是输出它们的和。例如，输入形如“1010B＋1DH＋109D＝”的加法算式后，执行程序输出“和是148”的结果。Python程序段如下： s＝input(＂请输入一个混合进制的加法算式：　＂) dic＝{＂B＂：2，＂D＂：10，＂H＂：16} st＝[＂＂]*100 top，i，x，m＝1，0，0，0 while i＜len(s)： if s[i]＝＝＂＋＂or s[i]＝＝＂＝＂： m＝①　dic[st[top]]　 top＝top－1 t＝0 while top！＝1： if st[top]＞＝＂A＂ and st[top]＜＝＂F＂： st[top]＝ord(st[top])－ord(＂A＂)＋10 else： st[top]＝int(st[top]) ②　x＝x＋st[top]*m**t　 t＝t＋1 top＝top－1 print(＂t＝＂，t，m，x) else： ③　top＝top＋1　 st[top]＝s[i] i＝i＋1 print(＂和是＂，x) (1)请在横线处填入合适的代码。 (2)若输入“1011B＋2DH＋178D＝”，则输出的结果是　234　。 【解析】 由程序可知列表st中保存着当前加数的每一位，当读到第一个加号时，列表st的值为[“1”，“0”，“1”，“0”，“B”]，当读到第二个加号时，st的值为[“1”，“D”，“H”]，当读到“＝”时，st的值为[“1”，“0”，“9”，“D”]。①列表st的最后一位是进制编号，读取st最后一位，通过字典dic得到进制值。②通过权值法把st列表中保存的不同进制的数转换为十进制数。③读取到加数的每一位数字，都保存在st列表的相应位置。 　　某工作系统为多任务系统， 可以启动多个任务， 但同一时刻只能运行一个任务。现有一批不同时刻到达且优先级(0表示最高级)互不相同的任务需要系统处理。 处理过程中， 优先级高的任务可抢占系统获得优先处理，编程计算各任务运行结束的顺序和系统运行效率。(系统运行效率＝各任务处理总时间/系统运行时间)。系统任务处理示例如下图所示： 当系统运行到第5秒初时，任务T0到达，系统空闲，可立即运行任务；第8秒初任务T1到达，且优先级高于正在运行的任务T0，任务T1抢占系统，优先处理，任务T0 挂起(暂停处理)；第13秒初任务T1处理结束，此时任务T2 到达，但优先级低于挂起任务T0，任务T2 挂起，任务T0恢复运行状态；第14秒初任务T0 结束…… 所有任务处理完毕后，程序输出结果：“任务结束的顺序：　T1，　T0，　T3，　T2，　系统本次处理效率：　76”。 (1)如有任务列表[[”T0”，2，2，3]，[”T1”，5，1，4]，[”T2”，6，0，5]，[”T3”，9，3，5]]，则系统处理完毕后，各任务结束的先后顺序为　T0，T2，T1，T3　(填写任务名，并用逗号分隔)。 (2)实现该功能的Python程序段如下，请在横线处填入合适的代码。 (3)程序段中加框处代码有误，请改正：　top！＝－1 or ready<n or busy　。 import time as tm def sort_priority(index，n)： #sort_priority()函数功能：调整index数组中的n＋1个挂起任务序号，确保从index[n]到index[0] 保存的挂起任务序号对应任务优先级为从高到低，代码略 return task＝[]　　　　　　　　#存放任务列表 n＝4 #存放任务数量 #task添加n个任务，代码略，示例：[[”T0”，5，2，4]，[”T1”，8，1，5]，[”T2”13，3，4]，[”T3”，16，0，3]] for i in range(n－1)： #按任务到达时间先后，对任务升序排序 for j in range(n－1，i，－1)： if①　task[j][1]<task[j－1][1]　： task[i]，task[i－1]＝task[j－1]，task[j] stack＝[－1]*n #存放挂起的任务序号 top＝－1 clock，order＝0，”” # clock模拟系统时钟，单位：秒；order 存放各任务结束的顺序 ready，runing＝0，－1 # ready存放新到达的任务序号；runing存放正在运行的任务序号 total＝0 #累计任务处理总时间 busy＝False #系统空闲状态，False为空闲 while ： if ready<n and task[ready][1]＝＝clock： total＋＝task[ready][3] if not busy： runing＝ready busy＝True elif task[runing][2]<task[ready][2]： top＋＝1 stack[top]＝ready ②　sort_priority(stack，top)　 else： top＋＝1 ③　stack[top]＝runing　 runing＝ready ready＋＝1 elif not busy and top！＝1： runing＝stack[top] top－＝1 clock＋＝1 tm.sleep(1) #程序暂停1秒 if busy： task[runing][3]－＝1 if task[runing][3]＝＝0： order＋＝task[runing][0]＋”，” if task[runing][3]＝＝0 and top＝＝－1： busy＝False elif task[runing][3]＝＝0 and top！＝－1： runing＝stack[top] top－＝1 percent＝round(④　total/clock　*100) print(”任务结束的顺序：　%s 系统本次处理效率：　%d”%(order，percent)) 【解析】 由表可知，各任务结束先后顺序为： T0，T2，T1，T3。 (2)①此处程序段的作用是利用冒泡排序，按照任务到达时间先后， 对任务列表进行升序排序。需要注意的是排序关键字存放在数组每个数据元素中索引为1的位置。 ②根据系统空闲状态、新到达任务ready和正在运行任务runing的优先级来决定系统下一步的任务处理情况。此处对应分支的条件为task[runing][2]<task[ready][2]，即正在运行任务runing的优先级高于新到达任务ready，故新到达任务ready需要压入挂起任务的栈中，此时需要将栈中所有挂起任务按照任务优先级重新进行从高到低排列，故此处需要调用自定义函数来完成此功能。 ③此处对应分支的条件为正在运行任务runing的优先级低于新到达任务ready，此时需要将正在运行任务runing压入挂起任务的栈中。 ④系统运行效率＝各任务处理总时间/系统运行时间，阅读程序可知，变量total表示各任务处理总时间，变量clock表示系统运行时间。 (3)当系统任务未处理完时，需要继续执行while循环。因此，若系统状态繁忙、挂起任务栈未处理完，或者新任务未遍历完时，需要继续执行。 |随|堂|检|测| 1．2023·富阳中学检测小明有一本口算练习册，但是做完之后需要校对，小明爸爸为此写了一个计算口算练习题的Python 程序。口算练习题存放在文件“calculate.txt”中，将每一个式子和计算得到的结果写入文件“ans.txt”中，两个文件中的部分内容如下图所示： 计算练习题的规则：①从左往右计算；②先计算括号内的式子；③乘除的优先级高于加减；④练习题中的除法计算默认是整除。考虑到运算符优先级的关系，小明爸爸的程序思路如下：①使用两个栈分别保存式子中的数字和运算符；②遇到“(”，运算符直接入栈；③遇到“)”，则先计算括号中的式子，碰到“(”停止；④对于运算符加减乘除，若先碰到乘除，或前后两者优先级相同，则先进行计算。以“13－(2＋1)*2＋7＝”为例： 字符 13 － ( 2 ＋ 1 ) * 2 ＋ 7 ＝ 数值栈a 13 13 13 13.2 13.2 13.2.1 13.3 13.3 13.3.2 13. 6 7 7.7 14 运算符栈b 空 － －，( －，( －，(，＋ －，(，＋ － －，* －，* － ＋ ＋ 空 说明 入栈 算加法 入栈 算乘法 算减法 算加法 请回答下列问题： (1)若有式子“5－4＋2＝”，当处理完字符“＋”后，数值栈a 中从栈底到栈顶的数值依次为　1　。 (2)实现上述功能的Python 程序如下，请在横线处填入合适的代码。 def cal(x，y，ch)： if ch＝＝”＋”： return x＋y elif ch＝＝”－”： return x－y elif ch＝＝”*”： return x*y return ①　x//y　 def writefile(filename，p)： #将p 写入到filename 中，代码略 f＝open(”calculate.txt”) pol＝[line.strip(” ”) for line in f．readlines()] for k in range(len(pol))： topa＝－1；topb＝－1 a＝[－1]*100；b＝[””]*100 i＝0 s＝pol[k] while i<len(s)： if s[i].isdecimal()： #判断字符s[i]是否为数字字符 t＝”” while s[i].isdecimal()： t＋＝s[i] i＋＝1 topa＋＝1 ②　a[topa]＝int(t)　 else： if s[i]＝＝”(”： topb＋＝1 b[topb]＝s[i] elif s[i]＝＝”)”： #处理括号内的式子 ch＝b[topb] while③　ch！＝”(”　： a[topa－1]＝cal(a[topa－1]，a[topa]，ch) topa－＝1 topb－＝1 ch＝b[topb] topb－＝1 else： ch＝b[topb] #处理前一个更高优先级或平级的运算符 while ch in [”＋”，”－”] and s[i] in [”＋”，”－”，”＝”] or ch in [”*”，”/”]： a[topa－1]＝cal(a[topa－1]，a[topal，ch) topa－＝1 topb－＝1 ch＝b[topb] topb＋＝1 ④　b[topb]＝s[i]　 i＋＝1 pol[k]＋＝str(a[0]) writefile(”ans.txt”，pol) 【解析】 (1)依题意，5、4 先入a 栈，“－”入b 栈，遇到“＋”号时，由于与“－”号优先级相同，先计算减法得1，随后处理“＋”入栈。故答案为1。 (2)①处自定义函数功能比较明显，对两个参数x，y 根据操作符ch 进行相应运算，代码缺少除法处理。题意表明是整除，故填x//y。 ②由于s[i]只是单个字符，若有连续多个数字，利用循环连接到字符串t 上。出循环后需将提取的数字入栈，topa 为栈顶指针。 ③循环体是不断从b 栈中弹出操作符进行相应运算。依题意可知，碰到“(”停止。 ④ch 为前一个运算符，s[i]为当前运算符，循环符合题干给出的条件。若前一个运算符与当前s[i]同级或前一运算符为”*”，”/”，此时依题意先做栈内运算。出循环后新的运算符s[i]入栈。 学科网（北京）股份有限公司 $$