Giải thuật và lập trình: §7. Ký pháp tiền tố, trung tố và hậu tố


BIỂU THỨC DƯỚI DẠNG CÂY NHỊ PHÂN

Chúng ta có thể biểu diễn các biểu thức số học gồm các phép toán cộng, trừ, nhân, chia bằng một cây nhị phân, trong đó các nút lá biểu thị các hằng hay các biến (các toán hạng), các nút không phải là lá biểu thị các toán tử (phép toán số học chẳng hạn). Mỗi phép toán trong một nút sẽ tác động lên hai biểu thức con nằm ở cây con bên trái và cây con bên phải của nút đó.

Ví dụ: Cây biểu diễn biểu thức (6 / 2 + 3) * (7 - 4) như sau:

http://v1study.com/public/images/article/giai-thuat-va-lap-trinh-bieu-thuc-duoi-dang-cay-nhi-phan.png

Biểu thức dưới dạng cây nhị phân

CÁC KÝ PHÁP CHO CÙNG MỘT BIỂU THỨC

Với cây nhị phân biểu diễn biểu thức trong hình trên thì:

  • Nếu duyệt theo thứ tự trước, ta sẽ được * + / 6 2 3 - 7 4, đây là dạng tiền tố (prefix) của biểu thức. Trong ký pháp này, toán tử được viết trước hai toán hạng tương ứng, người ta còn gọi ký pháp này là ký pháp Ba Lan.

  • Nếu duyệt theo thứ tự giữa, ta sẽ được 6 / 2 + 3 * 7 - 4. Ký pháp này hơi mập mờ vì thiếu dấu ngoặc. Nếu thêm vào thủ tục duyệt inorder việc bổ sung các cặp dấu ngoặc vào mỗi biểu thức con sẽ thu được biểu thức (((6 / 2) + 3) * (7 - 4)). Ký pháp này gọi là dạng trung tố (infix) của một biểu thức (Thực ra chỉ cần thêm các dấu ngoặc đủ để tránh sự mập mờ mà thôi, không nhất thiết phải thêm vào đầy đủ các cặp dấu ngoặc).

  • Nếu duyệt theo thứ tự sau, ta sẽ được 6 2 / 3 + 7 4 - *, đây là dạng hậu tố (postfix) của biểu thức. Trong ký pháp này toán tử được viết sau hai toán hạng, người ta còn gọi ký pháp này là ký pháp nghịch đảo Balan (Reverse Polish Notation - RPN)

Chỉ có dạng trung tố mới cần có dấu ngoặc, dạng tiền tố và hậu tố không cần phải có dấu ngoặc.

CÁCH TÍNH GIÁ TRỊ BIỂU THỨC

Có một vấn đề cần lưu ý là khi máy tính giá trị một biểu thức số học gồm các toán tử hai ngôi (toán tử gồm hai toán hạng như +, -, *, /) thì máy chỉ thực hiện được phép toán đó với hai toán hạng. Nếu biểu thức phức tạp thì máy phải chia nhỏ và tính riêng từng biểu thức trung gian, sau đó mới lấy giá trị tìm được để tính tiếp. Ví dụ như biểu thức 1 + 2 + 4 máy sẽ phải tính 1 + 2 trước được kết quả là 3 sau đó mới đem 3 cộng với 4 chứ không thể thực hiện phép cộng một lúc ba số được.

Khi lưu trữ biểu thức dưới dạng cây nhị phân thì ta có thể coi mỗi nhánh con của cây đó mô tả một biểu thức trung gian mà máy cần tính khi xử lý biểu thức lớn. Như ví dụ trên, máy sẽ phải tính hai biểu thức 6 / 2 + 3 và 7 - 4 trước khi làm phép tính nhân cuối cùng. Để tính biểu thức 6 / 2 + 3 thì máy lại phải tính biểu thức 6 / 2 trước khi đem cộng với 3.

Vậy để tính một biểu thức lưu trữ trong một nhánh cây nhị phân gốc ở nút n, máy sẽ tính gần giống như hàm đệ quy sau:

function Calculate(n): Value; {Tính biểu thức con trong nhánh cây gốc n}

begin

if <Nút n chứa không phải là một toán tử> then Calculate := <Giá trị chứa trong nút n>

else {Nút n chứa một toán tử R}

begin

