solution

Cho một biểu thức số học dạng trung tố (infix), viết liền không có khoảng trắng, gồm các toán hạng là chữ số đơn ($0$-$9$), các toán tử $+, -, \times, \div$ (ký hiệu + - * /) và dấu ngoặc đơn (, ). Độ ưu tiên chuẩn: *, / cao hơn +, -; các toán tử cùng độ ưu tiên tính từ trái sang phải (left-associative).

Trước tiên, hãy chuyển biểu thức sang dạng hậu tố (postfix / RPN) bằng thuật toán operator-precedence chuẩn (shunting-yard): duyệt từng ký tự từ trái sang phải, toán hạng đưa thẳng vào output; khi gặp toán tử, trước khi đẩy nó vào ngăn xếp toán tử phải lần lượt pop và đưa ra output mọi toán tử trên đỉnh ngăn xếp có độ ưu tiên $\ge$ độ ưu tiên toán tử hiện tại (và không phải (); dấu ) sẽ pop và xuất ra mọi toán tử cho đến khi gặp ( (bỏ luôn cặp ngoặc).

Sau đó, mô phỏng việc sinh mã cho máy ảo ngăn xếp thực thi biểu thức hậu tố này: mỗi toán hạng ứng với một lệnh đẩy 1 phần tử vào ngăn xếp, mỗi toán tử pop ra 2 phần tử rồi đẩy lại 1 kết quả (phép chia lấy phần nguyên làm tròn về 0). Hãy tính độ sâu ngăn xếp lớn nhất (số phần tử nhiều nhất từng có đồng thời trên ngăn xếp) trong suốt quá trình thực thi, và giá trị kết quả cuối cùng.

Ví dụ: biểu thức 3+4*2 có dạng hậu tố 3 4 2 * +; khi thực thi, ngăn xếp đạt độ sâu tối đa là $3$ (khi cả 3, 4, 2 cùng nằm trên ngăn xếp trước khi nhân); kết quả cuối cùng là $11$.