Cây cú pháp trừu tượng (Abstract Syntax Tree - AST) của một biểu thức số học có thể được duyệt theo thứ tự tiền tố (nút - trái - phải) để sinh ra ký pháp Ba Lan (Polish notation). Ngược lại, từ một chuỗi ký pháp tiền tố hợp lệ, ta luôn dựng lại được đúng một AST nhị phân.
Cho một biểu thức số học viết dưới ký pháp tiền tố, trong đó mỗi toán tử là toán tử hai ngôi thuộc tập {+,−,×,÷} (ký hiệu lần lượt bằng +, -, *, /). Hãy dựng AST tương ứng rồi tính giá trị của biểu thức.
Ví dụ: với biểu thức tiền tố + 3 * 4 5, AST có gốc là +, con trái là lá 3, con phải là nút * với hai lá 4 và 5. Giá trị: 3+(4×5)=23.
Một dòng duy nhất gồm các token cách nhau bởi đúng một dấu cách. Mỗi token là:
+, -, *, /; hoặc- phía trước để biểu diễn số âm, ví dụ -5; token này khác với token toán tử - vì có thêm chữ số theo sau nên không gây nhầm lẫn).Dãy token đảm bảo tạo thành đúng một cây nhị phân hợp lệ (mỗi toán tử luôn có đủ hai toán hạng con, có thể là số hoặc một biểu thức con khác). Phép chia / đảm bảo luôn chia hết; nếu cần chia số âm, kết quả lấy theo quy tắc làm tròn về 0.
In ra một số nguyên duy nhất - giá trị của biểu thức.
Ví dụ:
Đầu vào:
5
Đầu ra:
5
Đầu vào:
+ 3 * 4 5
Đầu ra:
23
Đang tải editor...