Thứ Hai, 13 tháng 1, 2014

Cụm



Bài 4.1. 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ụ:
CUM.INP
CUM.OUT

x*(a+1)*((b-2)/(c+3))

4
(a+1)
(b-2)
(c+3)
((b-2)/(c+3))
Gợi ý
Giả sử xâu s 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[i] ta xét hai trường hợp:
s         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         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 daucuoi 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
---------------------------*)
procedure BieuThuc;
var i: byte;
begin
KhoiTriSt; {Khởi trị cho stack}
SoCum := 0; {Khởi trị con đếm cụm}
   for i := 1 to length(s) do
      case s[i] of
'(': NapSt(i);
')': if StackRong then
      begin SoCum:= -1;  exit; end
else
begin
    inc(SoCum);
    dau[SoCum] := LaySt;
    cuoi[SoCum] := i;
end;
end {case};
if p > 0 then
 begin SoCum := -1; exit; end;
end;
Sau khi duyệt xong xâu s ta ghi kết quả vào tệp output g. Hàm copy(s,i,d) cho xâu gồm d kí tự được cắt từ xâu s kể từ kí tự thứ i trong s. Thí dụ copy('12345678',4,3) = '456'.
(*  Pascal  *)
program Cum;
{$B-}
uses crt;
const
fn = 'CUM.INP'; gn = 'CUM.OUT';
type mb1 = array[1..255] of byte;
var s: string; {chua bieu thuc can xu li}
   st: mb1; {stack}
  {stack luu vi tri xuat hien dau ( trong xau s}
   p: integer; {con tro stack}
   dau,cuoi: mb1; {vi tri dau, cuoi cua 1 cum}
   SoCum: integer;
   f,g: text;
(*--------------------------
      Khoi tri stack st
---------------------------*)
procedure KhoiTriSt;
begin p := 0; end;
(*--------------------------
  Nap tri i vao stack st
---------------------------*)
procedure NapSt(i: byte);
begin inc(p); st[p] := i; end;
(*--------------------------------
   Lay ra 1 tri tu ngon stack st
---------------------------------*)
function LaySt: byte;
begin LaySt := st[p]; dec(p); end;
(*--------------------------
   Kiem tra Stack St rong ?
---------------------------*)
function StackRong: Boolean;
begin StackRong := (p=0); end;
(*--------------------------
  Xu ly bieu thuc trong s
---------------------------*)
procedure BieuThuc; tự viết
(*---------------------------------
Doc du lieu tu tep input vao xau s
----------------------------------*)
procedure Doc;
begin
s := ''; {gan tri  rong cho s}
assign(f,fn); reset(f);
if not seekeof(f) then readln(f,s);
close(f);
end;
(*--------------------------
Ghi ket qua vao tep output
---------------------------*)
procedure Ghi;
var i: byte;
begin
assign(g,gn); rewrite(g); writeln(g,SoCum);
for i := 1 to SoCum do
writeln(g,copy(s,dau[i],cuoi[i]-dau[i]+1));
close(g);
end;
BEGIN
Doc; BieuThuc; Ghi;
END.

Không có nhận xét nào:

Đăng nhận xét