Chuyển biểu thức trung tố sang tiền tố và hậu tố bằng Stack

Các biểu thức đại số được sử dụng hằng ngày đều được biểu diễn dưới dạng trung tố (infix). Cách biểu diễn này rất dễ hiểu với con người vì hầu hết các toán tử (+, -, *, /) đều là toán tử hai ngôi và chúng phân cách giữa hai toán hạng với nhau. Tuy nhiên đối với máy tính, để tính được giá trị của một biểu thức đại số theo dạng này không đơn giản như ta vẫn làm. Để khắc phục điều đó, máy tính cần chuyển cách biểu diễn các biểu thức đại số từ trung tố sang một dạng khác là tiền tố hoặc hậu tố.

Thế nào là biểu thức tiền tố, trung tố và hậu tố

Trong đoạn giới thiệu trên có lẽ bạn cũng hình dung được thế nào là biểu thức trung tố, hiểu đơn giản tức là toán tử sẽ được đặt giữa hai toán hạng, dĩ nhiên đây phải là toán tử hai ngôi. Vậy dựa vào vị trí của của toán tử, liệu ta có thể biểu diễn biểu thức đại số dưới dạng khác? Câu trả lời là được, và như đã nói, ta có ba cách là biểu thức tiền tố (prefix), trung tố (infix) và hậu tố (postfix). Hãy xem một chút giới thiệu về cách biểu diễn biểu thức tiền tố và hậu tố để hiểu rõ hơn về chúng.

-       Prefix: Biểu thức tiền tố được biểu diễn bằng cách đặt toán tử lên trước các toán hạng. Cách biểu diễn này còn được biết đến với tên gọi “ký pháp Ba Lan” do nhà toán học Ba Lan Jan Łukasiewicz phát minh năm 1920. Với cách biểu diễn này, thay vì viết x+y như dạng trung tố, ta sẽ viết +xy. Tùy theo độ ưu tiên của toán tử mà chúng sẽ được sắp xếp khác nhau, bạn có thể xem một số ví dụ ở phía sau phần giới thiệu này.

-       Postfix: Ngược lại với cách Prefix, tức là các toán tử sẽ được đặt sau các toán hạng. Cách biểu diễn này được gọi là “ký pháp nghịch đảo Ba Lan” hoặc được viết tắt là RPN (Reverse Polish notation), được phát minh vào khoảng giữa thập kỷ 1950 bởi một triết học gia và nhà khoa học máy tính Charles Hamblin người Úc.

Một số ví dụ:

Infix	Prefix	Postfix
x+y	+xy	xy+
x+y-z	-+xyz	xy+z -
x+y*z	+x*yz	xyz*+
x+(y-z)	+x-yz	xyz-+

Độ ưu tiên của các toán tử

Một trong những điều quan trọng trước khi bắt đầu là phải tính toán được độ ưu tiên của các toán tử trong biểu thức nhập vào. Để đơn giản ta chỉ xét các toán tử hai ngôi và thường dùng bao gồm: multiply (+),subtract (-), multiply (*), divide (/), Modulo (%). Theo đó các toán tử “*, /, %” có cùng độ ưu tiên và cao hơn hai toán tử “+, -”.

Các phương thức kiểm tra toán tử và toán hạng

Trong thuật toán chuyển đổi này ta cần có các phương thức kiểm tra xem một thành phần của chuỗi có phải là toán tử hoặc toán hạng không. Thay vì sử dụng các cấu trúc if hoặc switch dài dòng và bất tiện khi phát triển, ta sẽ dùng Regex để kiểm tra.

Ngoài ra vì chuỗi nhập vào là một biểu thức đại số, nên các toán hạng ta sẽ xét không chỉ là các chữ số mà còn có chữ cái từ a-z và A-Z.

Có một quy tắc nữa là khi dùng chữ cái thì chỉ cho phép duy nhất một chữ cái đại diện cho một toán hạng, còn khi dùng chữ số thì có thể nhiều chữ số ghép thành một toán hạng.

Chuyển biểu thức Infix sang Postfix

Lý do tôi trình bày thuật toán chuyển sang postfix trước vì thuật toán này phổ biến và dễ cài đặt hơn, bạn cũng sẽ thấy sự tương đồng của thuật toán này với thuật toán chuyển từ infix sang prefix khi tôi trình bày ở phần sau.

Thuật toán để chuyển một biểu thức Infix sang dạn Prefix:

Đọc từng token trong biểu thức infix từ trái qua phải, với mỗi token ta thực hiện các bước sau:

-       Nếu là toán hạng: cho ra output.

