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 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
---------------------------*)
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