Ứng dụng mô hình cây để tính giá trị biểu thức

Ứng dụng mô hình cây để tính giá trị của biểu thức Cây là đồ thị vô hướng liên thông không có chu trình. Mô hình cây có rất nhiều ứng dụng trong nhiều lĩnh vực khác nhau, đặc biệt là trong tin học, cây được sử dụng để xây dựng các thuật toán tổ chức các thư mục, các thuật toán tìm kiếm, sắp xếp, nén và giải nén dữ liệu. Hàng ngày chúng ta vẫn sử dụng những chiếc máy tính để tính giá trị các biểu thức phức tạp. Vậy làm thế nào mà máy tính có thể tính được những biểu thức như vậy? Để trả lời cho câu hỏi trên, bài viết này tôi xin trình bày cách sử dụng mô hình cây để tính giá trị biểu thức. I. Kiến thức cơ bản về cây 1. Định nghĩa: Cây là đồ thị vô hướng liên thông và không có chu trình. Cây sẽ gồm một tập hợp hữu hạn các nút (đỉnh) và các cạnh nối các nút. Trong cây người ta thường quy định một nút đặc biệt gọi là gốc. Giữa các nút ở trên cây có mối quan hệ phân cấp cha con. 2. Các phương pháp duyệt cây: Phép xử lý các nút trên cây mà ta gọi là phép thăm các nút một cách hệ thống sao cho mỗi nút được thăm đúng một lần gọi là phép duyệt cây. Có 3 phương pháp duyệt cây là: duyệt cây theo thứ tự trước, duyệt cây theo thứ tự giữa, duyệt cây theo thứ tự sau. Giả sử cho một cây T có gốc là R và các cây con của gốc theo thứ tự là T1, T2, T3,, Tm. Ta sẽ định nghĩa một cách đệ quy ba phép duyệt cây như sau: Duyệt cây theo thứ tự trước: Bước 1: Thăm gốc của cây T; Bước 2: Lần lượt duyệt các cây con T1, T2,, Tm theo thứ tự trước. Duyệt cây theo thứ tự giữa: Bước 1: Duyệt cây con thứ nhất T1 theo thứ tự giữa; Bước 2: Thăm gốc của cây T; Bước 3: Duyệt các cây con còn lại T2,, Tm theo thứ tự giữa. Duyệt cây theo thứ tự sau: Bước 1: Lần lượt duyệt các cây con T1, T2,, Tm theo thứ tự sau; Bước 2: Thăm gốc của cây T. Ví dụ: Ta nhận được dạng hậu tố (kí pháp Ba Lan ngược) của một biểu thức khi ta duyệt cây nhị phân biểu diễn biểu thức đó theo thứ tự sau. Chẳng hạn biểu thức: ((x+y)^2)+((x-4)/3) có dạng hậu tố là: x y + 2 ^ x 4 - 3 / + II. Dùng kí pháp Ba Lan ngược để tính giá trị biểu thức: Trước hết chúng ta xét một ví dụ cụ thể: Cho biểu thức: 5+(6-3)*2-1 Dạng hậu tố là: 5 6 3 - 2 * 1 - + Tính toán: 5 3 2 * 1- + 5 6 1 - + 5 5 + 10 Vậy bài toán đặt ra chỉ còn là: Chuyển biểu thức dạng bình thường sang dạng hậu tố (kí pháp Ba Lan ngược). Thuật toán đổi biểu thức bình thường sang kí pháp Ba Lan ngược: Ta dùng một mảng là stack: để lưu các phép toán, các dấu ngoặc trong quá trình xử lí. Và dùng một mảng BaLan để lưu kết quả chuyển đổi. Đọc xâu biểu thức đã cho theo thứ tự từ trái qua phải: - Nếu gặp toán hạng thì đưa vào Balan - Nếu gặp dấu mở ngoặc thì đưa vào stack. - Nếu gặp toán tử thì: ta phải xét các toán tử trên cùng của stack: nếu các toán tử này có mức ưu tiên lớn hơn mức ưu tiên của toán tử đang xét thì lần lượt lấy các toán tử này ra khỏi stack và đưa vào Balan, làm như vậy cho tới khi gặp toán tử có mức ưu tiên nhỏ hơn hoặc bằng mức ưu tiên của toán tử đang xét thì dừng và nạp toán tử đang xét này vào stack. - Nếu gặp dấu đóng ngoặc thì: Lần lượt lấy các phần tử của stack ra đưa sang Balan cho tới khi gặp dấu ngoặc mở thì dừng lại, và xóa luôn dấu ngoặc mở khỏi stack. Sau đây là chương trình minh họa tính giá trị biểu thức: Uses crt; Const MAX=100; So=['0'..'9']; mang:array['0'..'9'] of shortint=(0,1,2,3,4,5,6,7,8,9); Var Balan:array[1..MAX] of longint; stack:array[0..MAX] of char; pheptoan:array[1..MAX] of boolean; a:array[1..MAX] of real; i,tbt,tpt,p,q:longint; kq:real; s :string; ch:char; Procedure khoitao; Begin writeln('Nhap vao 1 bieu thuc:'); readln(s); s:=concat('(',s,')'); stack[0]:=')'; End; Function uutien(ch:char):integer; Begin Case ch of '(' : uutien:=-1; ')' : uutien:=0; '+' : uutien:=1; '-' : uutien:=2; '*' : uutien:=3; '/' : uutien:=4; end; End; Procedure Run; var ch1: char; Begin while uutien(stack[tpt])>=uutien(ch) do begin ch1:=stack[tpt]; dec(tpt); inc(tbt); Balan[tbt]:=uutien(ch1); pheptoan[tbt]:=true; end; End; Procedure xuli_chuso; begin q:=0; while (s[1] in so) and (s'') do begin q:=q*10+mang[s[1]]; delete(s,1,1); end; inc(tbt); Balan[tbt]:=q; End; Procedure add; Begin inc(tpt); stack[tpt]:=ch; End; Procedure KiphapBalan; Begin tpt:=0; tbt:=0; p:=0; while s'' do begin ch:=s[1]; case ch of '(': begin add; delete(s,1,1); end; ')' : begin Run; dec(tpt); delete(s,1,1); end; '+','-','*','/' : begin Run; add; delete(s,1,1); end; '0'..'9' : xuli_chuso; end; end; End; Function Pop:real; Begin pop:=a[p]; dec(p); end; Procedure Push(x:real); Begin inc(p); a[p]:=x; End; Procedure tinh; Begin for i:=1 to tbt do if pheptoan[i] then case balan[i] of 1 : push(pop+pop); 2 : push(-pop+pop); 3 : push(pop*pop); 4 : push(1/pop*pop); end else push(Balan[i]); kq:=pop; End; Procedure xuli; Begin KiphapBalan; tinh; writeln(kq:15:2); End; BEGIN clrscr; khoitao; xuli; readln END.