-       Nếu là dấu mở ngoặc “(“: cho vào stack

-       Nếu là dấu đóng ngoặc “)”: lấy các toán tử trong stack ra và cho vào output cho đến khi gặp dấu mở ngoặc “(“. (Dấu mở ngoặc cũng phải được đưa ra khỏi stack)

-       Nếu là toán tử:

• Chừng nào ở đỉnh stack là toán tử và toán tử đó có độ ưu tiên lớn hơn hoặc bằng toán tử hiện tại thì lấy toán tử đó ra khỏi stack và cho ra output.
• Đưa toán tử hiện tại vào stack

Sau khi duyệt hết biểu thức infix, nếu trong stack còn phần tử thì lấy các token trong đó ra và cho lần lượt vào output.

Hãy xem ví dụ sau để hiểu rõ hơn thuật toán này.

Chúng ta sẽ chuyển biểu thức A*B+C*((D-E)+F)/G từ dạng Infix sang dạng Postfix:

Token	Stack	Output
A	{Empty}	A
*	*	A
B	*	A B
+	+	A B *
C	+	A B * C
*	+ *	A B * C
(	+ * (	A B * C
(	+ * ( (	A B * C
D	+ * ( (	A B * C D
-	+ * ( ( -	A B * C D
E	+ * ( ( -	A B * C D E
)	+ * (	A B * C D E -
+	+ * ( +	A B * C D E -
F	+ * ( +	A B * C D E – F
)	+ *	A B * C D E – F +
/	+ /	A B * C D E – F + *
G	+ /	A B * C D E – F + * G
	{Empty}	A B * C D E – F + * G / +

Chuyển biểu thức Infix sang Prefix

Không có nhiều sự khác biệt giữa việc chuyển từ Infix sang Prefix với Infix sang Postfix, chủ yếu là sự thay đổi thứ tự duyệt từ phải sang trái thay vì từ trái sang phải. Và thay vì duyệt theo hướng ngược lại như thế bạn có thể thực hiện một chuyển đổi nhỏ để đảo ngược biểu thức nhập vào.

Chú ý là tôi sử dụng “đảo ngược biểu thức” thay vì ”đảo ngược chuỗi”, việc đảo ngược này phải giữ nguyên được giá trị của các toán hạng, ví dụ bạn không thể đảo ngược 12 thành 21 được. Hơn nữa vì chuỗi đã đảo ngược nên các dấu ngoặc đơn cũng phải được hiểu ngược lại. Cụ thể ta có ví dụ sau:

Chuyển biểu thức Infix A*B+C*((D-E)+F)/G sang dạng Prefix

Đầu tiên ta đảo ngược biểu thức trên thành G/)F+)E-D((*C+B*A, sau đó ta thực hiện các bước trong thuật toán sau:

Đọc từng token trong biểu thức infix từ trái qua phải, với mỗi token ta thực hiện các bước sau:
-       Nếu là toán hạng: cho ra output.
-       Nếu là dấu đóng ngoặc “)“: cho vào stack
-       Nếu là dấu mở ngoặc “(”: lấy các toán tử trong stack ra và cho vào output cho đến khi gặp dấu đóng ngoặc “)“. (Dấu đóng ngoặc cũng phải được đưa ra khỏi stack)
-       Nếu là toán tử:
* Chừng nào ở đỉnh stack là toán tử và toán tử đó có độ ưu tiên lớn hơn toán tử hiện tại thì lấy toán tử đó ra khỏi stack và cho ra output.
* Đưa toán tử hiện tại vào stack.

Sau khi duyệt hết biểu thức infix, nếu trong stack còn phần tử thì lấy các token trong đó ra và cho lần lượt vào output. Cuối cùng là đảo ngược biểu thức một lần nữa và ta sẽ thu được kết quả.

 Các bạn có thể tham khảo sourse code trong C++ giải bài toán chuyển biểu thức trung tố sang tiền tố:

int tiento(char a[])
{
char b[100],c[100]; //b la chuoi kq, c la chuoi chua cac ky tu la toan tu
int top=-1,n=-1;
for(int i=strlen(a);i>=0;i--) //quet tu cuoi len
{
if('0'<=a[i]&&a[i]<='9') //neu la toan hang cho vao b
{
n++;
b[n]=a[i];
}
if(a[i]==')') //neu la ')' cho vao c
{
top++;
c[top]=a[i];
}
if(a[i]=='(') 
{
do
{
n++; //neu la '(' thi lan luot cho nhung toan tu trong c vao b cho den khi gap ')'
b[n]=c[top]; 
top--;
}while(c[top]!=')');
top--; //bo dau ')'
}
if(a[i]=='+'||a[i]=='-'||a[i]=='*'||a[i]=='/') // Neu la toan tu
{
if(((a[i]=='+'||a[i]=='-')&&(c[top]=='*'||c[top]=='/'))||(a[i]=='*')&&(c[top]=='/')||(a[i]=='/')&&(c[top]=='*'))
{//if (toan tu cuoi cung trong c co do uu tien lon hon hoac bang toan tu dang duyet
n++;
b[n]=c[top]; //thi cho toan tu do vao b-kq
top--;
}
top++;
c[top]=a[i]; //cho toan tu dang duyet vao c
}
}
if(top>-1)
{
for(int i=top;i>=0;i--){ //sau khi duyet het ma trong c van con phan tu thi lan luot cho vao b
n++;
b[n]=c[i];
}

}
for(int i=n;i>=0;i--) printf("%c",b[i]); //xuat nguoc b ta duoc kq
}