[Hướng Dẫn]Giải Quyết Triệt để Vấn đề Trung Và Hậu Tố

Trang chủ » Chuyển Biểu Thức Trung Tố Sang Hậu To C » [Hướng Dẫn]Giải Quyết Triệt để Vấn đề Trung Và Hậu Tố

Có thể bạn quan tâm

[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;
ELSEPush(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)

Từ khóa » Chuyển Biểu Thức Trung Tố Sang Hậu To C