Trong pha dịch ngược mã (decompilation), người ta cần khôi phục lại một biểu thức nguồn từ bytecode đã được biên dịch, phục vụ việc gỡ lỗi hoặc tối ưu hoá lại. Cho một chương trình bytecode chỉ gồm hai loại lệnh:
PUSH x: đẩy hằng số nguyên x (được biểu diễn nguyên văn dưới dạng chuỗi, có thể âm) vào đỉnh ngăn xếp.ADD, SUB, MUL, DIV: lấy ra hai phần tử trên đỉnh (gọi là B rồi A theo thứ tự lấy ra — B được đẩy vào sau nên lấy ra trước), tạo biểu thức con có ngoặc đầy đủ (A op B) với op tương ứng là + - * /, rồi đẩy biểu thức con đó (dưới dạng một chuỗi ký tự) trở lại ngăn xếp — tại bước dịch ngược này, ta không tính giá trị số, chỉ ghép chuỗi biểu thức.Bytecode được đảm bảo là kết quả biên dịch hợp lệ của đúng một biểu thức nhị phân duy nhất theo thứ tự hậu tố (postfix): sau khi xử lý hết mọi lệnh, ngăn xếp chuỗi biểu thức luôn còn lại đúng một phần tử.
Hãy khôi phục và in ra biểu thức trung tố (infix) tương ứng, với ngoặc đơn bao quanh mọi phép toán nhị phân (không rút gọn ngoặc theo độ ưu tiên toán tử, để biểu thức luôn rõ ràng và không mơ hồ), các toán tử và toán hạng cách nhau đúng một khoảng trắng.
Ví dụ: bytecode PUSH 1, PUSH 2, ADD, PUSH 4, PUSH 3, SUB, MUL (tương ứng biểu thức hậu tố 1 2 + 4 3 − ×) cho kết quả ((1 + 2) * (4 - 3)).
PUSH x (x là số nguyên, có thể âm, ∣x∣≤109) hoặc một trong ADD, SUB, MUL, DIV.In ra trên một dòng duy nhất biểu thức trung tố đầy đủ ngoặc tương ứng, đúng định dạng mô tả ở trên.
Ví dụ:
Đầu vào:
1
PUSH 5
Đầu ra:
5
Đầu vào:
3
PUSH 3
PUSH 4
ADD
Đầu ra:
(3 + 4)
Đang tải editor...