TỔ CHỨC DỮ LIỆU Bài . Cụm Một cụm trong một biểu thức toán học là đoạn nằm giữa hai dấu đóng và mở ngoặc đơn (). Với mỗi biểu thức cho trước hãy tách các cụm của biểu thức đó. Dữ liệu vào: Tệp văn bản chứa một dòng kiểu xâu kí tự (string) là biểu thức cần xử lí. | Sáng tạo trong Thuật toán và Lập trình Tập I 89 CHƯƠNG 4 TỔ CHỨC DỮ LIỆU Bài . Cụm Một cụm trong một biểu thức toán học là đoạn nằm giữa hai dấu đóng và mở ngoặc đơn . Với mồi biểu thức cho trước hãy tách các cụm của biểu thức đó. Dữ liệu vào Tệp văn bản CUM. INP chứa một dòng kiểu xâu kí tự string là biểu thức cần xử lí. Dữ liệu ra Tệp văn bản CUM .OUT dòng đầu tiên ghi d là số lượng cụm. Tiếp đên là d dòng mồi dòng ghi một cụm được tách từ biểu thức. Trường hợp gặp lồi cú pháp ghi số - 1. Thí dụ x a 1 b-2 c 3 4 a 1 b-2 c 3 b-2 c 3 Gợi ý Giả sử xâu 5 chứa biểu thức cần xử lí. Ta duyệt lần lượt từ đầu đến cuối xâu s với mỗi kí tự s z ta xét hai trường hợp Trường hợp thứ nhất s i là dấu mở ngoặc ta ghi nhận i là vị trí xuất hiện đầu cụm vào một ngăn xếp stack st inc p st p i trong đó p là con trỏ ngăn xếp. p luôn luôn trỏ đến ngọn tức là phần tử cuối cùng của ngăn xếp. Thủ tục này gọi là nạp vào ngăn xếp NapST. Sáng tạo trong Thuật toán và Lập trình Tập I 90 Trường hợp thứ hai s i là dấu đóng ngoặc ta lấy phần tử ngọn ra khỏi ngăn xếp kết hợp với vị trí i để ghi nhận các vị trí đầu và cuối cụm trong s. Hàm này gọi là lấy phần tử ra khỏi ngăn xếp LayST. Khi lấy một phần tử ra khỏi ngăn xếp ta giảm con trỏ ngăn xếp 1 đơn vị. j st p dec p Có hai trường hợp gây ra lỗi cú pháp đơn giản như sau 1. Gặp mà trước đó chưa gặp Lỗi chưa mở đã đóng . Lỗi này được phát hiện khi xảy ra tình huống s i và stack rỗng p 0 . 2. Đã gặp mà sau đó không gặp Lỗi mở rồi mà không đóng . Lỗi này được phát hiện khi xảy ra tình huống đã duyệt hết biểu thức s nhưng trong stack vẫn còn phần tử p 0 . Lưu ý rằng stack là nơi ghi nhận các dấu mở ngoặc . Ta dùng biến SoCum để đếm và ghi nhận các cụm xuất hiện trong quá trình duyệt biểu thức. Trường hợp gặp lỗi ta đặt SoCum -1. Hai mảng dau và cuoi ghi nhận vị trí xuất hiện của kí tự đầu cụm và kí tự cuối cụm. Khi tổng hợp kết quả ta sẽ dùng đến thông tin của hai mảng này. ----------------------------- Xử lý biểu thức trong s .
