Trước khi sinh mã cho máy ảo ngăn xếp, trình biên dịch cần chuyển biểu thức viết ở dạng trung tố (infix) quen thuộc sang dạng hậu tố (postfix) bằng thuật toán Shunting-yard của Dijkstra.
Cho một biểu thức trung tố gồm toán hạng là biến (một chữ cái) hoặc hằng số nguyên không âm, các toán tử hai ngôi +,−,×,÷,∧ (ký hiệu + - * / ^, trong đó ^ là lũy thừa) và dấu ngoặc đơn (, ). Độ ưu tiên: ^ cao nhất, kế đến * và / (bằng nhau), thấp nhất là + và - (bằng nhau). Các toán tử + - * / kết hợp trái; riêng ^ kết hợp phải. Hãy sinh ra biểu thức hậu tố tương ứng.
Ví dụ: a + b * c có postfix là a b c *. Biểu thức a ^ b ^ c (kết hợp phải) có postfix là a b c ^ ^ (nghĩa là a(bc)).
Một dòng chứa biểu thức trung tố, các token (biến, số, toán tử, dấu ngoặc) cách nhau bởi đúng một khoảng trắng. Biểu thức luôn cân bằng ngoặc và hợp lệ về cú pháp.
In ra một dòng là biểu thức hậu tố, các token cách nhau bởi đúng một khoảng trắng, không chứa dấu ngoặc.
Ví dụ:
Đầu vào:
a + b * c
Đầu ra:
a b c * +
Đầu vào:
( a + b ) * c
Đầu ra:
a b + c *
Đang tải editor...