Cho một biểu thức số học trung tố gồm số nguyên không âm, biến (một chữ cái thường), các toán tử + - * / và dấu ngoặc (không có ^, không có toán tử một ngôi). Hãy dựng AST rồi tính giá trị của biểu thức khi thay mỗi biến bởi giá trị được cho trước (định giá bằng cách duyệt AST - mỗi nút trong được tính bằng cách đệ quy tính hai cây con rồi áp dụng toán tử tương ứng).
Độ ưu tiên: *, / cao hơn +, -; các toán tử cùng độ ưu tiên kết hợp trái. Phép chia / chia lấy phần nguyên theo quy tắc làm tròn về 0, và đề bài đảm bảo mọi phép chia xuất hiện đều chia hết, không có phép chia cho 0.
Ví dụ: biểu thức (a+b)*c với a=2,b=3,c=4 cho kết quả (2+3)×4=20.
Dòng 1: biểu thức trung tố, chuỗi không chứa khoảng trắng, chỉ gồm chữ số (số nguyên không âm), chữ cái thường (biến), các ký tự + - * / ( ).
Dòng 2: số nguyên k - số lượng biến được gán giá trị.
k dòng tiếp theo, mỗi dòng gồm tên biến (một chữ cái thường) và giá trị nguyên của nó (có thể âm), cách nhau bởi một dấu cách.
Mọi biến xuất hiện trong biểu thức đều được gán giá trị đúng một lần trong danh sách trên.
In ra một số nguyên duy nhất - giá trị của biểu thức sau khi thay các biến.
Ví dụ:
Đầu vào:
(a+b)*c
3
a 2
b 3
c 4
Đầu ra:
20
Đầu vào:
a+b
2
a 3
b 4
Đầu ra:
7
Đang tải editor...