Đây là bước sinh mã (code generation) trong một trình biên dịch: chuyển một biểu thức số học viết ở dạng trung tố (infix) thành bytecode cho máy ảo ngăn xếp.
Biểu thức đầu vào chỉ gồm các số nguyên không âm (có thể nhiều chữ số), các phép toán + - * / và dấu ngoặc đơn ( ), không chứa khoảng trắng, tuân theo thứ tự ưu tiên toán học thông thường (∗,/ ưu tiên cao hơn +,−), các phép cùng mức ưu tiên tính từ trái sang phải (left-associative), biểu thức được đảm bảo hợp lệ và ngoặc cân bằng.
Hãy áp dụng đúng thuật toán Shunting-yard kinh điển của Dijkstra để chuyển biểu thức sang dạng hậu tố (postfix/RPN), sau đó sinh ra bytecode tương ứng theo quy tắc: mỗi toán hạng (số) sinh ra lệnh PUSH x; mỗi toán tử + - * / sinh ra lần lượt lệnh ADD, SUB, MUL, DIV — theo đúng thứ tự xuất hiện trong dãy hậu tố.
Quy tắc Shunting-yard cần áp dụng: khi gặp một toán tử mới, trước khi đẩy nó vào ngăn xếp toán tử, phải lần lượt lấy ra (và đưa vào dãy hậu tố) mọi toán tử đang ở đỉnh ngăn xếp toán tử có độ ưu tiên lớn hơn hoặc bằng độ ưu tiên của toán tử mới (và không phải dấu (); khi gặp ), lấy ra mọi toán tử cho tới khi gặp ( tương ứng (và bỏ luôn cặp ngoặc này khỏi ngăn xếp, không đưa vào dãy hậu tố).
Ví dụ: biểu thức 3+4*2 có dạng hậu tố là 3 4 2 * +, sinh ra bytecode:
PUSH 3
PUSH 4
PUSH 2
MUL
ADD
Một dòng duy nhất chứa biểu thức trung tố (độ dài từ 1 đến 300 ký tự), chỉ gồm chữ số 0-9, các ký tự + - * /, và dấu ngoặc ( ), không có khoảng trắng.
Dòng đầu tiên in ra số nguyên m — tổng số lệnh bytecode sinh ra. m dòng tiếp theo, mỗi dòng là một lệnh theo đúng thứ tự sinh mã, ở dạng PUSH x (với x là số nguyên không âm, giữ nguyên không thêm số 0 ở đầu) hoặc một trong ADD, SUB, MUL, DIV.
Ví dụ:
Đầu vào:
(3+4)*2
Đầu ra:
5
PUSH 3
PUSH 4
ADD
PUSH 2
MUL
Đầu vào:
3+4*2
Đầu ra:
5
PUSH 3
PUSH 4
PUSH 2
MUL
ADD
Đang tải editor...