Ky phap Ba Lan: chuyen bieu thuc dang trung to thanh hau to

[nccnm]

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ỉ

[mapleleaf]

Cái này hình như liên quan đến stack hay queue gi đấy. Bạn search thử đi.

Hồi đó học cái này lớt phớt lắm nên chẳng nhớ đọc được ở đâu.

[jiSh@n]

Bạn vào http://spkt.net/pn/html/index.php?na...viewtopic&t=49 xem mã nguồn bằng C, cái này chỉ đơn giản dùng stack.

[songok]

Bai nay con tuy thuoc vao nguoi su dung nhap vao nhu the nao nua: Neu nguoi su dung nhap day du cac dau ngoac vi du ( 8*(7+3)) thi coi nhu xong , ban chi can dung cau truc cay nhu sau :

typedef struct node {
char key;
node* left;
node* right;
};
key de chi so hay cac phep toan nhu : *,/,+,- con node* left , node* right de chi den nhanh con cua cay

Bai nay tui da lam lau roi, nhung khong dung cay, ma dung mang va su dung stack de lam, bai nay tui lam cho nguoi su dung nhap vao thoai mai, nghia la khong can bo ngoac gi het, chuong trinh se tu bo ngoac. Tui se gui ct nay cho ban

[nccnm]

Cám ơn các ban, đặc biệt là bạn songok, mình chờ mail của bạn he`.
Mình đã tìm ra thuật toán của bài này rồi, đúng là không cần phải dùng cây , duyệt diếc gì hết, chỉ cần dùng stack.

[dongthao]

to nccnm: Bài này nếu bạn dùng stack hay queue thì khá đơn giản. Nhưng mình nghĩ bạn nên dùng cấu trúc cây thì sẽ hiểu rõ hoạt động của cây hơn, cụ thể là các cách duyệt cây: preorder, inoder, postorder. Nếu bạn có quan tâm đến cây thì mình sẽ nói sau. Còn nếu bạn dùng stack thì mình nghĩ không có gì để bàn, đúng không?

[songok]

Dung cau truc cay hay stack hay queue gi cung vay thoi, may ham duyet sau, rong gi do viet de quy co vai dong thoi ( neu thich thi ban cho the khu de quy cung duoc) . Rac roi o cho : neu co du dau ( thi moi dung chu neu nguoi su dung go thieu hay go sai, hay lam bieng go dau ngoac ghi cac giai thuat tren cung khong xong.

Xin loi ban nccmn nhe : minh quen mat di gui cho ban chuong trinh tinh gia tri bieu thuc cua minh, ma ban cho minh mail duoc hong, minh khong biet attach file cho nao het. Minh se gui lien cho ban

chuc may man

[bichduyen_nt]

Duyên cũng có làm bài này hồi học kỳ trước, xài STACK , làm cũng khá hoàn chỉnh, có luôn phần kiểm tra nhập biểu thức vô, bạn muốn tham khảo không? PM địa chỉ mail của bạn cho D đi, D sẽ gởi bài tập của D qua cho bạn

[nccnm]

hi địa chỉ mail mình là : nccnm@yahoo.com , nếu các bạn gửi mình sẽ cảm ơn lắm lắm...
Dĩ nhiên là nếu biểu thức nhập sai thì thuật toán đó làm sao cho kết quả đúng.
Thực ra nếu ai học môn chương trình dịch rồi thì bài toán này có thể giải theo cách:
+đầu tiên là phân tích từ vựng xem cái nào là toán hạng, cái nào là toán tử
+sau đó phân tích cú pháp ta sẽ được cái cây trên

Lý thuyết thì là thế nhưng do mấy đứa bạn "xấu xa" toàn rủ mình bỏ học đi ténh bi a nên mình chỉ biết đến thế mà thời gian nộp bài cũng sắp hết.

to dongthao: cám ơn bạn, thật ra các cách duyệt cây thì mình học từ lâu rồi, vấn đề ở chỗ này là làm sau dựng được cái cây đó.
to bichduyen: bạn gửi cho mình nhé , mình cũng chưa rõ cách bạn kiểm tra biểu thức thế nào.

[jiSh@n]

Bạn cứ xem chương trình của mình ở địa chỉ trên, chương trình có khả năng kiểm tra biểu thức, có thể tự động sửa một số lỗi nhỏ và có hỗ trợ nhập giá trị của biến bên trong biểu thức.