Câu hỏi

Biểu thức dưới đây được biểu diễn dưới dạng hậu tố (ký pháp Ba Lan ngược). Giá trị kết quả của biểu thức này là gì? Ở đây, các số ở dạng thập phân, và các ký hiệu ‘+’, ‘−’, ‘*’, và ‘/’ đại diện cho các phép toán cộng, trừ, nhân, và chia tương ứng:
100 5 6 2 + * 12 4 / − − 36 −

Lời giải

Ký pháp nghịch đảo Ba Lan

Là một ký hiệu toán trong đó dấu đi theo toán hạng. Ví dụ trong ký hiệu thông thường, bài toán 1 cộng 2 được viết là: 1 + 2, với ký pháp nghịch đảo Ba Lan, thì bài toán lại viết là: 1 2 +. Hay ký hiệu thông thường là (1 + 2)*3 thì với ký pháp nghịch đảo Ba Lan sẽ là 1 2 + 3 *.
Ký hiệu có chữ Ba Lan trong đó vì trong thập niên 1920, nhà toán học Ba Lan Jan Łukasiewicz, sáng chế ký hiệu tiền tố (trong đó bài toán 3 cộng 2 lại viết là + 3 2) Ký hiệu RPN được đề xướng vào năm 1954 bởi Burks, Warren, and Wright và được phát minh lại do F. L. Bauer và E. W. Dijkstra vào đầu thập niên 1960 để giảm thiểu sử dụng bộ nhớ của máy tính và dùng ngăn xếp (stack) để tính những bài toán, nguồn wiki.
Một số lợi ích của ký pháp nghịc đảo Ba Lan đó là:
1. Không cần dấu ngoặc
Ví dụ với ký pháp thông thường cho biểu thức:(1 + 2) ∗ (4 − 3) chúng ta sẽ tốn 11 ký tư, bao gồm 4 ký tự cho 4 dấu ngoặc, nhưng với ký pháp Ba Lan nghịch đảo là: 1 2 + 4 3 - * sẽ chỉ tốn 7 ký tự như vậy tiết kiệm bộ nhở hơn .
2. Thực hiện phép toán ngay khi gặp toán tử
Cũng với(1 + 2) ∗ (4 − 3) thông thường chúng ta sẽ cần tính 2 phép tính trong ngoặc trước, nghĩa là sẽ tăng thêm dữ liệu cần lưu trữ, với ký pháp Ba Lan nghịch đảo chúng ta có thể dùng ngăn xếp để tính toán dữ liệu cần lưu trữ sẽ giảm đi và độ phức tạp cũng sẽ giảm đi nhiều.

Quay trở lại bài toán

Với biểu thức 100 5 6 2 + * 12 4 / − − 36 − chúng ta tính toán sử dụng ngăn xếp như sau:

  1. Đưa 100 vào ngăn xếp ta có: [100].
  2. Đưa 5 vào ngăn xếp ta có: [100, 5].
  3. Đưa 6 vào ngăn xếp ta có: [100, 5, 6].
  4. Đưa 2 vào ngăn xếp ta có: [100, 5, 6, 2].
  5. Gặp toán tử dấu +, lấy 2 và 6 ra khỏi ngăn xếp, tính phép cộng: 6 + 2 = 8 đưa 8 vào ngăn xếp ta có: [100, 5, 8].
  6. Gặp toán tử dấu *, lấy 8, 5 ra khỏi ngăn xếp, tính phép nhân: 5 * 8 = 40, đưa 40 vào ngăn xếp ta có: [100, 40].
  7. Đưa 12 vào ngăn xếp ta có: [100, 40, 12].
  8. Đưa 4 vào ngăn xếp ta có: [100, 40, 12, 4].
  9. Gặp dấu chia, lấy 4 và 12 ra, tính 12/4 = 3, đưa 3 vào ngăn xếp ta có: [100, 40, 3].
  10. Gặp dấu -, lấy 3 và 40 ra khỏi ngăn xếp, tính 40 - 3 = 37, đưa 37 vào ngăn xếp ta có: [100, 37].
  11. Gặp dấu -, lấy 37 và 100 ra khỏi ngăn xếp, tính 100 - 37 = 63, đưa 63 vào ngăn xếp ta có [63].
  12. Đưa 36 vào ngăn xếp ta có: [63, 36].
  13. Gặp dấu trừ, lấy 36 và 63 ra khỏi ngăn xếp, tính 63 - 36 = 27.
    Kết qủa cuối cùng chúng ta có 27.

Tổng kết lại

Như vậy chúng ta đã cùng nhau trả lời câu hỏi liên quan đến ký pháp nghịch đảo Ba Lan.

Cám ơn bạn đã quan tâm đến bài viết|video này. Để nhận được thêm các kiến thức bổ ích bạn có thể:

  1. Đọc các bài viết của TechMaster trên facebook: https://www.facebook.com/techmastervn
  2. Xem các video của TechMaster qua Youtube: https://www.youtube.com/@TechMasterVietnam nếu bạn thấy video/bài viết hay bạn có thể theo dõi kênh của TechMaster để nhận được thông báo về các video mới nhất nhé.
  3. Chat với techmaster qua Discord: https://discord.gg/yQjRTFXb7a