x := Calculate(nút con trái của n);

y := Calculate(nút con phải của n);

Calculate := x R y;

end;

end.

(Trong trường hợp lập trình trên các hệ thống song song, việc tính giá trị biểu thức ở cây con trái và cây con phải có thể tiến hành đồng thời làm giảm đáng kể thời gian tính toán biểu thức).

Để ý rằng khi tính toán biểu thức, máy sẽ phải quan tâm tới việc tính biểu thức ở hai nhánh con trước, rồi mới xét đến toán tử ở nút gốc. Điều đó làm ta nghĩ tới phép cây theo thứ tự sau và ký pháp hậu tố. Trong những năm đầu 1950, nhà lô-gic học người Balan Jan Lukasiewicz đã chứng minh rằng biểu thức hậu tố không cần phải có dấu ngoặc vẫn có thể tính được một cách đúng đắn bằng cách đọc lần lượt biểu thức từ trái qua phải và dùng một Stack để lưu các kết quả trung gian:

Bước 1: Khởi động một Stack rỗng

Bước 2: Đọc lần lượt các phần tử của biểu thức RPN từ trái qua phải (phần tử này có thể là hằng, biến hay toán tử) với mỗi phần tử đó, ta kiểm tra:

- Nếu phần tử này là một toán hạng thì đẩy giá trị của nó vào Stack.

- Nếu phần tử này là một toán tử ®, ta lấy từ Stack ra hai giá trị (y và x) sau đó áp dụng toán tử ® đó vào hai giá trị vừa lấy ra, đẩy kết quả tìm được (x ® y) vào Stack (ra hai vào một).

Bước 3: Sau khi kết thúc bước 2 thì toàn bộ biểu thức đã được đọc xong, trong Stack chỉ còn duy nhất một phần tử, phần tử đó chính là giá trị của biểu thức.

