Cây biểu thức số học
Nguyễn Tuấn Dũng
Chúng ta đã có bài ″Xử lý biểu thức số học″ của bạn Lê Văn Chương trong THNT số 29
(tháng 2/2002). Tác giả trình bày phương pháp tính biểu thức số học theo cách đưa về dạng
ký pháp nghịch đảo Balan và sử dụng cấu trúc dữ liệu kiểu stack (ngăn xếp). Trong bài viết
này, tôi muốn bàn về một phương pháp khác khá thuận tiện cho việc biểu diễn và tính toán
biểu thức số học, đó là cây biểu thức số học. Để đơn giản và nhằm mục đích làm nổi bật
những đặc trưng của phương pháp này, chúng ta giói hạn xâu biểu thức nhập vào chỉ ở
mức độ sau:
- Các số hạng chỉ là một kí tự (′0′..′9′) hoặc ′A′..′z′).
Các phép toán bao gồm 4 phép toán hai ngôi : +,-,*,/.
Ngoài ra, các dấu ngoặc có thể có hoặc không và giả sử biểu thức nhập vào đã đúng quy
cách (bạn có thể xem lại thủ tục kiểm tra biểu thức nhập vào đã đúng quy cách hay chưa
trên THNT số 29).
Biểu diễn cây nhị phân bằng cấu trúc dữ liệu kiểu con trỏ
Xuất phát từ đặc điểm các phép toán của chúng ta chỉ là các phép toán hai ngôi nên cách
mô tả phù hợp và tiện lợi nhất cho biểu thức số học chính là một cây nhị phân đầy đủ (số
nút trên các mức đều là tối đa).
Trong đó, các phép toán +,-,*,/ sẽ nằm tại các gốc (có cây con), còn các số hạng thì nằm
trên lá (các nút tận cùng của cây, không có cây con). Bên trái của mỗi gốc là cây con trái
biểu diễn cho biểu thức bên trái phép toán nằm tại gốc đó và tương tự như thế, bên phải là
cây con phải biểu diễn cho biểu thức bên phải của phép toán. Phép toán được thực hiện
cuối cùng trong biểu thức sẽ nằm tại gốc chính của cây. Có thể lấy ví dụ về hình ảnh một
cây biểu thức như hình vẽ bên.
Để biểu diễn một cây nhị phân, ta dùng kiểu dữ liệu con trỏ. Định nghĩa như sau:
Type ptr=^node;
Node=record
Info: char;
l,r: ptr;
End;
Var T:ptr;

