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.

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)

Code:

          Đây là thụt một tab
                    Đây là thụt 2 tab

Anh Đức đã viết:[You must be registered and logged in to see this image.]