Ví dụ: Tính biểu thức 10 2 / 3 + 7 4 - * (tương ứng với biểu thức (10 / 2 + 3) * (7 - 4).

Đọc

Xử lý

Stack

10

Đẩy vào Stack

10

2

Đẩy vào Stack

10, 2

/

Lấy 2 và 10 khỏi Stack, Tính được 10 / 2 = 5, đẩy 5 vào Stack

5

3

Đẩy vào Stack

5, 3

+

Lấy 3 và 5 khỏi Stack, tính được 5 + 3 = 8, đẩy 8 vào Stack

8

7

Đẩy vào Stack

8, 7

4

Đẩy vào Stack

8, 7, 4

-

Lấy 4 và 7 khỏi Stack, tính được 7 - 4 = 3, đẩy 3 vào Stack

8, 3

*

Lấy 3 và 8 khỏi Stack, tính được 8 * 3 = 24, đẩy 24 vào Stack

24

Ta được kết quả là 24.

Dưới đây ta sẽ viết một chương trình đơn giản tính giá trị biểu thức RPN. Chương trình sẽ nhận Input là biểu thức RPN gồm các số thực và các toán tử + - * / và cho Output là kết quả biểu thức đó.

Quy định khuôn dạng bắt buộc là hai số liền nhau trong biểu thức RPN phải viết cách nhau ít nhất một dấu cách. Để quá trình đọc một phần tử trong biểu thức RPN được dễ dàng hơn, sau bước nhập liệu, ta có thể hiệu chỉnh đôi chút biểu thức RPN về khuôn dạng dễ đọc nhất. Chẳng hạn như thêm và bớt một số dấu cách trong Input để mỗi phần tử (toán hạng, toán tử) đều cách nhau đúng một dấu cách, thêm một dấu cách vào cuối biểu thức RPN. Khi đó quá trình đọc lần lượt các phần tử trong biểu thức RPN có thể làm như sau:

T := '';

for p := 1 to Length(RPN) do {Xét các ký tự trong biểu thức RPN từ trái qua phải}

if RPN[p] # ' ' then T := T + RPN[p] {Nếu RPN[p] không phải dấu cách thì nối ký tự đó vào T}

else {Nếu RPN[p] là dấu cách thì phần tử đang đọc đã đọc xong, tiếp theo sẽ là phần tử khác}

begin

<Xử lý phần tử T>

T := ''; {Chuẩn bị đọc phần tử mới}

end;

Để đơn giản, chương trình không kiểm tra lỗi viết sai biểu thức RPN, việc đó chỉ là thao tác tỉ mỉ chứ không phức tạp lắm, chỉ cần xem lại thuật toán và cài thêm các mô-đun bắt lỗi tại mỗi bước.

Ví dụ về Input / Output của chương trình:

Nhập vào biểu thức RPN: 10 2/3  + 4 7 -*

10 2 / 3 + 4 7 - * = 24.0000

{$N+,E+}

Ta có chương trình như sau:

program CalculateRPNExpression;

const

Opt = ['+', '-', '*', '/'];

var

T, RPN: String;

Stack: array[1..255] of Extended;

p, Last: Integer;

{Các thao tác đối với Stack}

procedure StackInit;

begin

Last := 0;

end;

procedure Push(V: Extended);

begin

Inc(Last); Stack[Last] := V;

end;

function Pop: Extended;

begin

Pop := Stack[Last]; Dec(Last);

end;

procedure Refine(var S: String); {Hiệu chỉnh biểu thức RPN về khuôn dạng dễ đọc nhất}

var

i: Integer;

begin

S := S + ' ';

for i := Length(S) - 1 downto 1 do {Thêm những dấu cách giữa toán hạng và toán tử}

if (S[i] in Opt) or (S[i + 1] in Opt) then Insert(' ', S, i + 1);

for i := Length(S) - 1 downto 1 do {Xoá những dấu cách thừa}

if (S[i] = ' ') and (S[i + 1] = ' ') then Delete(S, i + 1, 1);

end;

procedure Process(T: String); {Xử lý phần tử T đọc được từ biểu thức RPN}

var

x, y: Extended;

e: Integer;

begin

if not (T[1] in Opt) then {T là toán hạng}

begin

Val(T, x, e);

Push(x); {Đổi T thành số và đẩy giá trị đó vào Stack}

end

else {T là toán tử}

begin

y := Pop;

x := Pop; {Ra hai}

case T[1] of

'+': x := x + y;

'-': x := x - y;

'*': x := x * y;

'/': x := x / y;

end;

Push(x); {Vào một}

end;

end;

begin

Write('Enter RPN Expression: '); ReadLn(RPN);

Refine(RPN);

StackInit; T := '';

for p := 1 to Length(RPN) do {Xét các ký tự của biểu thức RPN từ trái qua phải}

if RPN[p] <> ' ' then T := T + RPN[p] {nếu không phải dấu cách thì nối nó vào sau xâu T}

else {Nếu gặp dấu cách}

begin

Process(T); {Xử lý phần tử vừa đọc xong}

T := ''; {Đặt lại T để chuẩn bị đọc phần tử mới}

end;

WriteLn(RPN, ' = ', Pop:0:4); {In giá trị biểu thức RPN được lưu trong Stack}

end.

CHUYỂN TỪ DẠNG TRUNG TỐ SANG DẠNG HẬU TỐ

Có thể nói rằng việc tính toán biểu thức viết bằng ký pháp nghịch đảo Balan là khoa học hơn, máy móc, và đơn giản hơn việc tính toán biểu thức viết bằng ký pháp trung tố. Chỉ riêng việc không phải xử lý dấu ngoặc đã cho ta thấy ưu điểm của ký pháp RPN. Chính vì lý do này, các chương trình dịch vẫn cho phép lập trình viên viết biểu thức trên ký pháp trung tố theo thói quen, nhưng trước khi dịch ra các lệnh máy thì tất cả các biểu thức đều được chuyển về dạng RPN. Vấn đề đặt ra là phải có một thuật toán chuyển biểu thức dưới dạng trung tố về dạng RPN một cách hiệu quả, và dưới đây ta trình bày thuật toán đó:

Thuật toán sử dụng một Stack để chứa các toán tử và dấu ngoặc mở. Thủ tục Push(V) để đẩy một phần tử vào Stack, hàm Pop để lấy ra một phần tử từ Stack, hàm Get để đọc giá trị phần tử nằm ở đỉnh Stack mà không lấy phần tử đó ra. Ngoài ra mức độ ưu tiên của các toán tử được quy định bằng hàm Priority như sau: Ưu tiên cao nhất là dấu "*" và "/" với Priority là 2, tiếp theo là dấu "+" và "-" với Priority là 1, ưu tiên thấp nhất là dấu ngoặc mở "(" với Priority là 0.

Stack := ø;

for <Phần tử T đọc được từ biểu thức infix> do

{T có thể là hằng, biến, toán tử hoặc dấu ngoặc được đọc từ biểu thức infix theo thứ tự từ trái qua phải}

case T of

'(': Push(T); ')':

repeat

x := Pop;

if x # '(' then Output(x);

until x = '(';

'+', '-', '*', '/':

begin

while (Stack # ø) and (Priority(T) ≤ Priority(Get)) do Output(Pop);

Push(T);

end;

else Output(T);

end;

while (Stack # ø) do Output(Pop);

Ví dụ với biểu thức trung tố (2 * 3 + 7 / 8) * (5 - 1) ta có như sau:

Đọc

Xử lý

Stack

Output

(

Đẩy vào Stack

(

 

2

Hiển thị

(

2

*

phép "*" được ưu tiên hơn phần tử ở đỉnh Stack là "(", đẩy "*" vào Stack

(*

 

3

Hiển thị

(*

2 3

+

phép "+" ưu tiên không cao hơn phần tử ở đỉnh Stack là "*", lấy ra và hiển thị "*". So sánh tiếp, thấy phép "+" được ưu tiên cao hơn phần tử ở đỉnh Stack là "(", đẩy "+" vào Stack

(+

2 3 *

7

Hiển thị

(+

2 3 * 7

/ phép "/" được ưu tiên hơn phần tử ở đỉnh Stack là "+", đẩy "/" vào Stack (+/  
8 Hiển thị (+/ 2 3 * 7 8
) Lấy ra và hiển thị các phần tử trong Stack tới khi lấy phải dấu ngoặc mở ø 2 3 * 7 8 / +
* Stac đang là rỗng, đẩy * vào Stack *  
( Đẩy vào Stack *(  
5 Hiển thị *( 2 3 * 7 8 / + 5
- phép "-" được ưu tiên hơn phần tử ở đỉnh Stack là "(", đẩy "-" vào Stack *(-  
1 Hiển thị *(- 2 3 * 7 8 / + 5 1
) Lấy ra và hiển thị các phần tử ở đỉnh Stack cho đến khi lấy phải dấu ngoặc mở * 2 3 * 7 8 / + 5 1 -
Hết Lấy ra và hiển thị hết các phần tử còn lại trong Stack   2 3 * 7 8 / + 5 1 - *

Dưới đây là chương trình chuyển biểu thức viết ở dạng trung tố sang dạng RPN. Biểu thức trung tố đầu vào sẽ được hiệu chỉnh sao cho mỗi thành phần của nó được cách nhau đúng một dấu cách, và thêm một dấu cách vào cuối cho dễ tách các phần tử ra để xử lý. Vì Stack chỉ dùng để chứa các toán tử và dấu ngoặc mở nên có thể mô tả Stack dưới dạng xâu ký tự cho đơn giản.

Ví dụ về Input / Output của chương trình:

Infix: (10*3 +  7 /8) * (5-1)

Refined: ( 10 * 3 + 7 / 8 ) * ( 5 - 1 )

RPN: 10 3 * 7 8 / + 5 1 - *

P_2_07_2.PAS * Chuyển biểu thức trung tố sang dạng RPN

program ConvertInfixToRPN; const

Opt = ['(', ')', '+', '-', '*', '/'];

var

T, Infix, Stack: String; {Stack dùng để chứa toán tử và dấu ngoặc mở nên dùng String cho tiện}

p: Integer;

{Các thao tác đối với Stack}

procedure StackInit; begin

Stack := '';

end;

procedure Push(V: Char);

begin

Stack := Stack + V;

end;

function Pop: Char;

begin

Pop := Stack[Length(Stack)];

Dec(Stack[0]);

end;

function Get: Char;

begin

Get := Stack[Length(Stack)];

end;

procedure Refine(var S: String); {Hiệu chỉnh biểu thức trung tố về khuôn dạng dễ đọc nhất}

var

i: Integer;

begin

S := S + ' ';

for i := Length(S) - 1 downto 1 do {Thêm những dấu cách trước và sau mỗi toán tử và dấu ngoặc}

if (S[i] in Opt) or (S[i + 1] in Opt) then Insert(' ', S, i + 1);

for i := Length(S) - 1 downto 1 do {Xoá những dấu cách thừa}

if (S[i] = ' ') and (S[i + 1] = ' ') then Delete(S, i + 1, 1);

end;

function Priority(Ch: Char): Integer; {Hàm lấy mức độ ưu tiên của Ch}

begin

case ch of

'*', '/': Priority := 2;

'+', '-': Priority := 1;

'(': Priority := 0;

end;

end;

procedure Process(T: String); {Xử lý một phần tử đọc được từ biểu thức trung tố}

var

c, x: Char;

begin

c := T[1];

if not (c in Opt) then Write(T, ' ')

else

case c of

'(': Push(c); ')': repeat

x := Pop;

if x <> '(' then Write(x, ' ');

until x = '(';

'+', '-', '*', '/':

begin

while (Stack <> '') and (Priority(c) <= Priority(Get)) do Write(Pop, ' ');

Push(c);

end;

end;

end;

begin

Write('Infix = '); ReadLn(Infix);

Refine(Infix);

WriteLn('Refined: ', Infix);

Write('RPN: ');

T := '';

for p := 1 to Length(Infix) do

if Infix[p] <> ' ' then T := T + Infix[p]

else

begin

Process(T); T := '';

end;

while Stack <> '' do Write(Pop, ' ');

WriteLn;

end.

XÂY DỰNG CÂY NHỊ PHÂN BIỂU DIỄN BIỂU THỨC

Ngay trong phần đầu tiên, chúng ta đã biết rằng các dạng biểu thức trung tố, tiền tố và hậu tố đều có thể được hình thành bằng cách duyệt cây nhị phân biểu diễn biểu thức đó theo các trật tự khác nhau. Vậy tại sao không xây dựng ngay cây nhị phân biểu diễn biểu thức đó rồi   thực hiện các công việc tính toán ngay trên cây?. Khó khăn gặp phải chính là thuật toán xây dựng cây nhị phân trực tiếp từ dạng trung tố có thể kém hiệu quả, trong khi đó từ dạng hậu tố lại có thể khôi phục lại cây nhị phân biểu diễn biểu thức một cách rất đơn giản, gần giống như quá trình tính toán biểu thức hậu tố:

Bước 1: Khởi tạo một Stack rỗng dùng để chứa các nút trên cây

Bước 2: Đọc lần lượt các phần tử của biểu thức RPN từ trái qua phải (phần tử này có thể là hằng, biến hay toán tử) với mỗi phần tử đó:

Tạo ra một nút mới N chứa phần tử mới đọc được

Nếu phần tử này là một toán tử, lấy từ Stack ra hai nút (theo thứ tự là y và x), sau đó đem liên kết trái của  N trỏ đến x, đem liên kết phải của N trỏ đến y.

Đẩy nút N vào Stack

Bước 3: Sau khi kết thúc bước 2 thì toàn bộ biểu thức đã được đọc xong, trong Stack chỉ còn duy nhất một phần tử, phần tử đó chính là gốc của cây nhị phân biểu diễn biểu thức.

Bài tập

Bài 1

Viết chương trình chuyển biểu thức trung tố sang dạng RPN, biểu thức trung tố có cả những phép toán một ngôi: Phép lấy số đối (-x), phép luỹ thừa xy (x^y), lời gọi hàm số học (sqrt, exp, abs v.v…)

Bài 2

Viết chương trình chuyển biểu thức logic dạng trung tố sang dạng RPN. Ví dụ: Chuyển: a and b or c and d  thành: a b and c d and or

Bài 3

Chuyển các biểu thức sau đây ra dạng RPN:

a) A * (B + C) b) A + B / C + D

c) A * (B + -C) d) A - (B + C)d/e

e) A and B or C f) A and (B or not C)

g) (A or B) and (C or (D and not E))  h) (A = B) or (C = D)

i) (A < 9) and (A > 3) or not (A > 0)

j) ((A > 0) or (A < 0)) and (B * B - 4 * A * C < 0)

Bài 4

Viết chương trình tính biểu thức logic dạng RPN với các toán tử and, or, not và các toán hạng là TRUE hay FALSE.

Bài 5

Viết chương trình hoàn chỉnh tính giá trị biểu thức trung tố.

« Prev
Next »