Sắp đoạn

Sắp đoạn

               Trong một tệp văn bản chứa những đoạn cắt ra từ một trục số. Mỗi đoạn có dạng <d, c> trong đó "<" có thể là một trong hai kí tự ( hoặc [, > có thể là một trong hai kí tự ) hoặc], d và c là các biểu thức dạng x hoặc x + y hoặc x*y với x và y là những số tự nhiên. Ta luôn có d £ c. Chiều dài của đoạn <d, c> là hiệu c - d. Hãy sắp xếp các đoạn tăng theo chiều dài và ghi chúng vào một tệp văn bản theo đúng dạng thức đọc được của mỗi đoạn. Có thể thêm, bớt một số dấu cách trong và ngoài các đoạn. Trên mỗi dòng của tệp luôn luôn chứa trọn một số đoạn.

Thí dụ cho dữ liệu vào trong file input “Doan.inp” là:

[2+1,7) (4,4*3) (5,6]

Sau khi sắp ta được kết quả sau trong file output “Doan.out”:

(5,6] [2+1,7) (4,4*3)

Thuật toán

Ta mô tả cấu trúc của mỗi đoạn như sau:

mo  so1[toan1  so2] , so3[toan2  so4]

trong đó:

s         mo là một trong hai dấu mở ngoặc: ( hoặc [.

s         so1, so2, so3 và so4 là các số tự nhiên xuất hiện trong thành phần của đoạn.

s         toan1 và toan2 là dấu các phép toán (+, *), nếu có trong thành phần của đoạn.

s         dong là một trong hai dấu đóng ngoặc: ) hoặc].

Trong mô tả trên, chúng ta sử dụng kí pháp [*] để chỉ ra thành phần * có thể bỏ qua.

Nếu thành phần thứ i (i = 1..2) của đoạn không có dấu phép toán, thì cũng không có toán hạng thứ hai, tức là thành phần đó có dạng là một số tự nhiên thì ta đặt toan[i] = BL (dấu cách).

       Nếu số thứ i không xuất hiện trong đoạn, ta đặt so[i] = 0.

Thí dụ:

Đoạn	mo	so1	Toan1	so2	so3	Toan2	so4	dong
[2+10,7*6)	[	2	+	10	7	*	6	)
[2+10,7)	[	2	+	10	7	BL	0	)
(2,7+5]	(	2	BL	0	7	+	5	]

Ngoài ra ta thêm một thành phần len để xác định chiều dài của đoạn. len của mỗi đoạn được tính theo công thức sau

len = TriCuoi-TriDau

TriCuoi = so3 Toan2 so4, nếu Toan2 là dấu '+' hoặc '*' và

TriCuoi = so3, nếu Toan2 = BL.

Tương tự,

TriDau = so1 Toan1 so2, nếu Toan1 là dấu '+' hoặc '*' và

TriDau = so1, nếu Toan1 = BL.

Ta sử dụng cấu trúc bản ghi để biểu diễn dữ liệu cho mỗi đoạn:

type

MangSo = array[1..4] of integer; {4 toan hang}

MangToan = array[1..2] of char; {2 toan tu +,*}

KieuDoan = record

              mo: char;

              dong: char;

              so: MangSo;

              Toan: MangToan;

              len: integer;

            end;

Các đoạn đọc được sẽ được ghi dần vào mảng a với biến đếm số phần tử n:

type MangDoan = array[0..1000] of KieuDoan;

var a: MangDoan; n: integer;

Khi đó thủ tục tính chiều dài len của mỗi đoạn sẽ được cài đặt như sau:

procedure LenSeg(i: integer);

var dau, cuoi: integer;

begin

  with a[i] do

   begin

    dau := so[1];

    if Toan[1]='+' then dau := dau+so[2]

    else if Toan[1]='*' then dau:=dau*so[2];

          cuoi:=so[3];

    if Toan[2]='+' then cuoi:=cuoi+so[2]

    else if Toan[2]='*' then cuoi:=cuoi*so[2];

   end;

   len := cuoi-dau;

end;

Cấu trúc  with x do T cho phép ta thực hiện thao tác T trên các thành phần của bản ghi x  mà không phải viết lại phần tiếp đầu x.

Để đọc các đoạn từ tệp ta sử dụng một máy trạng thái như sau. Hãy tưởng tượng mắt bạn bị bịt kín, do đó bạn phải dùng tay để nhận biết từng kí tự trong tệp văn bản. Mỗi lần bạn sờ một kí tự c nào đó rồi dựa vào kí tự đó bạn xác định các thủ tục cần thực hiện để nhận biết từng đối tượng. Muốn vậy ta sử dụng một biến gọi là biến trạng thái q với mục đích ghi nhận các tình huống đã gặp và trên cơ sở đó xác định các thao tác cần thiết. Gọi q là biến trạng thái. Trong quá trình đọc và xử lí tệp input ta có thể gặp năm trạng thái như sau:

q = 0: Trạng thái dò tìm đầu đoạn: Nếu gặp kí tự mở đầu một đoạn, cụ thể là nếu gặp kí tự c = '(' hoặc c = '[' thì cần tạo một đoạn mới như sau:

-                   Tăng chỉ dẫn ghi nhận đoạn mới: n := n + 1;

-                   Ghi nhận kí tự mở đầu đoạn: a[n].mo:= c;

-                   Khởi trị mảng số: a[n].so := (0, 0, 0, 0);

-                   Khởi trị mảng dấu các phép toán: a[n].Toan:= (BL, BL);

-                   Chuyển qua trạng thái q := 1 là trạng thái tìm đọc so[1].

0: if c in['(','['] then

         begin

n:=n+1; a[n].mo:=c;

a[n].so:=KhoiTriSo;

a[n].Toan:=KhoiTriToan;

q:= 1;

         end;

Các biến KhoiTriSo và KhoiTriToan được khai báo và gán trị khởi đầu như sau:

const

         KhoiTriSo: MangSo = (0,0,0,0);

         KhoiTriToan: MangToan = (BL,BL);

q = 1: Trạng thái tìm đọc số thứ nhất, so[1]: Ở trạng thái này, nếu gặp chữ số thì ta ghép thêm chữ số đó vào so[1], nếu gặp dấu phép toán thì ta hiểu là thành phần thứ nhất của đoạn là một biểu thức dạng:

so[1] Toan[1] so[2]

Ta ghi nhận dấu phép toán vào trường Toan[1] và chuyển qua trạng thái q = 2 để đọc số thứ hai. Nếu gặp dấu phẩy (,) là dấu ngăn giữa hai thành phần của đoạn ta chuyển qua trạng thái q = 3 để đọc số đầu tiên của thành phần thứ hai, tức là đọc so[3].

1: if c in ChuSo then DocSo(n,1)

else if c in PhepToan then

begin a[n].Toan[1]:=c; q:=2; end

else if c=',' then q:=3;

Thủ tục DocSo(i,j) nhận thêm 1 chữ số để ghép vào biến a[i].so[j].

q = 2: Đọc số thứ hai, so[2]: Ở trạng thái này, nếu gặp chữ số thì ta ghép thêm chữ số đó vào so[2], nếu gặp dấu phẩy là dấu ngăn giữa hai thành phần của đoạn ta chuyển qua trạng thái q = 3 để đọc số đầu tiên của thành phần thứ hai, tức là đọc so[3].

       2: if c in ChuSo then DocSo(n,2)

else if c =',' then q:=3;

q = 3: Đọc số thứ ba, so[3]: Ở trạng thái này, nếu gặp chữ số thì ta ghép thêm chữ số đó vào so[3], nếu gặp dấu phép toán thì ta hiểu là thành phần thứ hai của đoạn là một biểu thức dạng:

so[3] Toan[2] so[4]

Ta ghi nhận dấu phép toán vào trường Toan[2] và chuyển qua trạng thái q = 4 để đọc số thứ tư, so[4], nếu gặp kí tự c = ')' hoặc c = ']' thì ta hiểu là đã kết thúc một đoạn, ta gọi thủ tục KetDoan để thực hiện các thao tác sau:

-     Ghi nhận kí tự đóng đoạn: a[n].dong:= c.

-     Tính chiều dài của đoạn: LenSeg(n);

-     Chuyển qua trạng thái q = 0 để tiếp tục với đoạn tiếp theo, nếu còn.

procedure KetDoan;

begin

a[n].dong:=c; LenSeg(n); q:=0;

end;

Đoạn chương trình thể hiện trạng thái q = 3 khi đó sẽ như sau:

3: if c in ChuSo then DocSo(n,3)

   else if c in PhepToan then

    begin a[n].Toan[2]:=c; q:=4 end

   else if c in[')',']'] then KetDoan;

