Từ 1 tới 6 trên tổng số 6 kết quả

Đề tài: Cách biểu diễn một biểu thức dưới dạng cây.

  1. #1
    Ngày gia nhập
    09 2008
    Bài viết
    1

    Mặc định Cách biểu diễn một biểu thức dưới dạng cây.

    e chào mí anh chị pro ạ...
    e mới là gà của C,hiện giờ thầy giáo giao cho e một đồ án liên quan đến kí pháp nghịch đảo Ba Lan...
    trong đó có phần "cách biểu diễn một biểu thức dưới dạng cây", e search thì chỉ thấy người ta đã biểu diễn sẵn xong rồi tính giá trị biểu thức dựa trên cây đó chứ hông đưa ra cách chuyển "..."
    huhu...e hông bít làm sao hết, nhờ mí a chị help e với...thanks nhìu ạ!

    Bạn lưu ý cách đặt tiêu đề nhé !!! -- thân --
    Đã được chỉnh sửa lần cuối bởi zkday2686 : 12-10-2008 lúc 03:08 PM.

  2. #2
    Ngày gia nhập
    09 2007
    Bài viết
    724

    Bạn xem cái topic này xem có giúp gì được cho bạn không ???
    http://forums.congdongcviet.com/showthread.php?t=5415

    --- Thân ----

  3. #3
    Ngày gia nhập
    11 2008
    Bài viết
    10

    Mình xin đề xuất giải thuật thế này.
    Biểu thức ban đầu của biểu thức được gọi là biểu diễn trung tố. Đầu tiên bạn cần đưa về hậu tố (Kí pháp Ba Lan).
    Sau đây là thuật toán đưa về kí pháp Ba Lan từ biểu thức trung tố.
    Khởi tạo Q: stack rỗng, S là xâu trung tự ban đầu, T="" là xâu hậu tố.
    Để bài toán được trình bày dễ hiểu hơn, ta coi S đã được chuẩn hóa (Không chứa dấu trống hoặc kí tự đặc biệt, biểu thức được tối ưu hóa, vd không có trường hợp 2 - +2 mà phải là 2-2...).

    Duyệt từng hạng tử của S từ trái qua phải
    - Nếu gặp dấu ( => push vào Q
    - Nếu gặp một toán hạng hoặc hằng số, thêm vào xâu T
    - Nếu gặp dấu ) => pop từ Q và thêm vào xâu T tới khi nào pop được dấu ( chú ý không thêm dấu ( vào T nhé.
    - Nếu gặp một toán tử, thì chừng nào toán tử ở đỉnh của Q có độ ưu tiên lớn hơn toán tử đang xét thì pop toán tử đó ra và thêm vào T.
    Duyệt hết S, lần lượt pop các toán tử còn lại trong Q và thêm vào T, ta đã được biểu thức hậu tố.
    VD. 2+3*4-5/6
    thực hiện từng bước
    Ban đầu T=""; Q=rỗng
    gặp kí tự '2':
    - T = 2;
    - Q = rổng
    gặp '+'
    - T = 2
    - Q = +
    gặp 3
    - T = 2 3
    - Q = +
    gặp *
    - T = 2 3
    - Q = + * (độ ưu tiên của + nhỏ hơn * nên không bị pop ra)
    gặp 4
    - T = 2 3 4
    - Q = + *
    gặp -
    - T = 2 3 4 *
    - Q = + - (do * ưu tiên hơn - nên pop lấy * và thêm vào T)
    gặp 5
    - T = 2 3 4 * 5
    - Q = + -
    gặp /
    - T = 2 3 4 * 5
    - Q = + - /
    gặp 6
    - T = 2 3 4 * 5 6
    - Q = + - /
    hết xâu, pop các phần từ của Q vào cho T.
    - T = 2 3 4 * 5 6 / - +

    Đến đây bạn có thể tính biểu thức mà không cần dùng cây rồi.
    Tính như sau
    Duyệt từng hạng tử của T
    Nếu gặp toán hạng hoặc hằng số, push vào Q (Trước khi push, Q đã bị rỗng)
    Nếu gặp toán tử, pop số toán hạng hoặc hằng số ứng với toán tử đó ra (toán tử 2 ngôi thì pop 2 hạng tử), tính kết quả và lại push vào Q.
    Khi duyệt hết T, trong Q chỉ còn lại kết quả của biểu thức.
    Vẫn ví dụ trên: T = 2 3 4 * 5 6 / - +
    tình trạng của Q qua từng bước như sau.
    2
    2 3
    2 3 4
    2 12 (duyệt tới *, pop ra 3, 4 và tính 3*4)
    2 12 5
    2 12 5 6
    2 12 0.8 (duyệt tới /, pop ra 5, 6 và tính 5/6= 0.8)
    2 10.2 (duyệt tới -, pop ra 12, 0.8 và tính 12-0.8)
    12.2 (duyệt tới +, pop ra 2, 10.2 và tính 2+10.2)
    Kết thúc, pop ra 12.2 là kết quả biểu thức.

  4. #4
    Ngày gia nhập
    11 2008
    Bài viết
    5

    Đây là loại bài toán rất hay, thuật toán của nó dùng nhiều trong việc xây dựng các biểu thức số học, chương trình dịch, biểu thức chính quy, mình thấy dùng C/C++ cho loại bài này là hơi phức tạp (về cú pháp ) , có thể dùng Java và C# sẽ đơn giản hơn nhiều.

  5. #5
    Ngày gia nhập
    11 2008
    Bài viết
    10

    Sau đây mình xin nêu cách chuyển thành cây biểu thức từ xâu hậu tố.
    Cây biểu thức là cây nhị phân, có các lá là toán hạng hoặc hằng số, các nút không phải lá là các toán tử. (lưu ý các toán tử sin, cos chỉ cho phép số lượng nút con là 1 - toán tử 1 ngôi)
    ban đầu gốc của cây, mỗi núp P khởi tạo ban đầu có P.left = null và P.right = null;
    Stack Q = rỗng.
    Duyệt từ cuối xâu hậu tố T về đầu.
    Gặp hạng tử x(có thể là toán tử hoặc toán hạng):
    - tạo nút x.
    - Nếu Q khác rỗng: gọi s là phần tử trên đỉnh của Q, set x là nút con của s (ưu tiên s.right). Sau khi s được thêm nút con nếu đã đủ cả 2 nút con (với toán tử 2 ngôi hoặc đủ 1 nút con với toán tử 1 ngôi) thì Q.pop();
    - nếu x là toán tử thì push nút x vào Q.

    Khi duyệt hết xâu T, Q sẽ thành stack rỗng và đã xây dựng xong cây với gốc là toán tử đầu tiên được push vào Q.
    Muốn tính giá trị biểu thức ta chỉ việc gọi vòng đệ quy.

    calc(Node p) {
    if p là toán hạng hoặc hằng số thì return giá trị p;
    else return( calc(node.left), toán tử, calc(node.right) ); // nút p là toán tử, được tính bằng việc thực hiện toán tử đó với các ngôi tương ứng là nút con của nó.
    }

  6. #6
    Ngày gia nhập
    11 2008
    Bài viết
    10

    Mặc định Cách biểu diễn một biểu thức dưới dạng cây.

    Vì phải viết dài nên xin phép cho mình trình bày thành nhiều phần


    Trở lại ví dụ ở bài viết trước.
    T = 2 3 4 * 5 6 / - +
    cây được xây dựng qua từng bước như sau
    ..... (+)

    .....................(+)
    ........................\
    ........................(-)


    .....................(+)
    ........................\
    ........................(-)
    ...........................\
    ............................(/)


    .....................(+)
    ........................\
    ........................(-)
    ...........................\
    ............................(/)
    ..............................\
    ...............................(6)

    .....................(+)
    ........................\
    ........................(-)
    ...........................\
    ............................(/)
    .........................../...\
    ........................(5)...(6)

    ....................(+)
    ........................\
    ........................(-)
    ......................./...\
    ....................(*)....(/)
    .........................../....\
    .........................(5)....(6)

    .....................(+)
    .........................\
    ........................(-)
    ......................./.....\
    ...................(*).......(/)
    ......................\......./..\
    ......................(4)..(5)..(6)


    .....................(+)
    .........................\
    ........................(-)
    ......................./.....\
    ...................(*).......(/)
    ................../...\......./..\
    ................(3)...(4)..(5)..(6)

    .....................(+)
    ..................../....\
    ..................(2)...(-)
    ......................./.....\
    ...................(*).......(/)
    ................../...\......./..\
    ................(3)...(4)..(5)..(6)

    Việc tính toán và đưa ngược về trung tố bây giờ quá đơn giản phải không.
    Đã được chỉnh sửa lần cuối bởi linkinsteps : 05-11-2008 lúc 01:30 AM.

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn