solution

Khi sinh mã cho biểu thức boolean, trình biên dịch thường dùng kỹ thuật đánh giá ngắn mạch (short-circuit evaluation) để tránh sinh và thực thi những đoạn mã không cần thiết: với $a \ \texttt{AND} \ b$, nếu $a$ đã là 0 (sai) thì kết quả chắc chắn là 0, trình biên dịch sinh mã nhảy (jump) qua toàn bộ đoạn mã tính $b$ mà không thực thi nó; với $a \ \texttt{OR} \ b$, nếu $a$ đã là 1 (đúng) thì kết quả chắc chắn là 1 và đoạn mã tính $b$ cũng bị bỏ qua hoàn toàn.

Cho một biểu thức logic dưới dạng tiền tố (prefix), gồm các token cách nhau bởi khoảng trắng: lá là hằng số 0 hoặc 1; nút trong là AND hoặc OR, mỗi nút luôn có đúng hai cây con (được ghi liền ngay sau, theo đúng ngữ nghĩa tiền tố, ví dụ AND 1 OR 0 1 nghĩa là $1 \ \texttt{AND} \ (0 \ \texttt{OR} \ 1)$).

Mô phỏng việc sinh mã và thực thi ngắn mạch theo đúng quy tắc trên (toán hạng trái của mỗi phép toán luôn được đánh giá; toán hạng phải chỉ được đánh giá khi không thể ngắn mạch), hãy xác định: (1) giá trị cuối cùng của biểu thức (0 hoặc 1), và (2) số lá thực sự được đánh giá (không bị bỏ qua do ngắn mạch tại một tổ tiên nào đó của nó).

Ví dụ: AND 1 OR 0 1 — lá trái của AND là 1 (đã đánh giá, không ngắn mạch được nên phải đánh giá vế phải OR 0 1): lá 0 được đánh giá, vì OR với vế trái 0 nên phải đánh giá tiếp lá 1. Tổng cộng 3 lá được đánh giá, kết quả cuối là 1. In ra: 1 3.

Ví dụ khác: AND 0 OR 1 1 — lá trái của AND là 0, ngắn mạch ngay lập tức (bỏ qua toàn bộ OR 1 1), chỉ 1 lá được đánh giá, kết quả là 0. In ra: 0 1.