Bài tập | NEU OJ

Trong một bộ phân tích cú pháp LR (Shift-Reduce), quá trình phân tích một chuỗi vào được ghi lại thành một vết (trace) gồm dãy các hành động liên tiếp. Mỗi hành động thuộc một trong các dạng sau:

Sk: dịch chuyển (shift) — đẩy một ký hiệu vào ngăn xếp và chuyển sang trạng thái $k$ ( $k \ge 0$ là số nguyên, có thể nhiều chữ số).
Rk: rút gọn (reduce) — áp dụng luật sinh số $k$ để thu gọn đỉnh ngăn xếp.
acc: chấp nhận (accept) — chuỗi vào hợp lệ, quá trình phân tích kết thúc thành công.
err: lỗi (error) — bộ phân tích phát hiện lỗi cú pháp, quá trình dừng lại.

Vết luôn kết thúc bằng đúng một dòng acc hoặc err, và đây là dòng cuối cùng của vết (không có hành động nào sau đó). Hãy đọc vết và cho biết: có bao nhiêu hành động dịch chuyển, bao nhiêu hành động rút gọn xuất hiện trong vết (không tính dòng acc/err), và kết quả cuối cùng của quá trình phân tích.

Ví dụ: với vết gồm 5 dòng S3, S5, R2, S7, acc, có 3 lần dịch chuyển, 1 lần rút gọn, kết quả là chấp nhận.

Định dạng đầu vào:
Dòng đầu tiên chứa số nguyên $n$ ( $1 \le n \le 1000$ ) — số dòng của vết. $n$ dòng tiếp theo, mỗi dòng là một hành động theo đúng một trong các dạng Sk, Rk, acc, err (không có khoảng trắng thừa). Dòng cuối cùng (dòng thứ $n$ ) chắc chắn là acc hoặc err.
Định dạng đầu ra:
In ra đúng 3 dòng:
- Dòng 1: số lượng hành động dịch chuyển (shift).
- Dòng 2: số lượng hành động rút gọn (reduce).
- Dòng 3: ACCEPT nếu dòng cuối là acc, hoặc ERROR nếu dòng cuối là err.

solution

Đề bài: [Trình biên dịch] Đếm hành động trong vết phân tích Shift-Reduce