Thuat toan

Xử lý biểuthức số học
Lê Văn Chương
Trường THPT chuyên Phan Bội Châu - Nghệ An
Biểuthức số học được định nghĩa rất đơn giản và ngắn gọn như sau: Biểu thức số họclà một chuỗi ký tự bao gồm:
-Một số nguyên không dấu hoặc có dấu, hoặc một tên biến đặt theo chuẩn củaPascal.
-Hai biểu thức số học nối với nhau bởi một dấu phép tính (+, -, *, hoặc /). Cóthể đặt trong cặp dấu ngoặc đơn
Khi cho một biểu thứcthì thông thường ta phải kiểm tra xem biểu thức đã cho có là một biểu thức đúngkhông. Để kiểm tra một biểu thức xem nó có đúng không ta cần kiểm tra xem cácsố của nó có đúng không?, các biến trong đó có được đặt tên theo chuẩn củapascal không? các phép tính có hợp logic toán học không? các dấu ngoặc đơn cóđúng không?
Trong các điều kiệntrên thì kiểm tra số, tên biến, các dấu chúng ta không để cập đến vì chúng quádễ, một người mới bặt đầu học cũng có thể xử lý được. Chúng ta chỉ quan tâm đếnxử lý các dấu phép tính và ngoặc đơn, đặc biệt là dấu ngoắc đơn bởi vì nó phứctạp và khó xử lý nhất.
Bây giờ, chúng ta sẽxem xét một bài toán được gọi là đơn giản nhất trong xử lý biểu thức số học.Nội dung của bài toán như sau:
Bài toán 1: Lập trình chươngtrình nhập vào một xâu ký tự chỉ gồm các dấu mở ngoặc và đóng ngoặc đơn, sau đókiển tra tính đúng đăn của cách đặt dấu ngoặc. Một xâu ký tự đúng là xâu thỏamãn:
- Số lần mở ngoặc đúng bằng số lần đóng ngoặc.
- Dấu mở ngoặc phải đứng trước (ở phía bên trái)dấu đóng ngoặc tương ứng.
Bài toán xử lý khôngkhó nhưng nó là nền tảng để chúng ta áp dụng vào các bài toán có mức độ caohơn. Với bài này ta chỉ cần đọc dòng dữ liệu và tính số lần mở ngoặc có bằng sốlần đóng ngoặc không? nếu không thì đó là biểu thức sai, nếu có thì kiểm tratiếp dấu mở ngoặc có đứng trước dấu đóng ngoặc tương ứng không. Sau đây là đoạnchương trình chính.
For i:=1 to length(s)do
Begin
If s[i] in [ ( , ) ] then
Begin
If s[i]= ( then inc(mn)else dec(mn);
If mn<0 then beginwriteln( bieu thuc sai );halt;end;
End;
If mn<>0 thenbegin Writeln( Bieu thuc sai );Halt;End;
Writeln( Bieu thucdung );
End;
Chúngta có thể nâng cấp chúng trình trên để kiểm tra một biểu thức đẩy đủ nhập vàocó đúng không, đây chính là nội dung của bài toán 2.
Bài toán 2: Cho một xâu ký tựhãy kiểm tra xem xâu ký tự đó có là một biểu thức số học đúng hay không, biểuthức được xem là đúng nếu nó thỏa mãn các điều kiện sau:
- Một số nguyên, hoặc một tên biến đặt theochuẩn của pascal.
- Hai biểu thức số học nối với nhau bởi một dấuphép tính (+, -, *, hoặc /), có thể đặt trong một cặp dấu ngoặc đơn.
Với bài toán này, chúng ta không chỉkiểm tra dấu ngoặc đơn như bài trước mà còn kiểm tra tính đúng đắn của các phéptính, các số, các biến, kiểm tra các dấu phép tính có phù hợp không?
Thuật toán: Sử dụng biến dem đểkiểm tra các dấu ngoặc đơn có đúng không và biến dau để kiểm tra tính đúng đắncủa dấu. Cách kiểm tra như sau:
Khởi tạo dem:=0 và dau:=1;
Gọi i là ký tự đang xét của xâu s:
- Nếu i là dấu `(` và biến dau có giá trị bằng 0thì đặt biến tăng biến dem lên 1;
- Nếu i là dấu `)` và trước i là một dấu phéptính thì chắc chắn đây là một biểu thức sai, ngược lại giảm biến dem đi 1 đểbáo cho chương trình biết đã có 1 cặp dấu mở ngoặc đúng; nếu dem<0 thi` s la`mo^.t bie^?u thu+`c sai bo+?i vi` so^` ky` tu+. ddo`ng ngoa(.c nhie^`u ho+n mo+? ngoa(.c.
- Nếu i là một dấu phép tính(+, -, *, /) vàdau=1, có nghĩa là có 2 dấu liên tiếp nhau => đây là biểu thức sai, ngượclại, nếu i là một dấu phép tính và trước đó chưa có dấu nào (dau = 0) thì đặtdau:=1 để báo là đang xử lý biểu thức có dấu;
- Nếu i là các chữ cái A.. Z và a.. z thìđây chính là bắt đầu của 1 tên biến, ta phải xét i ở vị trí cuối cùng của tênbiến này rồi xử lý tiếp:
- Nếu dau=0: S là biểuthức sai, bởi vì: ta khởi tao dau=1 nên với