資源簡介

(共20張PPT)
棧的應(yīng)用
為了幫助小學(xué)生檢查口算作業(yè)，設(shè)計了“口算批改”程序，根據(jù)識別出來的算式，逐一計算，檢驗算式的正確性，并顯示計算結(jié)果是否正確。
項目情境
要設(shè)計“口算批改”項目，我們需要解決哪些問題：
1.將口算圖片轉(zhuǎn)化為文本。
2.處理每一個算式，計算算式的正確答案。
3.輸出判定結(jié)果。
將正確答案與輸入的答案進行比較。
利用OCR識別技術(shù)，將圖片識別為文本，并存入txt文件
口算批改項目—項目任務(wù)
要設(shè)計“口算批改”項目，我們需要解決哪些問題：
1.將口算圖片轉(zhuǎn)化為文本。
利用OCR識別技術(shù)，將圖片識別為文本，并存入txt文件
口算批改項目
項目第一課時已經(jīng)完成。
思考1：如何提取算式
例如：”6+(8-2)*2/3=10”
以字符串讀入，先找出等號，等號左邊是算式，等號右邊是輸入的結(jié)果
思考2：如何提取算式的數(shù)字與運算符
例如：”6+(8-2)*2/3=10”
分離算式中的數(shù)字和運算符。
數(shù)字可能有多位，所以需要循環(huán)取出數(shù)字，
運算符只有一位，只需逐位取出，取出后存入列表中。
要設(shè)計“口算批改”項目，我們需要解決哪些問題：
1.將口算圖片轉(zhuǎn)化為文本。
口算批改項目
要設(shè)計“口算批改”項目，我們需要解決哪些問題：
1.將口算圖片轉(zhuǎn)化為文本。
2.處理每一個算式，計算算式的正確答案。
3.輸出判定結(jié)果。
將正確答案與輸入的答案進行比較。
利用OCR識別技術(shù)，將圖片識別為文本，并存入txt文件
口算批改項目
思考3:計算機如何處理加、減、乘、除、括號等運算符的優(yōu)先級問題？
結(jié)合數(shù)學(xué)中的計算規(guī)律，加法和減法運算設(shè)置為同一級別，乘法和除法運算設(shè)置為同一級別，括號級別最高。
可以用字典來定義每個運算符的優(yōu)先級，或者通過分支語句實現(xiàn)。
思考4:結(jié)合運算符的優(yōu)先級，如何算得計算式的值？
先將表達式轉(zhuǎn)為逆波蘭表達式，再求得逆波蘭表達式的值
口算批改項目-抽象建模
開始
讀取等號左右兩邊表達式
將表達式轉(zhuǎn)為逆波蘭表達式
計算逆波蘭表達式的值
判斷計算所得的值與等號右邊結(jié)果是否相等
讀取文件獲取每一行的算式
輸出是否正確的結(jié)果
結(jié)束
口算批改項目
設(shè)計算法：如何將中綴表達式轉(zhuǎn)為后綴表達式（有括號）
1、初始化運算符棧S1
2、依次從數(shù)組中取出各個字符，根據(jù)字符做不同處理
3、遇到操作數(shù)時，將其輸出
4、遇到運算符時，比較其與S1棧頂運算符的優(yōu)先級:
若S1為空，或棧頂運算符為左括號“(”,則直接將此運算符入棧;
否則，若優(yōu)先級比棧頂運算符的高，也將運算符壓入S1(注意必須是高，相同和低于都不行);
否則，將S1棧頂?shù)倪\算符彈出，再次轉(zhuǎn)到4與S1中新的棧頂運算符相比較:
5 、遇到括號時:
如果是左括號“(”，則直接壓入S1;如果是右括號“)”，則依次彈出S1棧頂?shù)倪\算符，直到遇到左括號為止，此時將這一對括號丟棄;
6、重復(fù)步驟2至5，直到表達式遍歷結(jié)束
7、將S1中剩余的運算符依次彈出;
項目實施-設(shè)計算法
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]]:
#若運算符棧不空，棧頂為左括號或者比棧頂元素優(yōu)先級高，入棧
top+=1
ops[top]=i
break
else:#優(yōu)先級比棧頂優(yōu)先級相等或小
snbl.append(ops[top])
top-=1
項目實施-程序編寫
ops_rule={ #字典，定義優(yōu)先級
"+":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]]:
#若運算符棧不空，棧頂為左括號或者比棧頂元素優(yōu)先級高，入棧
top+=1
ops[top]=i
break
else:#優(yōu)先級比棧頂優(yōu)先級相等或小
snbl.append(ops[top])
top-=1
項目實施-程序編寫
ops_rule={ #字典，定義優(yōu)先級
"+":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])
項目實施-程序編寫
設(shè)計算法：如何計算逆波蘭表達式的值？
項目實施-設(shè)計算法
6 8 2 - 4 * 3 / +
6+(8-2)*4/3
1、從左往右遍歷逆波蘭表達式
①若取到數(shù)字進棧
②若取到運算符則取出棧頂?shù)膬蓚€數(shù)字進行運算，并將運算后將結(jié)果放入棧頂
2、循環(huán)遍歷到最后，棧頂?shù)闹导礊榻Y(jié)果
3、根據(jù)逆波蘭表達式計算得到等號左邊算式的值，與等號右邊的結(jié)果進行比較
①若相等，則輸出正確
②若不相等，則輸出錯誤
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("計算結(jié)果：",end=" ")
if nbl[0]==int(s2):
print("計算正確!")
else:
print("計算錯誤!正確結(jié)果為：",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("計算結(jié)果：",end=" ")
if nbl[0]==int(s2):
print("計算正確!")
else:
print("計算錯誤!正確結(jié)果為：",nbl[0])
項目實施-程序編寫
是否有其他思路呢？
6+(8-2)*4/3=14
數(shù)字棧
運算符棧
6
+
（
8
-
2
*
4
/
3
6
24
8
14
項目實施
課后作業(yè)：
編程：使用雙棧的方法計算數(shù)學(xué)表達式的值
項目小結(jié)
“口算批改”項目，我們主要研究：
1.將口算圖片轉(zhuǎn)化為文本。
2.處理每一個算式，計算算式的正確答案。
3.輸出判定結(jié)果。

展開更多......

收起↑