Giải Chuyên đề Tin học 12 Chân trời sáng tạo bài 4: Ứng dụng của ngăn xếp
Bài 4: Ứng dụng của ngăn xếp
Giải Chuyên đề Tin học 12 bài 4: Ứng dụng của ngăn xếp được VnDoc.com sưu tầm và xin gửi tới bạn đọc cùng tham khảo. Mời các bạn cùng tham khảo thêm tại mục Tin học 12 Chân trời sáng tạo.
Khởi động trang 18 Chuyên đề Tin 12 Chân trời
Cho biết cách trình bày cách để kiểm tra số dấu mở ngoặc và số dấu đóng ngoặc tương ứng trong chuỗi "(((){[]}))" có bằng nhau hay không.
Lời giải:
Cách trình bày cách để kiểm tra số dấu mở ngoặc và số dấu đóng ngoặc tương ứng trong chuỗi "(((){[]}))" có bằng nhau hay không:
Một chuỗi có dấu ngoặc cân bằng khi mỗi dấu mở ngoặc được theo sau bởi một dấu đóng ngoặc tương ứng được đặt ở vị trí thích hợp và ngược lại. Ví dụ, các chuỗi sau "((({[]}))", "({})([])" có dấu ngoặc cân bằng và các chuỗi sau "((O)]}", "((()" có dấu ngoặc không cân bằng. Ngăn xếp có thể được sử dụng để kiểm tra các dấu ngoặc và đảm bảo tính hợp lệ của một biểu thức toán học hoặc lời gọi hàm trong ngôn ngữ lập trình. Em có thể dùng ngăn xếp để kiểm tra tính hợp lệ của chuỗi bằng cách duyệt qua từng kí tự, ở mỗi kí tự đang xét, em thực hiện như sau:
1. Nếu kí tự là dấu mở ngoặc ("(" hoặc "{" hoặc "I") thì thêm vào ngăn xếp với thao tác push.
2 Nếu kí tự là dấu đóng ngoặc (")" hoặc "}" hoặc "1") thì lấy ra kí tự ở đỉnh ngăn xếp với thao tác pop. Sau đó kiểm tra nếu kí tự được pop là dấu mở ngoặc tương ứng với dấu đóng ngoặc đang xét thì tiếp tục quá trình duyệt chuỗi, ngược lại thì trả về kết quả chuỗi có dấu ngoặc không cân bằng.
3. Bỏ qua nếu kí tự không phải là mở ngoặc hay đóng ngoặc.
Sau khi hoàn thành duyệt chuỗi, kiểm tra nếu ngăn xếp rỗng thì chuỗi có dấu ngoặc cân bằng. Ngược lại, nếu ngăn xếp không rỗng thì chuỗi có dấu ngoặc không cân bằng.
Câu hỏi trang 22 Chuyên đề Tin 12 Chân trời
Em hãy minh hoạ:
a) Kiểm tra tính hợp lệ của dấu ngoặc trong chuỗi [2 * (4 + 3) - 5] bằng cách sử dụng ngăn xếp.
b) Chuyển biểu thức (1 - 4) * 2 + 7 sang dạng hậu tố bằng cách sử dụng ngăn xếp.
Lời giải:
a) Kiểm tra tính hợp lệ của dấu ngoặc trong chuỗi [2 * (4 + 3) - 5] bằng cách sử dụng ngăn xếp.
Code như sau:
stack = []
for char in bieu_thuc:
if char == '(':
stack.append(char)
elif char == ')':
if not stack or stack[-1] != '(':
return False
stack.pop()
return len(stack) == 0
bieu_thuc_x = "[2 * (4 + 3) - 5]"
if kiem_tra_hop_le_ngoac(bieu_thuc_x):
print(f"Biểu thức {bieu_thuc_x} có dấu ngoặc hợp lệ.")
else:
print(f"Biểu thức {bieu_thuc_x} có dấu ngoặc không hợp lệ.")
Kết quả: Biểu thức [2 * (4 + 3) - 5] có dấu ngoặc hợp lệ.
b) Chuyển biểu thức (1 - 4) * 2 + 7 sang dạng hậu tố bằng cách sử dụng ngăn xếp.
Code như sau:
precedence = {'+': 1, '-': 1, '*': 2, '/': 2}
stack = []
output = []
for char in bieu_thuc:
if char.isdigit():
output.append(char)
elif char in precedence:
while (stack and stack[-1] != '(' and
precedence[char] <= precedence.get(stack[-1], 0)):
output.append(stack.pop())
stack.append(char)
elif char == '(':
stack.append(char)
elif char == ')':
while stack and stack[-1] != '(':
output.append(stack.pop())
stack.pop()
while stack:
output.append(stack.pop())
return ' '.join(output)
bieu_thuc_b = "(1 - 4) * 2 + 7"
bieu_thuc_hau_to = chuyen_sang_hau_to(bieu_thuc_y)
print(f"Biểu thức {bieu_thuc_b} sau khi chuyển sang dạng hậu tố là: {bieu_thuc_hau_to}")
Kết quả của đoạn mã trên sẽ là:
Biểu thức (1 - 4) * 2 + 7 sau khi chuyển sang dạng hậu tố là: 1 4 - 2 * 7
Luyện tập trang 22 Chuyên đề Tin 12 Chân trời
Viết chương trình kiểm tra tính hợp lệ của dấu ngoặc trong chuỗi biểu thức số học. Dữ liệu vào: chuỗi biểu thức số học.
Dữ liệu ra: nếu các dấu ngoặc cân bằng thì thông báo lên màn hình "Chuỗi có dấu ngoặc hợp lệ", ngược lại thông báo "Chuỗi có dấu ngoặc không hợp lệ".
Lời giải:
#Mã giả kiểm tra dấu ngoặc hợp lệ trong chuỗi biểu thức
checkParentheses (s)
openParentheses = ["[","{","("] closeParentheses = ["]","}",")"] khởi tạo ngăn xếp stack rỗng for c in s:
if c là là dấu mở ngoặc:
Thêm c vào stack
elif c là dấu đóng ngoặc:
if stack rỗng:
return False
#Danh sách các ngoặc mở
#Danh sách các ngoặc đóng
else:
pos = vị trí của c trong closeParentheses
c1 là dấu mở ngoặc ở vị trí pos (tương ứng với c) c2 là dấu mở ngoặc lấy ra từ stack
if c1 khác c2:
return False
if stack rỗng:
return True
else:
return False
* Hàm kiểm tra dấu ngoặc hợp lệ trong chuỗi:
#Hàm kiểm tra dấu ngoặc hợp lệ trong chuỗi biểu thức
def checkParentheses(s):
openParentheses = ["[","",""] closeParentheses = ["]","}",")"] stack initStack() for c in s:
if c in openParentheses: push(stack, c)
elif c in closeParentheses:
if isEmptyStack(stack):
return False
else:
#Danh sách các kí tự ngoặc mở #Danh sách các kí tự ngoặc đồng #Khởi tạo ngăn xếp rỗng #Duyệt mọi kí tự trong s
#Kiểm tra nếu c là dấu mở ngoặc
#Thêm c vào stack
#Ngược lại, nếu c là dấu đóng ngoặc
pos = closeParentheses.index(c) #Lấy vị trí của kí tự ngoặc đóng
c1 = openParentheses[pos]
c2 = pop(stack)
if c1 = c2:
return False
if isEmptyStack(stack):
return True
else:
return False
#Nếu stack rỗng, dấu ngoặc hợp lệ
#Ngược lại, chuỗi có dấu ngoặc không hợp lệ
Nhiệm vụ 1 trang 23 Chuyên đề Tin 12 Chân trời
Chuyển biểu thức dạng trung tố sang hậu tố
Yêu cầu: Cho biểu thức 2 * (4 + 3) - 5. Hãy viết chương trình để chuyển một biểu thức dạng trung tố sang biểu thức dạng hậu tố với giả sử toán hạng, toán tử trong chuỗi chỉ gồm 1 kí tự.
Chạy chương trình trên.
Dữ liệu vào: chuỗi biểu thức dạng trung tố.
Dữ liệu ra: chuỗi biểu thức dạng hậu tố.
Lời giải:
Sử dụng hàm isOperator() để kiểm tra kí tự là toán tử, hàm getPriority() để xác định độ ưu tiên của toán tử, hàm inFixtoPostfix() để chuyển biểu thức dạng trung tố sang dạng hậu tố
Hàm kiểm tra kí tự có phải là toán tử hay không:
def isoperator (c):
return c in '+-*/^'
Hàm kiểm tra độ ưu tiên của toán tử:
def getPriority (op):
if op '+' or op ==
return 1
elif op ==
return 2
elif op:
else:
return 3
return 0
or op '/':
chuyển biểu thức dạng trung tổ sang dạng hậu tố:
#Hàm chuyển biểu thức trung tổ sang hậu tổ
def inFixtoPostfix(infix):
infix infix.replace('[', '(').replace('1', ')').replace('(', '(').
Replace (‘}’, ‘)’)
Lace('}', ')')
stack initStack()
postfix = ""
for c in infix:
if c =='':
continue
#Bỏ qua khoảng trắng
#Nếu kí tự là toán hạng, thêm vào chuỗi hậu tố
if c.isalpha() or c.isdigit():
postfix += c
#Nếu kí tự là '(', thêm vào stack
elif (':
push(stack, c)
#Nếu kí tự là ')'
elif c == ')': #Lấy ra khỏi stack và thêm vào postfix cho đến khi gặp ( while not isEmptyStack(stack) and top (stack) != '(':
postfix += pop(stack)
pop(stack)
elif isOperator (c): #Toán tử
if c != '^':
while not isEmptyStack(stack) and getPriority(c) <= getPriority(top(stack)): postfix + pop (stack)
postfix + pop(stack)
push(stack, c)
stack): áng tạo
while not isEmptyStack (stack):
postfix += pop(stack)
return postfix
infix = '2* (4 + 3) - 5'
postfix = inFixtoPostfix (infix)
print("Biểu thức hậu tố: " postfix)
infix = '2^2^3'
postfix = inFixtoPostfix(infix)
print("Biểu thức hậu tố: ", postfix)
Nhiệm vụ 2 trang 24 Chuyên đề Tin 12 Chân trời
Nhiệm vụ: Viết chương trình tính giá trị của biểu thức số học với biểu thức đầu vào là biểu thức hậu tố.
Yêu cầu: Viết chương trình tính giá trị biểu thức số học dùng hàm chuyển biểu thức inFixtoPostfix(). Chạy chương trình trên.
Lời giải:
Sử dụng inFixtoPostfix() để chuyển biểu thức dạng trung tố sang dạng hậu tố.
Sử dụng hàm calPostfix() để tính giá trị biểu thức dạng hậu tố.
Hàm tính b op a, với a, b là toán hạng, op là toán tử:
def calculate(a, b, op): if op '+': return b+a
elif opa return b-a
elif op ==
return b*a
elif op '/':
return b/a
else:
return b**a
Hàm tính giá trị biểu thức dạng hậu tố:
def calPostfix(s): stack initStack() for op in s:
if not isoperator(op): push(stack, op)
else:
a = int(pop(stack)) b= int(pop(stack))
d = calculate(a, b, op) push(stack, d)
k = pop(stack)
return k
k = calPostfix ('245-+6*') print(k)
k = calPostfix ('243+*5-') print(k)
#Thêm tí
hạng vào stack
#Kiếm tr. nếu op là toán tử #Lấy toán hạng a ra khỏi stack
#Lấy toán hạng b ra khỏi stack
#Gọi calculate để thực hiện phép tính b op a #Thêm d vào stack
#Lấy phần tử còn lại trong stack
#Trả về kết quả
Vận dụng trang trang 25 Chuyên đề Tin 12 Chân trời
Nhiệm vụ. Chuyển biểu thức dạng trung tố sang tiền tố.
Yêu cầu: Viết chương trình chuyển một biểu thức dạng trung tố inFix sang dạng tiền tố preFix.
Dữ liệu vào: chuỗi biểu thức dạng trung tố.
Dữ liệu ra: chuỗi biểu thức dạng tiền tố.
Lời giải:
1. Sử dụng lệnh inFix = inFix[:-1] để đảo ngược chuỗi biểu thức trung tố. Ví dụ, *(2 – 7/3) * (2/8 – 4)" được chuyển thành ")4–8/2(*)3/7–2(".
2. Thay thế các dấu đóng ngoặc thành dấu mở ngoặc và dấu mở ngoặc thành dấu đóng ngoặc trong chuỗi biểu thức đã đảo ngược trong bước 1.
Ví dụ, chuỗi ")4–8/2(*)3/7−2(" được chuyển thành "(4 – 8/2) * (3/7 – 2)".
3. Gọi hàm inFixtoPostfix() chuyển từ biểu thức dạng trung tố sang dạng hậu tố. 4. Đảo ngược chuỗi biểu thức kết quả của 3.
5. Kết thúc.
