Đầu tiên nói về cái công cụ cần đã, sau đó sẽ làm tất cả các bài tập dạng này mà thầy ra.

Để kiểm tra kết quả có chính xác không chỉ chuyển từ trung tố sang hậu tố và ngược lại, bạn có thể dùng một dịch vụ chuyển đổi trực tuyến cũng sẽ thực hiện tính toán giá trị của biểu thức sau khi chuyển đổi.

Để tránh quên, tạm viết lại một số khái niệm vào đây để các bạn đỡ mất công tra, đồng thời thống nhất được các định nghĩa.
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ố.
Trong bài này tôi sẽ giới thiệu kĩ thuật để giúp máy tính thực hiện điều này thông qua ngôn ngữ minh họa C#.

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 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-

Phương pháp chuyển từ biểu thức trung tố sang tiền tố và hậu tố

Có hai cách để chuyển một biểu thức từ trung tố sang hai loại còn lại đó là dùng:
- Stack
- Expression Tree (cây biểu thức)
Việc dùng Stack phổ biến hơn có ưu điểm là dễ cài đặt, đơn giản còn dùng Expression Tree sẽ giúp việc chuyển đổi được dễ hiểu và trực quan hơn tuy nhiên lại mất thời gian cài đặt. Trong bài viết này chỉ trình bày kĩ thuật sử dụng Stack, kĩ thuật dùng Expression Tree sẽ được
giới thiệu trong bài viết sau.

Độ ư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ử “ , -”. Như vậy ta có phương thức lấy độ ưu tiên toán tử như sau:

1	Xác định mức ưu tiên toán tử nằm trong chuỗi biểu thức (toantu)

2

{

3	if (toantu := "*" OR toantu := "/" OR toantu == "%")

4

return 2;

5	if (toantu := " " OR toantu == "-")

6

return 1;

7

return 0;

8

}

Định dạng lại biểu thức Infix trước khi chuyển đổi
Các biểu thức Infix khi nhập vào có thể dư thừa các khoảng trắng, các kí tự không phù hợp hoặc viết sai cú pháp. Phần kiểm tra cú pháp bạn có thể làm riêng hoặc để luôn trong các thuật toán chuyển đổi. Trong phần này yêu cầu định dạng để các phần tử của biểu thức (toán tử, toán hạng) phải được phân cách với nhau bằng một khoảng trắng. Các phần tử gọi là các token.
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. Ví dụ viết ab phải hiểu là a*b, viết 123 không được hiểu là 1*2*3.

1	Chương_trình_con_Nhận_dạng_toán_tử_tên_là IsOperator(string str)

2

{

3	Trả_về_đúng_khi_str_thuộc_một_trong_(str, @" |-|*|/|%");

4

}

5	Chương_trình_con_nhận_dạng_toán_hạng_là_chữ IsOperand(string str)

6

{

7	Trả_về_đúng_khi_str_chứa_ký_tự_đầu_tiên_trong_(str, @"^d $|^([a-z]|[A-Z])$");

8

}

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à đưa phần lấy đó nối thêm 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ử xét các trường hợp:

• 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à nối thêm vào 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.</blockquote>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 /

So sánh thứ tự của các toán hạng khi viết một biểu thức ở dạng trung tố và hậu tố:
Nếu ta không quan tâm đến toán tử, mà chỉ quan sát các toán hạng thôi thì sẽ thấy:
Thứ tự các toán hạng ở cả 2 cách viết trung tố và hậu tố là như nhau.
Ví dụ như ở trung tố thứ tự của toán hạng là A toán tử B toán tử C... dấu ngoặc ưu tiên lung tung.
Thì thứ tự toán hạng ở hậu tố cũng lần lượt A B C nhưng toán tử của phép tính được sắp xếp cho phép tính thực hiện trước.

Đề bài: Cho M = Biểu thức trung tố. Viết biểu thức dạng hậu tố N, N=M.
Ý tưởng:
- Duyệt từng phần tử trong M cho đến hết.
- Nếu Mi là toán hạng: nối thêm vào N.
- 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à đưa phần lấy đó nối thêm vào N 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ử xét các trường hợp:

• 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à nối thêm vào N.
  
• Đưa toán tử hiện tại vào stack
  