q = 4: Đọc số thứ tư, so[4]: Ở trạng thái này, nếu gặp chữ số thì ta ghép thêm chữ số đó vào so[4], nếu gặp kí tự c = ')' hoặc c = ']' thì ta hiểu là đã kết thúc một đoạn, ta gọi thủ tục KetDoan.

4: if c in ChuSo then DocSo(n,4)

   else if c in[')',']'] then KetDoan;

Đọc tệp xong ta dùng thủ tục qsort sắp các đoạn tăng dần theo chiều dài. Sau khi sắp ta ghi các đoạn vào tệp gn theo các trường.

(*  Pascal  *)

{$B-}

program Segments;

uses crt;

const

      fn = 'DOAN.INP'; {Tep input}

      gn = 'DOAN.OUT';{Tep output}

      MN = 1000; {So luong toi da cac doan}

      BL = #32;{Dau cach}

      ChuSo = ['0'..'9'];

      PhepToan = ['+','*'];

type

      MangSo = array[1..4] of integer;

      MangToan = array[1..2] of char;

      KieuDoan = record

                        mo: char; {dau mo ngoac}

                        dong: char; {dau dong ngoac}

                        so: MangSo; {4 so trong doan}

                        Toan: MangToan; {2 phep toan}

                        len: integer; {chieu dai doan}

                  end;

      MangDoan = array[0..MN] of KieuDoan;

const

      KhoiTriSo: MangSo = (0,0,0,0);

      KhoiTriToan: MangToan = (BL,BL);

var

      f,g:text;

      a: MangDoan;

      c: char;{ky tu dang xet}

      n: integer;{chi so doan dang xet}

      q: integer;{bien trang thai}

(*---------------------------------

Cac trang thai q = 0: do tim dau doan

1: doc so[1]

2: doc so[2]

3: doc so[3]

4: doc so[4]

-----------------------------------*)

procedure LenSeg(i: integer); tự viết

procedure KetDoan; tự viết

(*-----------------------------------------

   Them 1 chu so vao so thu j cua doan i

------------------------------------------*)

procedure DocSo(i,j: integer);

begin

       a[i].so[j]:=a[i].so[j]*10+(ord(c)-ord('0'))

end;

(*--------------------------------------

            Doc cac doan

---------------------------------------*)

procedure doc;

begin

      assign(f,fn); reset(f);

      q:=0; n:=0;

      while not eof(f) do

      begin

         read(f,c);

         case q of

         0: if c in['(','['] then                                 begin

              n:=n+1; a[n].mo:=c;

              a[n].so:=KhoiTriSo;

              a[n].Toan:=KhoiTriToan;

              q:=1;

            end;

         1: if c in ChuSo then DocSo(n,1)

            else if c in PhepToan then

            begin a[n].Toan[1]:=c; q:=2 end

            else if c=',' then q:=3;

         2: if c in ChuSo then DocSo(n,2)

            else if c =',' then q:=3;

         3: if c in ChuSo then DocSo(n,3)

            else if c in PhepToan then

                 begin

                   a[n].Toan[2]:=c; q:=4;

                 end

            else if c in[')',']'] then KetDoan;

         4: if c in ChuSo then DocSo(n,4)

             else if c in [')',']'] then KetDoan;

         end; { case }

      end; { while }

      close(f);

    end;

procedure qsort(d,c:integer);

var   i,j,m: integer;

      x: KieuDoan;

begin

i:=d; j:=c; m:=a[(i+j) div 2].len;

while i<=j do

begin

while a[i].len < m do i:=i+1;

while a[j].len > m do j:=j-1;

if i<=j then

begin

x:=a[i]; a[i]:=a[j]; a[j]:= x;

i:=i+1; j:=j-1;

end;

end;

if d < j then qsort(d,j);

if i < c then qsort(i,c);

end;

procedure Ghi;

var i: integer;

begin

assign(g,gn); rewrite(g);

for i:=1 to n do

with a[i] do

begin

           if Toan[1]<>BL then

              write(g,mo, so[1],Toan[1],so[2])

           else write(g,mo, so[1]);

           if Toan[2]<>BL then

       write(g,',',so[3],Toan[2],so[4],dong,BL)

     else write(g,',',so[3],dong,BL);

   { moi dong viet 10 doan }

if i mod 10 = 0 then writeln(g);

end;

close(g);

end;

BEGIN

Doc; qsort(1,n); Ghi;

END.