Mọi người ơi đã ai làm cái này chưa giúp hộ cái: chuyển biểu thức từ dạng trung tố sang hậu tố.
Cái này gọi là ký pháp Ba Lan chắc nhiều người biết.
Ví dụ như sau:
Biểu thức trung tố: (3+5)*(3-6)
Chuyển sang biểu thức hậu tố: 35+36-*
Hai biểu thức trên chỉ là kết quả của việc duyệt cây sau:
__________*_________
| |
____ +____ ____ -____
| | | |
3 5 3 6
Biểu thức trung tố là kết quả của việc duyệt theo thứ tự giữa.
Duyệt cây theo thứ tự giữa (inorder traversal):
-duyệt cây con trái theo thứ tự giữa
-thăm gốc
-duyệt cây con phải theo thứ tự giữa
Biểu thức hậu tố là kết quả của việc duyệt theo thứ tự sau (postorder traversal):
-duyệt cây con trái theo thứ tự sau
-duyệt cây con phải theo thứ tự sau
-thăm gốc
(ghi chú: phép xử lý các nút (node) trên cây được gọi là phép thăm (visit) nút, một cách hệ thống, sao cho mỗi nút chỉ được thăm một lần , gọi là phép duyệt nút.)
Vấn đề bây giờ là làm thế nào từ biểu thức trung tố mà xây dựng được cái cây kia, hic...hoặc làm cách khác, miễn là đúng.
Ai giúp được cám ơn lắm lắm....
Hình như hồi trước trong phần dowload của của diendantinhoc.net có bài viết về ký pháp nghịch đảo Ba Lan nhưng giờ không vào được. Nếu ai có làm ơn gửi vào nccnm@yahoo.com. Xin cảm ơn
ức thật sao cái cây của mình không hiển thị đúng nhỉ
Bookmarks