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

Ký pháp nghịch đảo Ba Lan
Reserve Polish Notation (RPN)

I.- Giới thiệu
1.1- Lịch sử : “Ký pháp nghịch đảo Ba Lan” được phát minh vào khoảng giữa thập kỷ 1950 bởi Charles Hamblin - một Nhà triết học & khoa học máy tính người Úc - dựa theo công trình về ký pháp Ba Lan của nhà Toán học người Ba Lan Jan Łukasiewicz. J.Hamblin trình bày nghiên cứu của mình tại Hội nghị khoa học vào tháng 6 /1957 và chính thức công bố vào năm 1962.
Cả hai loại “Ký pháp này ”, tuy thế vẫn còn là mới lạ với nhiều người ở nước ta. NST đã có 1 bài giới thiệu về ký pháp Ba Lan của nhà Toán học người Ba Lan Jan Łukasiewicz trên Thư viện “Bài giảng-phần Công cụ toán học”; nay giới thiệu tiếp “Ký pháp nghịch đảo Ba Lan” với mức sơ lược để người có trình độ PTTH cũng hiểu.
1.2- Tên gọi & ý nghĩa: Để đơn giản hóa quá trình tính toán, Charles Hamblin dựa theo ký pháp Ba Lan đã đưa ra qui tắc biến đổi lại biểu thức thông thường từ trung tố - infix (vì toán tử nằm ở giữa hai toán hạng). về dạng hậu tố - postfix. Trong khi Ký pháp Balan là tiền tố. Do đó gọi là ký pháp nghịch đảo Ba Lan.
Có thể phân biệt ba dạng biểu diễn biểu thức toán học qua thí dụ thô sơ sau:
- Biểu thức trung tố: 4+5 ; Toán tử/phép tinh đặt giữa (như học phổ thông)
- Biểu thức tiền tố: + 4 5 ;Toán tử/phép tinh đặt trước (Ký pháp Balan )
- Biểu thức hậu tố: 4 5 + ;Toán tử/phép tinh đặt sau, (ngược với Ký pháp Balan)
Thật ra thuật ngữ Reserve Polish Notation (RPN) dich sang tiếng Viêt như thế cũng chưa “đắt” lằm, Vì phép biểu diễn theo hậu tố không “đối nghịch” nhau với Ký pháp Balan mà chỉ là cách bổ sung cho một “ Hệ phương pháp” ghi chép tính toán mà thôi !
Trình bày biểu thức toán học theo cách thông thường tuy tự nhiên với con người nhưng lại khá “khó chịu” đối với máy tính; vì nó không thể hiện một cách tường minh quá trình tính toán để đưa ra giá trị của biểu thức.
II- Ứng dụng “Ký pháp nghịch đảo Ba Lan”:

Khi lập trình, tính giá trị một biểu thức toán học là điều quá đỗi bình thường. Tuy nhiên, trong nhiều ứng dụng (như chương trình vẽ đồ thị hàm số chẳng hạn, trong đó chương trình cho phép người dùng nhập vào hàm số), ta cần phải tính giá trị của một biểu thức được nhập vào từ bàn phím dưới dạng một chuỗi. Với các biểu thức toán học đơn giản (như a+b) thì bạn có thể tự làm bằng các phương pháp tách chuỗi “thủ công”. Nhưng để “giải quyết” các biểu thức có dấu ngoặc, ví dụ như (a+b)*c + (d+e)*f ,  thì các phương pháp tách chuỗi đơn giản đều không khả thi.
Trong tình huống này, ta phải dùng đến Ký Pháp Nghịch Đảo Ba Lan
Để đơn giản cho việc minh họa, ta giả định rằng chuỗi biểu thức mà ta nhận được từ bàn phím chỉ bao gồm: các dấu mở ngoặc/đóng ngoặc; 4 toán tử cộng, trừ, nhân và chia (+, -, *, /); các toán hạng đều chỉ là các con số nguyên từ 0 đến 9; không có bất kỳ khoảng trắng nào giữa các ký tự.
Quá trình tính toán giá trị của biểu thức hậu tố là đọc biểu thức từ trái sang phải, nếu gặp một toán hạng (con số hoặc biến) thì push toán hạng này vào ngăn xếp; nếu gặp toán tử, lấy hai toán hạng ra khỏi ngăn xếp (stack), tính kết quả, đẩy kết quả trở lại ngăn xếp. Khi quá trình kết thúc thì con số cuối cùng còn lại trong ngăn xếp chính là giá trị của biểu thức đó.
Ví dụ: biểu thức trung tố : 5 + ((1 + 2) * 4) + 3
được biểu diễn lại dưới dạng hậu tố là (ta sẽ bàn về thuật toán chuyển đổi từ trung tố sang hậu tố sau):
5 1 2 + 4 * + 3 +
Quá trình tính toán sẽ diễn ra theo như bảng dưới đây:
Ký tự
Thao tác
Trạng thái stack

5
Push 5
5

1
Push 1
5, 1

2
Push 2
5, 1, 2

+
Tính 1 + 2 Push 3
5, 3

4
Push 4
5, 3, 4

*
Tính 3 * 4 Push 12
5, 12

+
Tính 12 + 5 Push 17
17

3
Push 3