solution

Trong một trình biên dịch, khi định giá (evaluate) một biểu thức hậu tố (Reverse Polish Notation - RPN) bằng máy ngăn xếp (stack machine), số lượng ô nhớ ngăn xếp cần cấp phát tối đa chính là độ sâu ngăn xếp lớn nhất đạt được trong suốt quá trình định giá — đây là đại lượng quan trọng khi sinh mã máy (code generation), vì nó cho biết số thanh ghi/ô nhớ tạm tối thiểu bộ biên dịch cần dùng.

Cho một biểu thức hậu tố hợp lệ gồm các toán hạng là số nguyên (có thể âm) và các toán tử hai ngôi $+,\,-,\,\times,\,\div$ (ký hiệu trong đề lần lượt là + - * /). Quy tắc định giá bằng ngăn xếp: gặp toán hạng thì đẩy (push) giá trị vào ngăn xếp; gặp toán tử thì lấy ra (pop) hai giá trị trên cùng, gọi $x_1$ là giá trị được đẩy vào trước (nằm dưới) và $x_2$ là giá trị nằm trên đỉnh, tính $x_1 \text{ op } x_2$ rồi đẩy kết quả trở lại ngăn xếp. Phép chia $\div$ là chia lấy phần nguyên hướng về 0 (ví dụ $-7 \div 2 = -3$). Đề bảo đảm không có phép chia cho 0 và biểu thức luôn cho ra đúng một giá trị cuối cùng.

Hãy tính giá trị cuối cùng của biểu thức và độ sâu ngăn xếp lớn nhất (số phần tử nhiều nhất từng có mặt đồng thời trong ngăn xếp) trong suốt quá trình định giá.

Ví dụ: với biểu thức hậu tố 2 3 4 * +, ngăn xếp lần lượt là $[2], [2,3], [2,3,4], [2,12], [14]$ — độ sâu lớn nhất là $3$, giá trị cuối là $14$.