Trong đó T^.info chứa thông tin tại gốc cây, T^.l chứa địa chỉ trỏ tới cây con trái của T,
T^.r chứa địa chỉ trỏ tới cây con phải của T. Và tiếp tục T^.l^.info sẽ chứa thông tin tại gốc
cây con trái, T^.l^.l chứa địa chỉ trỏ tới cây con trái của cây con trái của T, T^.l^.r chứa địa
chỉ trỏ tới cây con phải của cây con trái của T..
Thuật toán chuyển biểu thức trung tố thành một cây biểu thức
Tiếp theo, giả sử biểu thức ban đầu được nhập vào dưới dạng một xâu kí tự (giống như ví
dụ: s=′(a-b)*(c-d)′ ). Dùng mảng A một chiều, mỗi phần tử của mảng là một bản ghi gồm
hai trường : info và ut , ta sẽ có thuật toán chuyển biểu thức dạng trung tố này thành một
cây biểu thức như sau :
1. Khởi tạo:
-Thiết lập độ ưu tiên cho các phép toán: utcongtru:=1;
utnhanchia:=2;
- Dùng một biến uutien để lưu mức độ ưu tiên hiện thời (ban đầu khởi tạo bằng 0).
2. Duyệt biểu thức trung tố từ trái qua phải:
- Gặp ′(′ thì inc(uutien,2), gặp ′)′ thì dec(uutien,2). Chú ý: không đưa dấu ngoặc vào mảng
A.
- Gặp số hạng thì đưa vào A như sau: A[i].info:=số hạng;
A[i].ut:=10000;
{có thể gán bằng một hằng tuỳ ý nhưng phải tương đối lớn, như maxint chẳng hạn (điều
này sẽ được sử dụng trong bước 3)}.
- Gặp phép toán +,- [hoặc *,/] thì đưa vào A như sau:
A[i].info:=phép toán;
A[i].ut:= utcongtru[hay utnhanchia] + uutien.
Ví dụ, biểu thức ban đầu là: (a+b*(c-d) thì ta được mảng A như sau :
3. Đệ quy:
- Trong mảng A, tìm bản ghi phải nhất và có độ ưu tiên bé nhất lấy làm gốc cây. Toàn bộ
phần mảng A bên trái bản ghi này sẽ tương ứng với biểu thức bên trái và là cây con trái.
Còn phần mảng A bên phải bản ghi này tương ứng với biểu thức bên phải và là cây con
phải.
- Hai cây con này tính chất và đặc điểm cũng giống như cây ban đầu. Vì thế ta lại tiếp tục

tìm bản ghi phải nhất và có độ ưu tiên bé nhất của 2 biểu thức bên trái và bên phải này để
làm gốc của các cây con trái và cây con phải tương ứng ở mức thấp hơn. (xem thêm
chương trình ở dưới)
- Quá trình đệ quy sẽ được dừng khi biểu thức của chúng ta chỉ gồm một phần tử của mảng
A, đó chính là các số hạng ứng với các nút lá của cây biểu thức.
Để minh hoạ cho bước 3, ta sẽ thực hiện với ví dụ trên (hình vẽ có trong file attachment):
+ Từ phần tử đầu đến phần tử cuối của mảng A, tìm bản ghi phải nhất và có độ ưu tiên bé
nhất: A[4] => cây hiện thời (hình 1):
+Từ A[1] đến A[3], bản ghi phải nhất và có độ ưu tiên bé nhất: A[2] => cây hiện thời (hình
2):
+ Từ A[1] đến A[1], bản ghi cần tìm: A[1] => cây hiện thời (hình 3).
+ Từ A[3] đến A[3], bản ghi cần tìm: A[3] => cây hiện thời (hình 4).
+ Từ A[5] đến A[7] bản ghi phải nhất và có độ ưu tiên bé nhất: A[6] => cây hiện thời (hình
5):
+Từ A[6] đến A[6], bản ghi cần tìm: A[6] => cây hiện thời (hình 6).
+Từ A[7] đến A[7], bản ghi cần tìm: A[7] => cây hiện thời (hình7).
4. Thủ tục đệ quy tính giá trị cây biểu thức
Một cách trực quan mà nói thì ta có thể thấy ngay việc sử dụng giải thuật đệ quy để tính
giá trị cây biểu thức là đơn giản và thích hợp nhất. Khi duyệt đến từng nút của cây, nếu là
một trong bốn phép toán +,-,*,/ thì giá trị của cây sẽ được tính bằng giá trị của cây con trái
cộng, trừ, nhân, hoặc chia tương ứng cho giá trị cây con phải (giá trị của hai cây con này
lại được tính tiếp nhờ lệnh gọi đệ quy). Còn nếu nút đó là một số hạng thì giá trị của cây
được gán bằng giá trị số hạng đó và dừng lại, không gọi đệ quy nữa (xem Procedure
DuyetTruoc;). Duyệt cây theo kiểu này được gọi là duyệt cây theo thứ tự trước (thăm gốc,
rồi lần lượt duyệt cây con trái và cây con phải theo thứ tự trước) và ta sẽ được biểu thức
tiền tố. Còn nếu duyệt theo thứ tự giữa (duyệt cây con trái theo thứ tự giữa, thăm gốc, rồi
duyệt cây con phải theo thứ tự giữa) hay duyệt theo thứ tự sau (duyệt cây con trái theo thứ
tự sau, duyệt cây con phải theo thứ tự sau rồi mới thăm gốc) ta sẽ được tương ứng biểu
thức trung tố và biểu thức hậu tố (hay kiểu kí pháp nghịch đảo Ba Lan). Do đó, tương tự
như vậy có thể thay thủ tục DuyetTruoc; bằng 2 thủ tục Duyetgiua; và Duyetsau; (ở cuối

chương trình ).
Dưới đây là chương trình tính biểu thức theo thuật toán trên. Xin dành việc update phần xử
lý xâu kí tự cho bạn đọc để có được một chương trình toàn vẹn hơn.
uses crt;
type ptr=^node;
node = record
info : char;
l,r : ptr;
end;
bg = record
info : char;
ut : integer;
end;
const maxbg = 256;
var s : string;
a : array[1..maxbg]of bg;
sbg:integer; Tree:ptr; result:real;
procedure Bt_to_bg;
{Từ biểu thức nhập vào xây dựng nên mảng các bản ghi}
ar i,j,k,uutien:integer;
begin
Write('Ban can tinh bieu thuc : '); readln(s);
uutien:=0; sbg:=0;
for i:=1 to length(s) do
begin
inc(sbg);
a[sbg].info:=s[i];
case s[i] of
'(' : begin
inc(uutien,2);

dec(sbg);
end;
')' : begin
dec(uutien,2);
dec(sbg);
end;
'0'..'9','A'..'z' : a[sbg].ut:=10000;
'+','-' : a[sbg].ut:=1 + uutien;
'*','/' : a[sbg].ut:=2 + uutien;
end;
end;
end;
function Right_min_bg(d,c:integer):integer ;
{Tim vi tri phai nhat co uu tien min trong a}
var i,j,k:integer;
begin
k:=10000;
for i:=c downto d do
begin
if a[i].ut
begin
k:=a[i].ut;
j:=i;
end;
end;
Right_min_bg:=j;
end;
function Bg_to_Tree(d,c:integer):ptr;
{Xây dựng cây biểu thức từ mảng các bản ghi}
var i,j,k:integer; p:ptr;

begin
new(p);
i:=Right_min_bg(d,c);
with P^ do
begin
if d
begin
info:=a[i].info;
l:=Bg_to_Tree(d,i-1);
r:=Bg_to_Tree(i+1,c);
end
else
begin
info:=a[d].info;
l:=nil;
r:=nil;
end;
end;
Bg_to_Tree:=P;
end;
function DuyetTruoc(T:ptr):real;
{Duyệt cây theo thứ tự trước để tính giá trị của biểu thức theo kiểu tiền tố}
var val:real;
begin
with T^ do
begin
case info of
'0'..'9' : val:=ord(info)-ord('0');
'A'..'z' : begin
write('Nhap gia tri cho ',info,'=');

readln(val);
end;
'+' : val:=DuyetTruoc(l)+DuyetTruoc(r);