Khỏe Đẹp Bài tập

Bài tập chuyển từ trung to sang hậu to

Các biểu thức đại số được biểu diễn dưới dạng trung tố [Infix]. Tuy nhiên, để máy tính tính được giá trị của một biểu thức thì cần biểu diễn các biểu thức đại số từ trung tố sang một dạng khác là tiền tố hoặc hậu tố. Bài viết trình bày về cách chuyển từ biểu thức trung tố [Infix] sang hậu tố [Postfix] và tính toán biểu thức hậu tố bằng kỹ thuật Stack.

Postfix là gì?

Biểu thức hậu tố [Postfix] là thuật toán được biểu diễn bằng cách đặt các toán tử ra sau các toán hạng.

Một vài ví dụ minh hoạ:

Infix	Postfix
A / B – C * D	A B / C D * +
A / [ B – C * D]	A B C D * - /
A / [B – C] * D	A B C - / D *

Thuật toán chuyển từ trung tố sang hậu tố

Khởi tạo Stack rỗng.
Khởi tạo 2 chuỗi x và token; i, j lần lượt là index của Infix và Postfix.
Duyệt vòng lặp for từ i = 1 cho đến cuối chuỗi Infix:
- Nếu Infix[i] là toán hạng thì đưa vào Postfix.
- Nếu Infix[i] là toán tử thì Push vào ngăn xếp S.
- Nếu Infix[i] là “]” thì Pop vào ngăn xếp S [lấy giá trị trên đỉnh của S] sau đó đưa vào Postfix.

Output: Postfix là biểu thức hậu tố.

Tính giá trị biểu thức hậu tố

Duyệt biểu thức dạng chuỗi từ trái sang phải:

Dùng hàm isdigit để kiểm tra:

Nếu là toán hạng thì dùng Push[] đưa vào ngăn xếp S.
Nếu là toán tử thì Pop[] 2 toán hạng trong ngăn xếp S ra, sau đó tính toán giá trị của chúng dựa vào toán tử này, sau đó Push[] lại vào S.
Thực hiện cho đến khi gặp kí tự \0 kết thúc chuỗi.
Kết quả của biểu thức chính là phần tử còn lại cuối cùng trong ngăn xếp S.

Code demo

Xét độ ưu tiên của các toán tử

int precedence[char x] { if [x == '['] return 0; if [x == '+' || x == '-'] return 1 ; if [x == '*' || x == '/' || x == '%'] return 2; return 3; }

Chuyển từ trung tố sang hậu tố

void infixtoPostfix[char infix[], char postfix[]] { Stack S; char x, token; int i = 0, j = 0; // i-index of infix,j-index of postfix init[&S]; for [i = 0; infix[i] != '\0'; i++] { token = infix[i]; if [isalnum[token]] postfix[j++] = token; else if [token == '['] Push[&S, '[']; else if [token == ']'] while [[x = Pop[&S]] != '['] postfix[j++] = x; else { while [precedence[token] =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]

Được sửa bởi Admin ngày Sun May 15, 2011 11:35 pm; sửa lần 1. [Reason for editing : Sửa lại cho đúng]

5
Giải thuật tính toán một biểu thức trung tố Sun May 15, 2011 4:48 pm

Bài gửi : 785
Điểm : 14376
Được cảm ơn : 10442
Ngày gia nhập : 11/05/2011

Giải thuật tính toán một biểu thức trung tố

Để 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.

6
Re: [Hướng dẫn]Giải quyết triệt để vấn đề trung và hậu tố Sun May 15, 2011 5:32 pm

Bài gửi : 785
Điểm : 14376
Được cảm ơn : 10442
Ngày gia nhập : 11/05/2011

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

7
Minh hoạ cho việc tính trung tố Sun May 15, 2011 6:38 pm

Bài gửi : 785
Điểm : 14376
Được cảm ơn : 10442
Ngày gia nhập : 11/05/2011

Minh hoạ cho việc tính trung tố phần giải thuật trênGiả 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 - 32]	*	Đưa dấu * vào S2	9,31,-31	+,,
9 + 31 * [7 - [6 + 5]* 4 - 32]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.

8
Re: [Hướng dẫn]Giải quyết triệt để vấn đề trung và hậu tố Sun May 15, 2011 10:46 pm

Bài gửi : 104
Điểm : 1674
Được cảm ơn : 382
Ngày gia nhập : 15/05/2011

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

9
[Lời giải]Chuyển biểu thức trung tố không dấu ngoặc thành hậu tố Sat Jul 16, 2011 5:56 am

Bài gửi : 785
Điểm : 14376
Được cảm ơn : 10442
Ngày gia nhập : 11/05/2011

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

- 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];
Until Empty[S]
5] Output [N]

================

Nếu Khách viếng thăm không đọc được các bài trong Kho bài chuẩn, là do Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.]. Sở dĩ nếu Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.] là vì Khách viếng thăm khai báo thiếu họ, thiếu tên, không dấu hoặc khai báo linh tinh trong trường RN. Đừng xin xỏ uỷ quyền, vì uỷ quyền hoàn toàn tự động cho Thành viên đọc được mọi thứ [không chỉnh bằng tay được], các thành viên khác sẽ không bao giờ được uỷ quyền.

10
Re: [Hướng dẫn]Giải quyết triệt để vấn đề trung và hậu tố Sun Jul 24, 2011 10:50 pm

Bài gửi : 48
Điểm : 152
Được cảm ơn : 55
Ngày gia nhập : 19/06/2011

Admin đã viết:Minh hoạ cho việc tính trung tố phần giải thuật trênGiả 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.

11
[Ý kiến] Thu Jul 28, 2011 9:00 pm

Bài gửi : 20
Điểm : 189
Được cảm ơn : 84
Ngày gia nhập : 15/07/2011

Admin đã viết:Chuyển biểu thức trung tố không dấu ngoặc thành hậu tốPROC Chuyen1] 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];

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.

12
Re: [Hướng dẫn]Giải quyết triệt để vấn đề trung và hậu tố Fri Aug 12, 2011 6:48 pm

Bài gửi : 1
Điểm : 15
Được cảm ơn : 5
Ngày gia nhập : 29/05/2011

Hic phần:Minh hoạ cho việc tính trung tố phần giải thuật trênGiả 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é

13
Re: [Hướng dẫn]Giải quyết triệt để vấn đề trung và hậu tố Fri Aug 12, 2011 7:51 pm

Bài gửi : 77
Điểm : 403
Được cảm ơn : 192
Ngày gia nhập : 11/05/2011

ngoannhi đã viết:Hic phần:Minh hoạ cho việc tính trung tố phần giải thuật trênGiả 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

14
Re: [Hướng dẫn]Giải quyết triệt để vấn đề trung và hậu tố Sun Jun 24, 2012 11:31 am

Bài gửi : 43
Điểm : 271
Được cảm ơn : 82
Ngày gia nhập : 19/11/2011

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 đề.