Trong giai đoạn sinh mã trung gian, trình biên dịch thường kiểm tra kiểu của biểu thức dạng hậu tố (RPN — Reverse Polish Notation) bằng một ngăn xếp kiểu (type stack), mô phỏng máy ảo dựa trên ngăn xếp.
Cho trước bảng khai báo k biến, mỗi biến có kiểu thuộc {int, float, bool, string}, và một biểu thức RPN gồm t token, mỗi token là một trong các dạng:
int/float/bool/string, phân loại như bài kiểm tra kiểu biểu thức số học).+ - * /: lấy ra 2 kiểu trên đỉnh ngăn xếp (phần tử pop thứ nhất là toán hạng phải, phần tử pop thứ hai là toán hạng trái), áp dụng đúng luật kiểm tra kiểu của bài kiểm tra kiểu biểu thức số học (widening int→float, string+string→string, các trường hợp còn lại lỗi), rồi đẩy kết quả trở lại ngăn xếp.(int) hoặc (float). Toán tử này lấy ra 1 kiểu trên đỉnh ngăn xếp; nếu kiểu đó là int hoặc float thì đẩy lại kiểu đích (int hoặc float); nếu là bool hoặc string thì đó là lỗi (không được ép kiểu qua lại giữa nhóm số và bool/string).Nếu tại bất kỳ bước nào ngăn xếp không đủ phần tử cần thiết (thiếu toán hạng), hoặc phép toán/ép kiểu không hợp lệ, toàn bộ biểu thức bị coi là lỗi kiểu. Sau khi xử lý hết token, nếu ngăn xếp còn lại đúng một phần tử thì đó là kiểu của biểu thức; nếu còn 0 hoặc nhiều hơn 1 phần tử, biểu thức cũng bị coi là lỗi kiểu.
Ví dụ: với 1 biến x:int và biểu thức x (float), ta đẩy int (kiểu của x) rồi ép sang float → kết quả float.
Dòng đầu là số nguyên k (0≤k≤100) — số biến khai báo.
Dòng tiếp theo gồm k token dạng tên:kiểu (ví dụ x:int), cách nhau bởi khoảng trắng — có thể bỏ trống dòng này nếu k=0.
Dòng tiếp theo là số nguyên t (1≤t≤1000) — số token của biểu thức RPN.
Dòng cuối gồm t token của biểu thức RPN, cách nhau bởi khoảng trắng.
In ra một dòng duy nhất: kiểu kết quả của biểu thức (int, float, bool, hoặc string), hoặc Type Error nếu biểu thức không hợp lệ.
Ví dụ:
Đầu vào:
2
x:int y:float
3
x y +
Đầu ra:
float
Đầu vào:
1
x:int
2
x (float)
Đầu ra:
float
Đang tải editor...