浙教版（2019）高中信息技术 选修1 第3章 3.3.2 栈的应用 课件（共20张PPT）

(共20张PPT)
栈的应用
为了帮助小学生检查口算作业，设计了“口算批改”程序，根据识别出来的算式，逐一计算，检验算式的正确性，并显示计算结果是否正确。
项目情境
要设计“口算批改”项目，我们需要解决哪些问题：
1.将口算图片转化为文本。
2.处理每一个算式，计算算式的正确答案。
3.输出判定结果。
将正确答案与输入的答案进行比较。
利用OCR识别技术，将图片识别为文本，并存入txt文件
口算批改项目—项目任务
要设计“口算批改”项目，我们需要解决哪些问题：
1.将口算图片转化为文本。
利用OCR识别技术，将图片识别为文本，并存入txt文件
口算批改项目
项目第一课时已经完成。
思考1：如何提取算式
例如：”6+(8-2)*2/3=10”
以字符串读入，先找出等号，等号左边是算式，等号右边是输入的结果
思考2：如何提取算式的数字与运算符
例如：”6+(8-2)*2/3=10”
分离算式中的数字和运算符。
数字可能有多位，所以需要循环取出数字，
运算符只有一位，只需逐位取出，取出后存入列表中。
要设计“口算批改”项目，我们需要解决哪些问题：
1.将口算图片转化为文本。
口算批改项目
要设计“口算批改”项目，我们需要解决哪些问题：
1.将口算图片转化为文本。
2.处理每一个算式，计算算式的正确答案。
3.输出判定结果。
将正确答案与输入的答案进行比较。
利用OCR识别技术，将图片识别为文本，并存入txt文件
口算批改项目
思考3:计算机如何处理加、减、乘、除、括号等运算符的优先级问题？
结合数学中的计算规律，加法和减法运算设置为同一级别，乘法和除法运算设置为同一级别，括号级别最高。
可以用字典来定义每个运算符的优先级，或者通过分支语句实现。
思考4:结合运算符的优先级，如何算得计算式的值？
先将表达式转为逆波兰表达式，再求得逆波兰表达式的值
口算批改项目-抽象建模
开始
读取等号左右两边表达式
将表达式转为逆波兰表达式
计算逆波兰表达式的值
判断计算所得的值与等号右边结果是否相等
读取文件获取每一行的算式
输出是否正确的结果
结束
口算批改项目
设计算法：如何将中缀表达式转为后缀表达式（有括号）
1、初始化运算符栈S1
2、依次从数组中取出各个字符，根据字符做不同处理
3、遇到操作数时，将其输出
4、遇到运算符时，比较其与S1栈顶运算符的优先级:
若S1为空，或栈顶运算符为左括号“(”,则直接将此运算符入栈;
否则，若优先级比栈顶运算符的高，也将运算符压入S1(注意必须是高，相同和低于都不行);
否则，将S1栈顶的运算符弹出，再次转到4与S1中新的栈顶运算符相比较:
5 、遇到括号时:
如果是左括号“(”，则直接压入S1;如果是右括号“)”，则依次弹出S1栈顶的运算符，直到遇到左括号为止，此时将这一对括号丢弃;
6、重复步骤2至5，直到表达式遍历结束
7、将S1中剩余的运算符依次弹出;
项目实施-设计算法
ops=[""]*20
top=-1
snbl=[] #存储逆波兰表达式
for i in a: #输出逆波兰表达式
if i in ops_rule:
while top>=-1:
if top==-1: #运算符栈为空，则入运算符栈ops
top+=1
ops[top]=i
break
else:
if ops[top]=="(" or ops_rule[i]>ops_rule[ops[top]]:
#若运算符栈不空，栈顶为左括号或者比栈顶元素优先级高，入栈
top+=1
ops[top]=i
break
else:#优先级比栈顶优先级相等或小
snbl.append(ops[top])
top-=1
项目实施-程序编写
ops_rule={ #字典，定义优先级
"+":1,
"-":1,
"*":2,
"/":2
}
ops=[""]*20
top=-1
snbl=[] #存储逆波兰表达式
for i in a: #输出逆波兰表达式
if i in ops_rule:
while top>=-1:
if top==-1: #运算符栈为空，则入运算符栈ops
top+=1
ops[top]=i
break
else:
if ops[top]=="(" or ops_rule[i]>ops_rule[ops[top]]:
#若运算符栈不空，栈顶为左括号或者比栈顶元素优先级高，入栈
top+=1
ops[top]=i
break
else:#优先级比栈顶优先级相等或小
snbl.append(ops[top])
top-=1
项目实施-程序编写
ops_rule={ #字典，定义优先级
"+":1,
"-":1,
"*":2,
"/":2
}
elif i=="(":
top+=1；ops[top]=i
elif i==")":
while top>=0: #运算符栈不空
if ops[top]=="(": #栈顶元素为左括号，则抛弃左括号，top减一
top-=1；break
else:
snbl.append(ops[top]) #栈顶元素不是左括号，则加入逆波兰表达式
top-=1
else:
snbl.append(i)
while top>=0:
snbl.append(ops[top])；top-=1
print("逆波兰表达式：")
for i in range(len(snbl)-1):
print(snbl[i],end=" ")
print(snbl[-1])
项目实施-程序编写
elif i=="(":
top+=1；ops[top]=i
elif i==")":
while top>=0: #运算符栈不空
if ops[top]=="(": #栈顶元素为左括号，则抛弃左括号，top减一
top-=1；break
else:
snbl.append(ops[top]) #栈顶元素不是左括号，则加入逆波兰表达式
top-=1
else:
snbl.append(i)
while top>=0:
snbl.append(ops[top])；top-=1
print("逆波兰表达式：")
for i in range(len(snbl)-1):
print(snbl[i],end=" ")
print(snbl[-1])
项目实施-程序编写
设计算法：如何计算逆波兰表达式的值？
项目实施-设计算法
6 8 2 - 4 * 3 / +
6+(8-2)*4/3
1、从左往右遍历逆波兰表达式
①若取到数字进栈
②若取到运算符则取出栈顶的两个数字进行运算，并将运算后将结果放入栈顶
2、循环遍历到最后，栈顶的值即为结果
3、根据逆波兰表达式计算得到等号左边算式的值，与等号右边的结果进行比较
①若相等，则输出正确
②若不相等，则输出错误
def js(op,x,y):
if op=="+":
return x+y
if op=="-":
return x-y
if op=="*":
return x*y
if op=="/":
return x/y
nbl=[""]*20 #用于计算逆波兰表达式的值
ntop=-1
for i in snbl:
if i in ops_rule: #如果i是符号
r=js(i,nbl[ntop-1],nbl[ntop])
ntop=ntop-2;ntop=ntop+1
nbl[ntop] = r
else:
ntop = ntop + 1
nbl[ntop] = i
print("计算结果：",end=" ")
if nbl[0]==int(s2):
print("计算正确!")
else:
print("计算错误!正确结果为：",nbl[0])
项目实施-程序编写
def js(op,x,y):
if op=="+":
return x+y
if op=="-":
return x-y
if op=="*":
return x*y
if op=="/":
return x/y
nbl=[""]*20 #用于计算逆波兰表达式的值
ntop=-1
for i in snbl:
if i in ops_rule: #如果i是符号
r=js(i,nbl[ntop-1],nbl[ntop])
ntop=ntop-2;ntop=ntop+1
nbl[ntop] = r
else:
ntop = ntop + 1
nbl[ntop] = i
print("计算结果：",end=" ")
if nbl[0]==int(s2):
print("计算正确!")
else:
print("计算错误!正确结果为：",nbl[0])
项目实施-程序编写
是否有其他思路呢？
6+(8-2)*4/3=14
数字栈
运算符栈
6
+
（
8
-
2
*
4
/
3
6
24
8
14
项目实施
课后作业：
编程：使用双栈的方法计算数学表达式的值
项目小结
“口算批改”项目，我们主要研究：
1.将口算图片转化为文本。
2.处理每一个算式，计算算式的正确答案。
3.输出判定结果。