Khi duyệt xong chuỗi M, nếu Stack còn chưa rỗng thì lấy lần lượt ra cho đến Stack.
Giải thuật:

- Khởi tạo Stack rỗng: S.

- Xây dựng hàm con xét độ ưu tiên	UT(x)
	CASE x	of
	*,/,%:	UT=2
	-, + :	UT=1
	ELSE:	UT=0
	END

- Bắt đầu chương trình

For i:=1 to /M/
	CASE Mi of
	Toán hạng:
		N = N + Mi;
	(:
		Push(Mi, S);
	):
		While x<> "("
		N=N +x;
		Pop(S,x);
		End While
	Toán tử:
		IF UT(Top(S)>=UT(Mi) Then
			Pop(S,x);
			N=N + x;
		ELSE	Push(Mi,S)
	End Case
Repeat
	Pop(S,x);
	IF x <>"("	N:=N + x
Until Empty(S)
Output (N)

Để tính toán một biểu thức trung tố bất kỳ, xen kẽ các toán tử, thì ta nên nhớ thứ tự ưu tiên các toán tử trước nếu không nhóm các dấu ngoặc lại. Còn có dấu ngoặc thì thực hiện các phép tính trong dấu ngoặc trong cùng trước.
Ở đây ta sẽ sử dụng 2 ngăn xếp. Điều này cho phép tính toán dễ hơn và không gây nhầm lẫn.

Ý tưởng:

Giả sử xâu M là xâu trung tố cần tính. Ở đây có điều kiện là xâu M đúng đắn, các phép toán hoàn toàn hợp lệ và có thể thực hiện được.
B1- Duyệt cho đến hết M.
B2- Đọc một phần tử Mi.
B3- Nếu gặp một toán hạng thì ghi nó vào stack S1.
B4- Nếu gặp dấu mở ngoặc, đưa nó vào stack S2.
B5- Nếu gặp một toán tử (gọi là o1), thực hiện hai bước sau:
o Chừng nào còn có một toán tử o2 ở (đỉnh ngăn xếp S2) VÀ độ ưu tiên của o1 nhỏ hơn hay bằng độ ưu tiên của o2 thì lấy o2 ra khỏi S2 để tính toán với 2 toán hạng của S1
o Push o1 vào ngăn xếp S2.
- Nếu gặp dấu đóng ngoặc thì cứ lấy các toán tử trong ngăn xếp S2 ra và tính toán cho đến khi lấy được dấu mở ngoặc ra khỏi ngăn xếp S2.
- Khi đã duyệt hết biểu thức trung tố, lần lượt lấy tất cả toán hạng (nếu còn) từ ngăn xếp S2 ra và tính toán với toán hạng trong S1.

- Khởi tạo 2 Stack rỗng: S1, S2;

- Xây dựng hàm con xét độ ưu tiên	UT(x)
	CASE x
	*,/,%:	UT=2
	-, + :	UT=1
	ELSE:	UT=0
	END

- Bắt đầu chương trình

For i:=1 to /M/
	Case Mi of:
	Toán hạng:	Push (Mi, S1);
	Dấu "(":	Push (Mi, S2);
	Toán tử:
		While UT(Top(S2) > UT(Mi)	Do
		Begin
			Pop(s1,b);
			Pop(s2,x);
			Pop(s1,a);
			y:=a x b;
			Push(y, S1);
		End
		Push (Mi, S2);
	Dấu ")":	While Top(S2)<>"("	Do
		Begin	Pop(s1,b);
			Pop(s2,x);
			Pop(s1,a);
			y:=a x b;
			Push(y, S1);
		End While
		Pop(S2,x)
	End Case
While NOT	Empty(S2)	Do
	Begin	Pop (S1,b);
		Pop (S2, x);
		Pop (S1, a);
		y:=a x b;
		Push(y, S1);
	End
Pop (S1, x)
Output (x);
End.

Minh hoạ cho việc tính trung tố phần giải thuật trên
Giả sử ta cần tính M = 9 + 31 * (7 - (6 + 5)* 4 - 3*2)*2

Đọc được theo M	Mi	Công việc phải làm	S1	S2	Ghi chú
9	9	Đưa 9 vào S1	9
9 +	+	Đưa + vào S2	9	+
9 + 31	31	Đưa 31 vào S1	9,31	+
9 + 31 *	*	Đưa * vào S2	9,31	+, *
9 + 31 * (	(	Đưa ( vào S2	9,31	+,*,(
9 + 31 * (7	7	Đưa 7 vào S1	9,31,7	+,*,(
9 + 31 * (7 -	-	Đưa -vào S2	9,31,7	+,*,(,-
9 + 31 * (7 - (	(	Đưa ( vào S2	9,31,7	+,*,(,-,(
9 + 31 * (7 - (6	6	Đưa 6 vào S1	9,31,7,6	+,*,(,-,(
9 + 31 * (7 - (6 +	+	Đưa + vào S2	9,31,7,6	+,*,(,-,(,+
9 + 31 * (7 - (6 + 5	5	Đưa 5 vào S1	9,31,7,6,5	+,*,(,-,(,+
9 + 31 * (7 - (6 + 5)	)	Lấy 5, 6 ở S1 ra và + ở S2 ra, tính 6+5 đưa kết quả là 11 vào S1, lấy ( ra khỏi S2	9,31,7,11	+,*,(,-
9 + 31 * (7 - (6 + 5)*	*	Đưa * vào S2	9,31,7,11	+,*,(,-,*
9 + 31 * (7 - (6 + 5)* 4	4	Đưa 4 vào S1	9,31,7,11,4	+,*,(,-,*
9 + 31 * (7 - (6 + 5)* 4 -	-	Lấy 4 và 11 ra khỏi S1, lấy * ra khỏi S2, tính 11*4, đưa kết quả 44 vào S1. Đưa dấu - vào tiếp S2	9,31,7,44	+,*,(,-,-	Do dấu * trong S2 ưu tiên cao hơn dấu -
9 + 31 * (7 - (6 + 5)* 4 - 3	3	Đưa 3 vào S1	9,31,7,44,3	+,*,(,-,-
9 + 31 * (7 - (6 + 5)* 4 - 3*	*	Đưa * vào S2	9,31,7,44,3	+,*,(,-,-,*
9 + 31 * (7 - (6 + 5)* 4 - 3*2	2	Đưa 2 vào S1	9,31,7,44,3,2	+,*,(,-,-,*
9 + 31 * (7 - (6 + 5)* 4 - 3*2)	)	1.Lấy 2,3 khỏi S1 và * khỏi S2, thực hiện 3*2 đưa kết quả là 6 vào S1.	9,31,7,44,6	+,*,(,-,-
		2. Lấy 6,44 ra khỏi S1 và - ra khỏi S2, thực hiện 44-6 đưa kết quả là 38 vào S1	9,31,7,38	+,*,(,-
		3. Lấy 38,7 ra khỏi S1 và - ra khỏi S2, thực hiện 7-38 đưa kết quả là -31 vào S1. Lấy để bỏ dấu ( ở S2	9,31,-31	+,*	Lấy đến dấu ( thì dừng
9 + 31 * (7 - (6 + 5)* 4 - 3*2)*	*	Đưa dấu * vào S2	9,31,-31	+,*,*
9 + 31 * (7 - (6 + 5)* 4 - 3*2)*2	2	Đưa 2 vào S1	9,31,-31,2	+,*,*	Hết chuỗi
		Lấy 2 và -31 khỏi S1, lấy * khỏi S2, thực hiện -31*2 đưa kết quả là -62 vào S2	9,31,-62	+,*
		Lấy -62 và 31 ra khỏi S1 và * ra khỏi S2, tính 31+-62 ghi kết quả -31 vào S2	9,-31	+
		Lấy - 31 và 9 khỏi S1 và + khỏi F2 tính 9 + - 31 ghi kết quả là -22 vào S1	-22		Hết thao tác do chuỗi S2 rỗng
		Lấy kết quả - 22 ghi ra màn hình.

Chương trình viết giả mã chuyển từ trung tố sang hậu tố
- Ý tưởng viết thì đúng, nhưng lúc viết thì thiếu.
+ Pop(S,x) trước khi N:= N + x;
+ Sau khi xong thì phải xóa dấu "(" ra khỏi stack

+ Khi Mi là toán tử thì phải kiểm tra stack có rỗng không rồi mới thực hiện

+ Cuối cùng kiểm tra stack, nếu không rỗng thì đẩy ra

Chuyển biểu thức trung tố không dấu ngoặc thành hậu tố
PROC Chuyen
1) S := Ø; N = Ø;
2)

- Xây dựng hàm con xét độ ưu tiên	UT(x)
	CASE x	of
	*,/:	UT=2
	-, + :	UT=1
	END

3) For i :=1 to /M/
	CASE Mi of
	a)Toán hạng:
		N = N + Mi;

	b) Toán tử:
		WHILE (S ≠ Ø) & (UT(Top(S)) ≥ UT(Mi)) DO
			Pop(S, x);
			N = N + x;
			Push(Mi, S)
	End Case
4) Repeat
	Pop(S,x);	N := N + x
Until Empty(S)
5) Output (N)

Admin đã viết:Minh hoạ cho việc tính trung tố phần giải thuật trên
Giả sử ta cần tính M = 9 + 31 * (7 - (6 + 5)* 4 - 3*2)*2

Đọc được theo M	Mi	Công việc phải làm	S1	S2	Ghi chú
9	9	Đưa 9 vào S1	9
9 +	+	Đưa + vào S2	9	+
9 + 31	31	Đưa 31 vào S1	9,31	+
9 + 31 *	*	Đưa * vào S2	9,31	+, *
9 + 31 * (	(	Đưa ( vào S2	9,31	+,*,(
9 + 31 * (7	7	Đưa 7 vào S1	9,31,7	+,*,(
9 + 31 * (7 -	-	Đưa -vào S2	9,31,7	+,*,(,-
9 + 31 * (7 - (	(	Đưa ( vào S2	9,31,7	+,*,(,-,(
9 + 31 * (7 - (6	6	Đưa 6 vào S1	9,31,7,6	+,*,(,-,(
9 + 31 * (7 - (6 +	+	Đưa + vào S2	9,31,7,6	+,*,(,-,(,+
9 + 31 * (7 - (6 + 5	5	Đưa 5 vào S1	9,31,7,6,5	+,*,(,-,(,+
9 + 31 * (7 - (6 + 5)	)	Lấy 5, 6 ở S1 ra và + ở S2 ra, tính 6+5 đưa kết quả là 11 vào S1, lấy ( ra khỏi S2	9,31,7,11	+,*,(,-
9 + 31 * (7 - (6 + 5)*	*	Đưa * vào S2	9,31,7,11	+,*,(,-,*
9 + 31 * (7 - (6 + 5)* 4	4	Đưa 4 vào S1	9,31,7,11,4	+,*,(,-,*
9 + 31 * (7 - (6 + 5)* 4 -	-	Lấy 4 và 11 ra khỏi S1, lấy * ra khỏi S2, tính 11*4, đưa kết quả 44 vào S1. Đưa dấu - vào tiếp S2	9,31,7,44	+,*,(,-,-	Do dấu * trong S2 ưu tiên cao hơn dấu -
9 + 31 * (7 - (6 + 5)* 4 - 3	3	Đưa 3 vào S1	9,31,7,44,3	+,*,(,-,-
9 + 31 * (7 - (6 + 5)* 4 - 3*	*	Đưa * vào S2	9,31,7,44,3	+,*,(,-,-,*
9 + 31 * (7 - (6 + 5)* 4 - 3*2	2	Đưa 2 vào S1	9,31,7,44,3,2	+,*,(,-,-,*
9 + 31 * (7 - (6 + 5)* 4 - 3*2)	)	1.Lấy 2,3 khỏi S1 và * khỏi S2, thực hiện 3*2 đưa kết quả là 6 vào S1.	9,31,7,44,6	+,*,(,-,-
		2. Lấy 6,44 ra khỏi S1 và - ra khỏi S2, thực hiện 44-6 đưa kết quả là 38 vào S1	9,31,7,38	+,*,(,-
		3. Lấy 38,7 ra khỏi S1 và - ra khỏi S2, thực hiện 7-38 đưa kết quả là -31 vào S1. Lấy để bỏ dấu ( ở S2	9,31,-31	+,*	Lấy đến dấu ( thì dừng
9 + 31 * (7 - (6 + 5)* 4 - 3*2)*	*	Đưa dấu * vào S2	9,31,-31	+,*,*
9 + 31 * (7 - (6 + 5)* 4 - 3*2)*2	2	Đưa 2 vào S1	9,31,-31,2	+,*,*	Hết chuỗi
		Lấy 2 và -31 khỏi S1, lấy * khỏi S2, thực hiện -31*2 đưa kết quả là -62 vào S2	9,31,-62	+,*
		Lấy -62 và 31 ra khỏi S1 và * ra khỏi S2, tính 31+-62 ghi kết quả -31 vào S2	9,-31	+
		Lấy - 31 và 9 khỏi S1 và + khỏi F2 tính 9 + - 31 ghi kết quả là -22 vào S1	-22		Hết thao tác do chuỗi S2 rỗng
		Lấy kết quả - 22 ghi ra màn hình.

Anh ơi anh cho em hỏi là nếu khi trình bày bài làm em chỉ sử dụng 1 ngăn xếp S chứ ko chia ra thành 2 ngăn xếp Sh và St thì có đc ko ạ?

Admin: Câu này phải hỏi thầy giáo. Nhưng theo bọn mình được biết thì khi lời giải đúng thì dù Khách viếng thăm dùng 1 ngăn xếp hay n ngăn xếp thì vẫn được điểm. Chỉ có điều là cách giải không tối ưu sẽ không được điểm tối đa thôi. Vì những bài kiểm tra trên lớp dù cách giải gì đi nữa, miễn là đúng, thầy vẫn chấm rất cẩn thận. Khách viếng thăm nên nhớ là ở đây bài được chấm theo giải thuật chứ không phải chấm theo quy cách trình bày.

Admin đã viết:Chuyển biểu thức trung tố không dấu ngoặc thành hậu tố
PROC Chuyen
1) S := Ø; N = Ø;
2)

- Xây dựng hàm con xét độ ưu tiên	UT(x)
	CASE x	of
	*,/:	UT=2
	-, + :	UT=1
	END

3) FOR i :=1 to /M/
	CASE Mi of
	a)Toán hạng:
		N = N + Mi;

	b) Toán tử:
		WHILE (S ≠ Ø) & (UT(Top(S)) ≥ UT(Mi)) DO
			Pop(S, x);
			N = N + x;
			Push(Mi, S)
	End Case
4) Repeat
	Pop(S,x);	N := N + x
Until Empty(S)
5) Output (N)

Theo mình nghĩ phần 3)b) Khi Mi là toán tử phải đưa hết các toán tử có độ ưu tiên cao hơn hoặc bằng Mi trong stack ra sau đó đưa toán tử Mi vào stack tức là việc Push(Mi,S) là công việc thực hiện có vai trò bình đẳng với vòng WHILE và nó đứng ngoài vòng WHILE thế này:
b) Toán tử:
          b1)WHILE (S ≠ Ø) & (UT(Top(S)) ≥ UT(Mi)) DO
                    Pop(S, x);
                    N = N + x;
          b2)Push(Mi, S)

Ban QT: Uh, Bạn nói đúng rồi đấy.

Hic phần:
Minh hoạ cho việc tính trung tố phần giải thuật trên
Giả sử ta cần tính M = 9 + 31 * (7 - (6 + 5)* 4 - 3*2)*2 = -2657 ( tính bằng máy tính ) >>>>> SAI ... Các anh chị xem lại giải thuật dùm em với nhé

ngoannhi đã viết:Hic phần:
Minh hoạ cho việc tính trung tố phần giải thuật trên
Giả sử ta cần tính M = 9 + 31 * (7 - (6 + 5)* 4 - 3*2)*2 = -2657 ( tính bằng máy tính ) >>>>> SAI ... Các anh chị xem lại giải thuật dùm em với nhé

Bạn ơi Admin trình bày là giải thuật dùng cho trung tố không dấu ngoặc, còn bài của bạn là trung tố không đầy đủ dấu ngoặc, thuật toán có khác một chút, bạn lưu ý phần mở và đóng dấu ngoặc ấy. Thời gian gấp quá ko tiện gõ lên diễn đàn, chúc bạn thi tốt.OK

Admin đã viết:

[You must be registered and logged in to see this image.] Chương trình viết giả mã chuyển từ trung tố sang hậu tố

Đề bài: Cho M = Biểu thức trung tố. Viết biểu thức dạng hậu tố N, N=M.
Ý tưởng:
- Duyệt từng phần tử trong M cho đến hết.
- Nếu Mi là toán hạng: nối thêm vào N.
- 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à đưa phần lấy đó nối thêm vào N 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ử xét các trường hợp:

• 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à nối thêm vào N.
  
• Đưa toán tử hiện tại vào stack
  

Khi duyệt xong chuỗi M, nếu Stack còn chưa rỗng thì lấy lần lượt ra cho đến Stack.
Giải thuật:

- Khởi tạo Stack rỗng: S.

- Xây dựng hàm con xét độ ưu tiên	UT(x)
	CASE x	of
	*,/,%:	UT=2
	-, + :	UT=1
	ELSE:	UT=0
	END

- Bắt đầu chương trình

FOR i:=1 to /M/
	CASE Mi of
	Toán hạng:
		N = N + Mi;
	(:
		Push(Mi, S);
	):
		WHILE x<> "("
		N=N +x;
		Pop(S,x);
		End WHILE
	Toán tử:
		IF UT(Top(S)>=UT(Mi) THEN
			Pop(S,x);
			N=N + x;
		ELSE	Push(Mi,S)
	End Case
Repeat
	Pop(S,x);
	IF x <>"("	N:=N + x
Until Empty(S)
Output (N)

anh chi k23 ơi.Anh chị nào có giải thuật chuẩn nhất up lên giúp em với. Em theo dõi trong giáo trình của thầy Đào Thanh Tĩnh và một số vở của các anh chị ghi lại nhưng có nhiều cách viết quá. Và ở bài này của anh admin em thấy nhiều chỗ thiếu dấu ';' kết thúc lệnh, chỗ "endcase" chỗ thì chỉ "end" không. hix.Mỗi ngôn ngữ có một cách viết khác nhau. Mong anh chị viết chuẩn hộ em để em có một đề cương ôn thi tốt. Cảm ơn anh chị nhiều.
Mà ở phần giải thuật này em hiểu ý tưởng của anh nhưng chưa hiểu lắm về các bước của giải thuật. Mong anh admin giải thích giúp em hiểu sâu hơn về vấn đề.

anh Đức Anh ơi! giúp em giải thuật chuyển từ dạng trung tố sang dạng hậu tố có đầy đủ dấu ngoặc với, ở thuật toán này em thấy mọi người viết khác nhau quá.
à. khi mình thực hiện thuật toán bằng tay, theo ý tưởng của giải thuật thì khi gặp dấu "(" thì ta đưa nó vào S, nhưng trong một số bài giải em xem của thầy và một số người k23 làm thì khi gặp "(" mọi người bỏ qua không đưa vào S. Vậy có được không ạ ?

Gửi Trang!
Với bài toán chuyển M từ dạng trung tố sang dạng hậu tố (M có đầy đủ dấu ngoặc)
Có hai vấn đề sau đây:
1. Vì M là biểu thức đầy đủ dấu ngoặc nên nếu gặp dấu ngoặc đóng thì đương nhiên trước đó đã phải có dấu ngoặc mở.
2. Với phép toán có dấu ngoặc, thì đương nhiên phải thực hiện phép toán trong ngoặc trước.
Vậy: Nếu gặp toán hạng thì đưa toán hạng vào N.
Nếu gặp toán tử thì đưa toán tử vào S
Khi gặp dấu ngoặc mở thì không cần đưa vào S. mà đọc tiếp...
Nếu gặp dấu ngoặc đóng thì lấy toán tử ra khỏi S và đưa toán tử đó vào N.

Anh Đức anh: Trong phần Toán tử em thấy hình như anh thiếu xét tính ưu tiên của các toán tử trong S thì phải? Anh xem lại giúp em nhé. Thanks anh!

Em ạ!
Khi xét đến ưu tiên các toán tử trong S, thì chỉ xét với các biểu thức M "không có dấu ngoặc" hoặc "không đầy đủ dấu ngoặc" thôi nhé. Em phải cố gắng đọc thật kỹ lý thuyết và làm thật nhiều ví dụ bằng tay để dễ hiểu hơn nhé!