Đề bài trang 18, sách Cấu trúc dữ liệu và giải thuật của thầy Đào Thanh T~:
Bài 1. Cho biểu thức:

Code:

 M = (A + B)*(C/(U+V))

dưới dạng hậu tố. Dùng bảng để minh hoạ hình ảnh của ngăn xếp được sử dụng để tính giá trị của biểu thức hậu tố nhận được nếu đặt A = 20, B = 12, C = 14 , U = 4, V = 3.

Bài 2. Dùng bảng để minh hoạ hình ảnh của ngăn xếp được sử dụng, để tính giá trị của biểu thức

Code:

((20+12)*(14/(4+3)))

Bài 3. Viết thủ tục dạng giả mã chuyển một biểu thức dạng trung tố về dạng hậu tố, sử dụng ngăn xếp hỗ trợ.

Bài 4. Dùng bảng để minh hoạ hình ảnh của ngăn xếp được sử dụng để chuyển một biểu thức dạng trung tố đầy đủ dấu ngoặc về dạng hậu tố.

Bài 5. Trong một văn bản (chẳng hạn một chương trình nguồn viết trên Pascal, các ký hiệu và dấu ngoặc [({})] phải khớp từng cặp và lồng vào nhau một cách đúng đắn. Viết thủ tục giả mã để kiểm tra tính đúng đắn của dấu ngoặc trong một xâu ký tự, sử dụng ngăn xếp hỗ trợ.

Giải bài 1.
Biểu thức M được viết dưới dạng hậu tố như sau:

Code:

A  B+  C U V+    / *

Thay các giá trị sẽ được:

Code:

20 12+  14 4 3+    / *

Ý TƯỞNG
Duyệt cho đến hết M
a. Đọc một phần tử x
b. Nếu x là biểu thức thì nạp vào stack
c. Nếu x là toán tử thì lấy 2 phần tử trên đỉnh stack và tính, sau đó đưa kết quả vào stack.
Lấy giá trị trong stack và viết ra màn hình.

GIẢI THUẬT
Khởi tạo stack rỗng
REPEAT
a. Đọc phần tử x từ biểu thức M
b. IF x là toán tử Then
i. Pop (S, a)
ii. Pop (S, b)
iii. w:= b x a
iv. Push (w, S)
Else Push(x, S)
UNTIL Kết thúc biểu thức M;
Pop (S, x)
Write (x)

Quá trình đọc và làm việc trong stack được minh hoạ như sau:

Đã đọc theo M	x	Lệnh	Công việc	Stack
20	20	push (x,S)	Đưa 20 vào S	20
20 12	12	push (x,S)	Đưa 12 vào S	12
20 12		Pop(S, a)	Lấy 12 đưa vào a
		Pop(S,b)	Lấy 20 đưa vào b
		w=b x a	Cộng 12 với 20
		Push (w, S)	Đưa kết quả vào S	22
20 12 14	14	push (x,S)	Đưa 14 vào S	22,14
20 12 14 4	4	push (x,S)	Đưa 4 vào S	22, 14, 4
20 12 14 4 3	3	push (x,S)	Đưa 3 vào S	22, 14, 4, 3
20 12 14 4 3 /		Pop(S, a)	Lấy 3 đưa vào a
		Pop(S, b)	Lấy 4 đưa vào b
		w=b x a	Cộng 3 với 4
		Push (w, S)	Đưa kết quả vào S	22, 14, 7
	/	Pop(S, a)	Lấy 7 ra
		Pop(S, b)	Lấy 14 ra
		w=b x a	Lấy 14/7
		Push (w, S)	Đưa kết quả vào S	22, 2
	*	Pop(S, a)	Lấy 2 ra
		Pop(S, b)	Lấy 22 ra
		w=b x a	Lấy 22 * 2
		Push (w, S)	Đưa kết quả vào S	44

Admin đã viết:Đề bài trang 18, sách Cấu trúc dữ liệu và giải thuật
Bài 2. Dùng bảng để minh hoạ hình ảnh của ngăn xếp được sử dụng, để tính giá trị của biểu thức

Code:

M=((20  12)*(14/(4  3)))

Lời giải:
Ý tưởng:
- Duyệt cho đến hết M
- Nếu Mi là ngoặc mở, bỏ qua
- Nếu Mi là toán tử hoặc toán hạng: Đưa vào stack
- Nếu là dấu đóng ngoặc thì lấy ra 3 phần tử trên đỉnh Stack, tính xong đưa vào stack.
- Lấy giá trị trong stack đưa ra màn hình.
Giải thuật để tính giá trị biểu thức trung tố:
- Khởi tạo Stack rỗng.

For i:=1 to /M/
	Case Mi of
	toán tử, toán hạng:
		Push(Mi, S)
	Dấu ")":
		Pop(S,c);
		Pop(S,b);
		Pop(S,a)
		x:=a b c; Push(x,S);

Pop(S,x);
Output (x)

Quá trình đọc và làm việc được minh hoạ theo bảng:
M=((20 +12)*(14/(4 +3)))

Đọc được theo M	Mi	Công việc	Stack
(	(	Bỏ qua
((	(	Bỏ qua
((20	20	Đưa 20 vào S	20
((20+		Đưa vào + S	20, +
((20 + 12	12	Đưa 12 vào S	20, +,12
((20 +12)	)	Lấy 12, + , 20 ra, tính 20 +12 đưa kết quả là 32 vào S	32
((20 + 12)*	*	Đưa * và S	32, *
((20 +12)*(	(	Bỏ qua	32, *
((20 +12)*(14	14	Đưa 14 vào S	32, *, 14
((20 +12)*(14/	/	Đưa / vào S	32,*,14,/
((20 +12)*(14/(	(	Bỏ qua	32,*,14,/
((20 +12)*(14/(4	4	Đưa 4 vào S	32,*,14,/,4
((20 +12)*(14/(4+		Đưa +vào S	32,*,14,/,4,+
((20 +12)*(14/(4 +3	3	Đưa 3 vào S	32,*,14,/,4, +,3
((20 +12)*(14/(4 +3)	)	Lấy 3, + , 4 ra, tính toán 4 +3 đưa kết quả là 7 vào S	32,*,14,/,7
((20 +12)*(14/(4 +3))	)	Lấy 7, /, 14 ra, tính 14/7 đưa kết quả là 2 vào S	32,*,2
((20 +12)*(14/(4 +3)))	)	Lấy 2, *, 32 ra tính 32 * 2, đưa kết quả là 64 vào S Sau đó đưa kết quả chính là số 64 ra màn hình	64

Bài 5. Trong một văn bản (chẳng hạn một chương trình nguồn viết trên
Pascal, các ký hiệu và dấu ngoặc [({})] phải khớp từng cặp và lồng vào
nhau một cách đúng đắn. Viết thủ tục giả mã để kiểm tra tính đúng đắn
của dấu ngoặc trong một xâu ký tự, sử dụng ngăn xếp hỗ trợ.
Ý tưởng:
- Duyệt cho đến hết M
- Đọc một phần tử Mi để xử lý
- Nếu là các dấu mở ngoặc đưa vào Stack.
- Nếu là dấu đóng ngoặc thì lấy phần tử đầu tiên trên đỉnh ra kiểm tra xem có cùng cặp không. Nếu không đúng, thông báo sai và thoát khỏi vòng duyệt.
- Các trường hợp khác của Mi, không làm gì cả.
Kết thúc duyệt, S không rỗng thì thông báo thiếu dấu ngoặc đóng. Ngược lại thông báo OK.

Giải thuật:
- Khởi tạo Stack S rỗng.
- Tạo lập hàm KT 2 phần tử dấu ngoặc, xác định đúng hoặc sai.
KTL:=0 là không lỗi, KTL:=1 là có lỗi (Có thể đặt lỗi là các số khác để báo lỗi chi tiết)

Function KTL(Dau1, Dau2);
	Case Dau1 of
	(:	IF (Dau2=")" then KTL:=0;
		ELSE KTL:=1
	[:	IF (Dau2="]" then KTL:=0;
		ELSE KTL:=1
	{:	IF (Dau2="}" then KTL:=0;
		ELSE KTL:=1
	END
END Function

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

For i:=1 to /M/
	Case Mi of
	(, [, {:
		Push (S, Mi);
	),],}:
		IF Empty(S) then
		Output "Lỗi thiếu dấu ngoặc mở trước vị trí " i
		ELSE
		Pop(S,x);
		IF (KTL(x,Mi)<>0 Then
		Output "Dấu ngoặc không phù hợp"
		End IF
	End Case
IF NOT Empty(S)	then
	Output "Lỗi thiếu dấu	ngoặc đóng"
ELSE	Output"OK".

END.

Bài 1 (trang 18).biểu thức hậu tố là : AB+CUV/* mới đúng chứ anh?
anh coi lai nhé.

Anh ơi!!anh có thể giải bài 3,4,5 được khộng ạ!

Ban QT:
Lời giải tương tự.

Admin đã viết:Bài 5. Trong một văn bản (chẳng hạn một chương trình nguồn viết trên
Pascal, các ký hiệu và dấu ngoặc [({})] phải khớp từng cặp và lồng vào
nhau một cách đúng đắn. Viết thủ tục giả mã để kiểm tra tính đúng đắn
của dấu ngoặc trong một xâu ký tự, sử dụng ngăn xếp hỗ trợ.
Ý tưởng:
- Duyệt cho đến hết M
- Đọc một phần tử Mi để xử lý
- Nếu là các dấu mở ngoặc đưa vào Stack.
- Nếu là dấu đóng ngoặc thì lấy phần tử đầu tiên trên đỉnh ra kiểm tra xem có cùng cặp không. Nếu không đúng, thông báo sai và thoát khỏi vòng duyệt.
- Các trường hợp khác của Mi, không làm gì cả.
Kết thúc duyệt, S không rỗng thì thông báo thiếu dấu ngoặc đóng. Ngược lại thông báo OK.

Giải thuật:
- Khởi tạo Stack S rỗng.
- Tạo lập hàm KT 2 phần tử dấu ngoặc, xác định đúng hoặc sai.
KTL:=0 là không lỗi, KTL:=1 là có lỗi (Có thể đặt lỗi là các số khác để báo lỗi chi tiết)

Function KTL(Dau1, Dau2);
	Case Dau1 of
	(:	IF (Dau2=")" THEN KTL:=0;
		ELSE KTL:=1
	[:	IF (Dau2="]" THEN KTL:=0;
		ELSE KTL:=1
	{:	IF (Dau2="}" THEN KTL:=0;
		ELSE KTL:=1
	END
END Function

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

FOR i:=1 to /M/
	Case Mi of
	(, [, {:
		Push (S, Mi);
	),],}:
		IF Empty(S) THEN
		Output "Lỗi thiếu dấu ngoặc mở trước vị trí " i
		ELSE
		Pop(S,x);
		IF (KTL(x,Mi)<>0 THEN
		Output "Dấu ngoặc không phù hợp"
		End IF
	End Case
IF NOT Empty(S)	THEN
	Output "Lỗi thiếu dấu	ngoặc đóng"
ELSE	Output"OK".

END.

Em nghĩ bài này còn thiếu. Nếu khi gặp dấu đóng ngoặc mà ngăn xếp rỗng không còn dấu mở ngoặc thì sao ạ.