- Kiến thức lập trình
Chúng ta sẽ áp dụng kiến thức đã được học ở bài 6 của khoá CS 101 để hoàn thành trò chơi này:
- Stack và Queue trong Python.
- Câu lệnh điều kiện trong Python.
- Vòng lặp while và for trong Python.
- Câu lệnh input() để nhập dữ liệu trong Python.
- Câu lệnh print() để in thông báo ra màn hình.
- Nội dung trò chơi
Một vật dụng không thể thiếu với các bạn học sinh khi học Toán đó là máy tính cầm tay. Máy tính cầm tay giúp chúng ta tính toán những phép toán cộng, trừ, nhân, chia, và kết hợp với dấu ngoặc đơn. Hẳn bạn học sinh nào cũng biết đến ba câu thần chú quen thuộc khi tính một biểu thức nào đó theo thứ tự tính toán: “Nhân chia trước, cộng trừ sau. Trong ngoặc trước, ngoài ngoặc sau. Tính từ trái sang phải”. Chúng ta có thể sử dụng Python để mô phỏng lại máy tính cầm tay và giúp tính toán nhanh hơn các biểu thức đơn giản với số tự nhiên. Chúng ta có thể chơi thử trò chơi ở đây nhé: https://s4v.trinket.io/sites/calculator
- Bắt tay vào lập trình thôi nào!!!
a. Thuật toán
Mỗi biểu thức người chơi nhập vào sẽ có dạng chuỗi (string). Chuỗi có thể xem là một mảng. Chúng ta sẽ lấy lần lượt từng phần tử của mảng. Trong trò chơi, chúng ta sẽ có số tự nhiên và phép toán (cộng, trừ, nhân, chia, ngoặc đơn). Chúng ta sẽ tạo hai mảng. Một mảng để lưu các kết quả tính toán và một mảng để lưu các phép toán.
Vì chúng ta chỉ có thể lấy ra được từng chữ số nên cần tạo một biến để lưu kết quả số có nhiều chữ số. Ví dụ số có một chữ số: 5. Chúng ta thấy 5 = 0 * 10 + 5. Với số có hai chữ số: 35 = (0 * 10 + 3) * 10 + 5. Với số có ba chữ số: 475 = ((0 * 10 + 4) * 10 + 7) * 10 + 5. Như vậy với số, chúng ta có thể lấy các chữ số từ trái sang phải và sử dụng quy luật ở trên. Với mỗi số như vậy, chúng ta sẽ thêm vào mảng chứa kết quả.
Chúng ta có 4 phép toán: cộng, trừ, nhân, chia, dấu ngoặc đơn. Chúng ta sẽ chia các phép toán thành 3 nhóm: Nhóm 1: cộng và trừ, Nhóm 2: nhân và chia, Nhóm 3: dấu ngoặc đơn. Mỗi nhóm sẽ có một thứ tự ưu tiên, từ lớn đến bé là: Nhóm 2, Nhóm 1, Nhóm 3.
Khi đi qua các phần tử của chuỗi được nhập vào ban đầu, nếu chúng ta gặp phải phép toán cộng, trừ, nhân, chia, dấu mở ngoặc, chúng ta sẽ kiểm tra thứ tự ưu tiên của nó với phép toán xuất hiện ở trước nó tính từ trái sang phải trong biểu thức. Vì chúng ta phải thực hiện phép toán từ trái sang phải và ưu tiên cho phép toán nhân và chia nên nếu phép toán phía trước có độ ưu tiên lớn hơn hoặc bằng phép toán hiện tại thì chúng ta sẽ thực hiện phép toán phía trước trước. Sau đó, chúng ta sẽ xoá phép toán đó ra khỏi mảng lưu phép toán và thêm vào mảng phép toán hiện tại.
Khi đi qua các phần tử của chuỗi được nhập vào ban đầu, nếu chúng ta gặp phải phép toán mở ngoặc thì chúng ta sẽ thêm nó vào trong mảng phép toán và đợi đến khi gặp phép toán đóng ngoặc. Khi gặp phép toán đóng ngoặc, chúng ta sẽ thực hiện phép toán trong ngoặc và xoá hết các phép toán trong ngoặc và phép toán mở, đóng ngoặc sau khi thực hiện xong.
Chúng ta có thấy mảng lưu kết quả phép tính và mảng lưu phép toán giống những ngăn xếp (stacks) không nào? Chúng ta đã học ở bài 6 hai câu lệnh với ngăn xếp là push và pop, cùng với câu thần chú LIFO (Last In First Out). Vì chúng ta thực hiện phép toán từ trái sang phải và chúng ta cũng lấy các phép toán theo thứ tự từ trái sang phải nên nó sẽ tuân theo LIFO.
b. Code:
Bước 1: Viết chương trình chính của trò chơi
Tương tự với blog “Câu chuyện ngẫu nhiên”, chúng ta sẽ sử dụng biến cont và vòng lặp while để tiếp tục hoặc dừng lại trò chơi theo yêu cầu của người chơi. Ngoài ra, chúng ta sẽ sử dụng câu lệnh input() để hỏi người dùng nhập vào biểu thức cần tính. Câu lệnh input() cùng với câu lệnh điều kiện còn giúp hỏi người chơi có muốn tiếp tục trò chơi không. Câu lệnh print() sẽ in ra màn hình kết quả tính toán của hàm evaluate sẽ được viết ở bước 4.
cont = True
while cont:
formula = input('Nhập biểu thức cần tính với số tự nhiên (gồm các phép tính cộng, trừ, nhân, chia và dấu ngoặc đơn)')
print('Kết quả của biểu thức là: %s' % str(evaluate(formula)))
tiep = input('Bạn có muốn tiếp tục không (Y/N)?')
if tiep.upper() == 'Y':
cont = True
else:
cont = False
Bước 2: Viết hàm kiểm tra phép toán và thứ tự ưu tiên của phép toán:
Chúng ta sẽ viết hàm is_op để kiểm tra xem input có phải là một trong những phép toán cộng, trừ, nhân, chia hay không. Chúng ta sẽ sử dụng câu lệnh in. Câu lệnh trả về True hoặc False.
def is_op(c):
return c in ['+', '-', '*', '/']
Tiếp theo, chúng ta sẽ viết hàm priority để trả về thứ tự ưu tiên của phép toán. Phép toán nhân chia sẽ được thực hiện trước, nên có thứ tự ưu tiên là 2. Phép toán cộng trừ có thứ tự ưu tiên 1. Phép toán mở ngoặc có thứ tự ưu tiên là -1. Những phép toán nào có thứ tự ưu tiên cao hơn sẽ được thực hiện trước.
def priority(op):
if op == '+' or op == '-':
return 1
if op == '*' or op == '/':
return 2
return -1
Bước 3: Viết hàm thực hiện phép toán:
Chúng ta sẽ viết hàm process_op nhận vào ngăn xếp lưu kết quả phép toán và phép toán. Hàm thêm kết quả phép toán mới vào ngăn xếp và trả về ngăn xếp. Với mỗi phép toán mới, chúng ta sẽ lấy ra kết quả trước và sau phép toán đó từ ngăn xếp bằng câu lệnh .pop(). Sau đó hàm sẽ thực hiện phép toán và thêm kết quả vào ngăn xếp.
Trường hợp đặc biệt: Số chia bằng 0 trong phép chia thì chúng ta sẽ thêm vào ngăn xếp kết quả vô cùng (∞). Trong Python sẽ là float(“inf”). Chúng ta sẽ sử dụng ký tự đặc biệt này để dừng vòng lặp ở hàm chính được viết ở bước 4.
def process_op(st, op):
r = st.pop()
l = st.pop()
if op == '+':
st.append(l + r)
elif op == '-':
st.append(l - r)
elif op == '*':
st.append(l * r)
elif op == '/':
if r == 0:
print('Biểu thức có phép chia cho 0: ' + str(l) + '/' + str(r))
st.append(float("inf"))
else:
st.append(l / r)
return st
Bước 4: Viết hàm evaluate:
Hàm evaluate nhận vào chuỗi s và in ra kết quả tính toán cuối cùng. Chúng ta sẽ tạo 2 ngăn xếp bằng mảng. Ngăn xếp st để lưu các kết quả tính toán và ngăn xếp op để lưu các phép toán. Chúng ta sẽ sử dụng vòng lặp for cùng với hàm range và len để đi qua các phần tử của chuỗi. range(len(s)) dùng để tạo một mảng gồm các số tự nhiên bắt đầu từ 0 với các phần tử nhỏ hơn chiều dài của mảng s. Các phần tử này tương ứng với index của các phần tử của chuỗi s.
Trường hợp thứ nhất khi phần tử trong chuỗi là khoảng trắng thì chúng ta sẽ không làm gì, và tiếp tục đi đến phần tử khác của chuỗi bằng câu lệnh continue. Trường hợp thứ hai khi phần tử trong chuỗi là dấu mở ngoặc, chúng ta sẽ thêm phép toán mở ngoặc vào ngăn xếp op. Trường hợp thứ ba khi phần tử trong chuỗi là một chữ số, chúng ta sẽ tìm tiếp từ phần tử đó đến hết chuỗi xem có chữ số nào nối tiếp không để tạo thành một số có nhiều chữ số. Để tìm xem phần tử có phải là số không, chúng ta có thể sử dụng câu lệnh isnumeric(). Để lấy ra các phần tử tiếp theo chúng ta có thể sử dụng vòng lặp for cùng với hàm range. range(i, len(s)) dùng để tạo một mảng gồm các số tự nhiên bắt đầu từ i với các phần tử nhỏ hơn chiều dài của mảng s. Để dừng lại khi không còn gặp các chữ số liên tiếp trong chuỗi, chúng ta dùng câu lệnh break.
Chúng ta sẽ tính ra giá trị của số có nhiều chữ số bằng công thức ở phần Thuật toán. Khi tính ra số, chúng ta sẽ thêm số đó vào ngăn xếp st (push) bằng câu lệnh .append(). Vì vòng lặp khi đi qua từng phần tử của chuỗi sẽ tăng index lên 1 đơn vị, nên để tránh bị lỗi khi có nhiều chữ số liền nhau, tạo thành một số có nhiều chữ số, chúng ta sẽ sử dụng một mảng có kích thước bằng với kích thước của chuỗi. Mảng này sẽ có kiểu dữ liệu boolean và được khởi tạo bằng False với tất cả các phần tử của mảng. Các phần tử của mảng này sẽ được gán là True nếu nó tương ứng với các chữ số đã đi qua trong chuỗi s. Như vậy chúng ta chỉ xét những vị trí có giá trị False.
st = []
op = []
mst = [False] * len(s)
for i in range(len(s)):
if s[i] == ' ':
continue
elif s[i] == '(':
op.append('(')
elif not mst[i]:
num = 0
for j in range(i, len(s)):
if s[j].isnumeric():
num = num * 10 + int(s[j])
mst[j] = True
else:
break
st.append(num)
Trường hợp thứ tư khi phần tử trong chuỗi là một trong các phép toán cộng, trừ, nhân, chia. Chúng ta có thể kiểm tra việc này bằng hàm is_op. Chúng ta sẽ so sánh thứ tự ưu tiên của phép toán đó với thứ tự ưu tiên của phép toán trước đó. Nếu phép toán trước đó có thứ tự ưu tiên lớn hơn hoặc bằng thứ tự ưu tiên của phép toán hiện tại thì chúng ta sẽ thực hiện phép toán trước đó bằng hàm process_op và bỏ phép toán trước đó ra khỏi mảng op bằng câu lệnh .pop() với ngăn xếp cho đến khi ngăn xếp op không còn phần tử nào. Hàm process_op nhận vào 2 inputs là mảng st để lưu kết quả của phép tính và phép toán trước đó. Chúng ta có thể dùng vòng lặp while để làm việc này. Cuối cùng chúng ta sẽ thêm phép toán hiện tại vào mảng op (push) bằng câu lệnh .append().
elif is_op(s[i]):
cur_op = s[i]
while len(op) != 0 and priority(op[-1]) >= priority(cur_op):
st = process_op(st, op[-1])
op.pop()
op.append(cur_op)Trường hợp thứ năm khi phần tử trong chuỗi là dấu đóng ngoặc thì chúng ta sẽ thực hiện các phép toán trước đó bằng hàm process_op cho đến khi gặp dấu mở ngoặc trong ngăn xếp op. Sau khi thực hiện mỗi phép toán, chúng ta phải bỏ phép toán vừa thực hiện ra khỏi ngăn xếp op bằng câu lệnh .pop(). Và cuối cùng là phải bỏ dấu mở ngoặc tương ứng ra khỏi ngăn xếp op.
elif s[i] == ')':
while op[-1] != '(':
st = process_op(st, op[-1])
op.pop()
op.pop()Chúng ta sẽ dừng vòng lặp đi qua các phần tử của s nếu trong ngăn xếp st có kết quả vô cùng (khi chia cho 0). Cuối cùng sau khi đi hết các phần tử của chuỗi s, chúng ta sẽ phải thực hiện các phép toán còn lại trong ngăn xếp op và bỏ phép toán vừa thực hiện ra khỏi ngăn xếp cho đến khi hết phần tử trong ngăn xếp.
while op:
st = process_op(st, op[-1])
op.pop()
Code hoàn chỉnh của hàm evaluate là
def evaluate(s):
st = []
op = []
mst = [False] * len(s)
for i in range(len(s)):
if s[i] == ' ':
continue
elif s[i] == '(':
op.append('(')
elif s[i] == ')':
while op[-1] != '(':
st = process_op(st, op[-1])
op.pop()
op.pop()
elif is_op(s[i]):
cur_op = s[i]
while len(op) != 0 and priority(op[-1]) >= priority(cur_op):
st = process_op(st, op[-1])
op.pop()
op.append(cur_op)
elif not mst[i]:
num = 0
for j in range(i, len(s)):
if s[j].isnumeric():
num = num * 10 + int(s[j])
mst[j] = True
else:
break
st.append(num)
if float("inf") in st:
break
while op:
st = process_op(st, op[-1])
if float("inf") in st:
break
op.pop()
return st[0]
4. Tada!!!
Như vậy chúng ta đã hoàn thành trò chơi rồi đấy. Thật đơn giản đúng không nào. Chúng ta cần thêm một điều kiện nếu kết quả từ hàm evaluate khác vô cùng thì sẽ in kết quả ra màn hình.
Code hoàn chỉnh sẽ là:
# -*- coding: utf-8 -*-
def is_op(c):
return c in ['+', '-', '*', '/']
def priority(op):
if op == '+' or op == '-':
return 1
if op == '*' or op == '/':
return 2
return -1
def process_op(st, op):
r = st.pop()
l = st.pop()
if op == '+':
st.append(l + r)
elif op == '-':
st.append(l - r)
elif op == '*':
st.append(l * r)
elif op == '/':
if r == 0:
print('Biểu thức có phép chia cho 0: ' + str(l) + '/' + str(r))
st.append(float("inf"))
else:
st.append(l / r)
return st
def evaluate(s):
st = []
op = []
mst = [False] * len(s)
for i in range(len(s)):
if s[i] == ' ':
continue
elif s[i] == '(':
op.append('(')
elif s[i] == ')':
while op[-1] != '(':
st = process_op(st, op[-1])
op.pop()
op.pop()
elif is_op(s[i]):
cur_op = s[i]
while len(op) != 0 and priority(op[-1]) >= priority(cur_op):
st = process_op(st, op[-1])
op.pop()
op.append(cur_op)
elif not mst[i]:
num = 0
for j in range(i, len(s)):
if s[j].isnumeric():
num = num * 10 + int(s[j])
mst[j] = True
else:
break
st.append(num)
if float("inf") in st:
break
while op:
st = process_op(st, op[-1])
if float("inf") in st:
break
op.pop()
return st[0]
cont = True
while cont:
formula = input('Nhập biểu thức cần tính với số tự nhiên (gồm các phép tính cộng, trừ, nhân, chia và dấu ngoặc đơn)')
result = evaluate(formula)
if result != float("inf"):
print('Kết quả của biểu thức là: %s' % str(evaluate(formula)))
tiep = input('Bạn có muốn tiếp tục không (Y/N)?')
if tiep.upper() == 'Y':
cont = True
else:
cont = False
Chương trình của chúng ta mới chỉ thực hiện các phép toán đơn giản với số tự nhiên. Các bạn học sinh hãy thử sáng tạo, cải tiến code để có thể thực hiện các phép toán với cả số thập phân và luỹ thừa, căn bậc hai nhé! Sau khi hoàn thành dự án cá nhân, các bạn đừng quên chia sẻ chương trình của mình lên STEAMese Profile để thầy cô và các bạn cùng trải nghiệm.
— — —
STEAM for Vietnam Foundation là tổ chức phi lợi nhuận 501(c)(3) được thành lập tại Hoa Kỳ với sứ mệnh thúc đẩy các hoạt động liên quan tới giáo dục STEAM (Science — Khoa học, Technology — Công nghệ, Engineering — Kỹ thuật, Arts — Nghệ thuật, Mathematics — Toán học) tại Việt nam. STEAM for Vietnam được thành lập và vận hành bởi đội ngũ tình nguyện viên là du học sinh và chuyên gia người Việt trên khắp thế giới.
— — —
📧Email: hello@steamforvietnam.org
🌐Website: www.steamforvietnam.org
🌐Fanpage: STEAM for Vietnam
📺YouTube: http://bit.ly/S4V_YT
🌐Zalo: Zalo Official