NKTEST - Kiểm tra chương trình

Problem

https://vn.spoj.com/problems/NKTEST

https://oj.vnoi.info/problem/NKTEST

Test tuy không phải là phương pháp để chứng minh tính đúng đắn của chương trình, nhưng vẫn được sử dụng rộng rãi để phát hiện lỗi sai và tăng độ tin cậy. Có nhiều phương pháp hiệu chỉnh chương trình, nhưng nội dung chủ yếu vẫn dựa trên cơ sở chọn các bộ tests để đi vào các nhánh khác nhau của chương trình.

Cho mô tả chương trình dưới dạng các dòng lệnh. Các lệnh tuyến tính được ký hiệu là S, lệnh rẽ nhánh không đầy đủ được xác định bởi 2 câu lệnh IF và END_IF, lệnh rẽ nhánh đầy đủ được xác định bởi 3 câu lệnh IF, ELSE, và END_IF. Điều kiện sau IF được bỏ qua trong mô tả. Chương trình kết thúc bằng lệnh ENDPROGRAM.

Yêu cầu

Xác định số lượng tests cần thiết để kiểm tra tất cả các nhánh của chương trình.

Dữ liệu

Gồm nhiều dòng, mô tả một chương trình theo định dạng đã nêu.

Kết quả

Gồm 1 dòng duy nhất, chứa số lượng tests cần thiết để kiểm tra tất cả các nhánh của chương trình.

Giới hạn

Kết quả không vượt quá 2^31-1

Ví dụ

Ví dụ 1

Input
S
IF
S
S
ELSE
IF
IF
S
ELSE
S
END_IF
S
ELSE
S
END_IF
END_IF
S
ENDPROGRAM

Output
4

Ví dụ 2

Input
S
IF
END_IF
ENDPROGRAM

Output
2

Ví dụ 3

Input
S
S
ENDPROGRAM

Output
1

Tutorial

Bài này có 2 trường hợp:

Merge 2 nhánh từ IF và ELSE dùng phép +. Nếu không có nhánh ELSE thì default là 1.
Tính lại số test trên 1 nhánh (IF hoặc ELSE), tức là trên cùng 1 nhánh sẽ có những bộ IF/END_IF hoặc IF/ELSE/END_IF, khi đó số test sẽ là tổ hợp của đống này, tức là dùng phép *. Ví dụ:
- IF (IF ELSE END) END ==> 1 + (1 + 1)
- IF (IF ELSE END) (IF END) END ==> (1+1) * (1+1)
- IF (IF ELSE (IF END) (IF ELSE END)) (IF END) (IF ELSE END) END => (1 + (2*2)) * 2 * 2

Dùng Stack. Với IF với ELSE đẩy vào stack các giá trị đặc biệt đánh dấu nhãn này, đồng thời đẩy giá trị 1 (dùng cho tổ hợp). Gặp END_IF thì ta xử lý.

Độ phức tạp: O(N) với N là số dòng từ input.

Submission

NKTEST.cpp

Tutorial SPOJ