solution

Trong sinh mã trung gian (intermediate code generation), một biểu thức hậu tố thường được thực thi bởi một máy ngăn xếp ảo (stack machine) với các lệnh PUSH (đẩy 1 giá trị) và POP (lấy 1 giá trị). Bài này yêu cầu vừa định giá biểu thức vừa đếm số lệnh của máy ảo, với phép tính được thực hiện trong số học modulo một số nguyên tố $p$ (để tránh tràn số và để phép chia luôn có kết quả xác định thông qua nghịch đảo modulo).

Cho một biểu thức hậu tố mà toán hạng là các biến chữ cái thường (a-z, có thể xuất hiện lặp lại), toán tử hai ngôi thuộc $\{+,-,\times,\div\}$ (+ - * /). Cho trước một số nguyên tố $p$ và giá trị (đã rút gọn modulo $p$, trong khoảng $[0, p-1]$) của từng biến xuất hiện trong biểu thức. Phép chia $\div$ được định nghĩa là nhân với nghịch đảo modulo $p$ của toán hạng bên phải, tính theo định lý Fermat nhỏ: $b^{-1} \equiv b^{p-2} \pmod p$ (đề bảo đảm toán hạng chia luôn khác $0 \bmod p$).

Máy ảo hoạt động như sau: gặp toán hạng, thực hiện 1 lệnh PUSH giá trị (đã rút gọn modulo $p$) của biến đó vào ngăn xếp; gặp toán tử, thực hiện 2 lệnh POP để lấy ra hai giá trị trên cùng (giá trị pop trước là toán hạng bên phải), tính kết quả modulo $p$ rồi thực hiện 1 lệnh PUSH kết quả đó.

Hãy in ra giá trị cuối cùng của biểu thức modulo $p$ (một số trong $[0,p-1]$), tổng số lệnh PUSH và tổng số lệnh POP đã thực hiện.

Ví dụ: với $p=7$, biểu thức a b +, $a=3, b=5$: kết quả $= (3+5) \bmod 7 = 1$; số lệnh PUSH $=3$ (đẩy $a$, đẩy $b$, đẩy kết quả), số lệnh POP $=2$.