Thuật toán bẻ ghi

Loài người viết các biểu thức toán học dùng ký hiệu trung tố (infix notation) đã vài nghìn năm: [4+3*(2+7)/3-2]*3. Ký hiệu trung tố có bất lợi lớn là cần nhiều dấu ngoặc để phân biệt các biểu thức khác nhau: (4+2)*3 ≠ 4+2*3. Ký hiệu tiền tố, còn gọi là ký hiệu Ba Lan (Polish notation), giải phóng chúng ta khỏi gông xiềng nô lệ của các dấu ngoặc. Ký hiệu này do nhà logic học người Ba Lan Jan Łukasiewicz nghĩ ra khoảng năm 1924. Trong ký hiệu tiền tố thì ta luôn viết toán tử trước (hai) toán hạng. Ví dụ, biểu thức [4+3*(2+7)/3-2]*3 dùng ký hiệu tiền tố có thể viết bằng * - + 4 / * 3 + 2 7 3 2 3.

Đến những năm 1950, 1960 thì người ta mới nghĩ đến ký hiệu hậu tố (postfix notation), hay còn gọi là ký hiệu Ba Lan ngược. Ở ký hiệu hậu tố thì toán tử được viết sau (các) toán hạng. Dijkstra là một trong những người nghĩ ra và thiết kế thuật toán cho ký hiệu hậu tố đầu tiên. Lý do là máy tính thì hay đọc input từ trái sang phải, mà ký hiệu hậu tố làm cho việc định trị một biểu thức rất tiện lợi: ta định trị mỗi toán tử ngay sau khi toán tử được đọc từ input. Khi biết thời điểm ra đời của các ký hiệu tiền tố và hậu tố, tôi đã tương đối ngạc nhiên; trước đó cứ nghĩ là ký hiệu tiền tố và hậu tố phải ra đời sớm hơn như vậy.

Định trị một biểu thức viết bằng ký hiệu hậu tố là bài toán (lập trình) cơ bản nhất của lớp cấu trúc dữ liệu đầu tiên: ta đọc input từ trái sang phải, khi thấy toán hạng thì nhấn (push) vào chồng (stack), nếu thấy toán tử thì định trị toán từ dùng 2 toán hạng trên đỉnh chồng, bật (pop) hai toán hạng này ra và nhấn kết quả vào chồng.

Định trị một biểu thức viết bằng ký hiệu trung tố không đơn giản như vậy. Dijkstra thiết kế một thuật toán gọi là thuật toán bẻ ghi (shunting-yard algorithm), chuyển từ biểu thức trung tố thành biểu thức hậu tố. Tất nhiên, sau đó ta có thể định trị biểu thức hậu tố dùng thuật toán trên. Nếu ta chỉ cần định trị biểu thức trung tố thôi thì không cần phải chuyển trực tiếp thành hậu tố rồi mới định trị. Thuật toán bẻ ghi có thể định trị biểu thức trung tố dùng hai chồng: một chồng toán tử và môt chồng toán hạng, như sau. Ta quét input từ trái sang phải, đọc từng token một (đây là tác vụ cơ bản của một lexical analyzer). Mỗi token là một toán hạng, toán tử, hoặc dấu ngoặc. Để đơn giản ta giả sử chỉ có một loại ngoặc (), và chỉ có các toán tử nhị phân +-*/. Cộng trừ có trật tự ưu tiên nhỏ hơn hẳn nhân chia.

Trước hết xét trường hợp không có dấu ngoặc. Gọi tok là input token đang xét.

• Nếu tok là một toán hạng thì ta nhấn nó vào chồng toán hạng.
• Nếu tok là một toán tử op thì
  • Trong khi vẫn còn toán tử op' trên đỉnh chồng toán tử, với trật tự ưu tiên lớn hơn hoặc bằng op thì ta bật op' ra khỏi chồng toán tử, bật 2 toán hạng ra khỏi chồng toán hạng, tính kết quả của op' áp dụng vào 2 toán hạng, nhấn kết quả vào chồng toán hạng. Nếu không có đủ toán hạng thì ta có lỗi cú pháp.
  • Nhấn op vào chồng toán tử.

Cuối cùng, khi đã hết input thì ta định trị tất cả các toán tử trong chồng toán tử, từ đỉnh chồng xuống. Nếu cuối cùng chỉ còn một toán hạng trong chồng toán hạng thì đó là kết quả. Nếu còn khác 1 toán hạng thì trả về lỗi cú pháp.

Trong trường hợp có dấu ngoặc thì ta xem dấu ngoặc là một toán tử. Khi thấy dấu mở ngoặc thì nhấn vào chồng toán tử. Khi thấy dấu đóng ngoặc thì định trị toàn bộ các toán tử trên chồng toán tử cho đến dấu mở ngoặc và ấn kết quả vào chồng toán hạng. Nói chung là thay (expression) bằng một toán hạng trong chồng toán hạng. Nếu không thấy dấu mở ngoặc tương ứng thì ta có lỗi cú pháp.

Thuật toán bẻ ghi thật là đơn giản, dễ thương, cơ bản, và cực kỳ hữu dụng. Không may là nó không phát hiện được mọi loại lỗi cú pháp. Ví dụ: đưa cho thuật toán trên biểu thức (3 4 +)*2 nó sẽ trả về 14.

Hỏi: sửa thuật toán như thể nào để nó phát hiện được loại lỗi cú pháp trên? Để đơn giản, ta vẫn giả sử chỉ có các toán tử nhị phân +-*/.