Khác với bài toán sinh TAC từ biểu thức hậu tố, ở đây đầu vào là một biểu thức trung tố (infix) có thể chứa dấu ngoặc và các toán tử với độ ưu tiên khác nhau: *, / ưu tiên cao hơn +, -; các toán tử cùng độ ưu tiên kết hợp trái (left-associative); dấu ngoặc ( ) có thể ghi đè thứ tự ưu tiên.
Hãy chuyển biểu thức sang dạng hậu tố bằng thuật toán Shunting-Yard (Dijkstra), sau đó mô phỏng ngăn xếp như bài sinh TAC từ hậu tố để sinh ra danh sách lệnh mã ba địa chỉ.
Ví dụ: 12 + x * ( y - 3 ) / z sinh ra t1 = y - 3, t2 = x * t1, t3 = t2 / z, t4 = 12 + t3, kết quả là t4.
Một dòng duy nhất chứa biểu thức trung tố; các token (toán hạng, toán tử, dấu ngoặc) được phân tách bởi đúng một khoảng trắng. Toán hạng là chữ cái thường (a-z) hoặc số nguyên không âm. Số lượng token không vượt quá 50.
Dòng đầu tiên: số nguyên K — số lệnh TAC được sinh ra (bằng số toán tử trong biểu thức). K dòng tiếp theo: các lệnh dạng tI = a op b theo đúng thứ tự sinh. Dòng cuối cùng: result = Z với Z là toán hạng/biến tạm mang giá trị của toàn biểu thức (nếu K=0, Z chính là toán hạng duy nhất).
Ví dụ:
Đầu vào:
a + b * c
Đầu ra:
2
t1 = b * c
t2 = a + t1
result = t2
Đầu vào:
( a + b ) * c
Đầu ra:
2
t1 = a + b
t2 = t1 * c
result = t2
Đang tải editor...