Đại học Lê Quý Đôn - 236 Hoàng Quốc Việt - Hà Nội

Chia sẻ kiến thức mọi mặt của các lớp cao học CNTT, Học viện Kỹ thuật Quân sự




Chào mừng đã đến với forum khmt.123.st
  • Bạn chưa đăng kí (hoặc chưa đăng nhập) nên quyền lợi của bạn sẽ bị hạn chế. Việc đăng kí làm thành viên hoàn toàn miễn phí, sau khi đăngkí bạn có thể post bài, tham gia thảo luận , nhìn thấy link ở những box hạn chế ... và rất nhiều quyền lợi khác. Thủ tục đăng kí rất nhanh chóng và đơn giản, hãy Đăng kí làm thành viên !
  • Nếu bạn quên mật khẩu, xin nhấn vào đây !
  • Nếu bạn gặp trục trặc trong vấn đề đăng kí hoặc không thể đăng nhập, hãy liên hệ với chúng tôi.




  • Chuyển đến trang : 1, 2  Next

    Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down  Thông điệp [Trang 1 trong tổng số 2 trang]

    Admin


    Quản trị viên
    Quản trị viên
    Đầu tiên nói về cái công cụ cần đã, sau đó sẽ làm tất cả các bài tập dạng này mà thầy ra.

    Để kiểm tra kết quả có chính xác không chỉ chuyển từ trung tố sang hậu tố và ngược lại, bạn có thể dùng một dịch vụ chuyển đổi trực tuyến cũng sẽ thực hiện tính toán giá trị của biểu thức sau khi chuyển đổi.



    Được sửa bởi Admin ngày Mon Jul 02, 2012 3:41 pm; sửa lần 1.


    ================
    Nếu Khách viếng thăm không đọc được các bài trong Kho bài chuẩn, là do Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.]. Sở dĩ nếu Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.] là vì Khách viếng thăm khai báo thiếu họ, thiếu tên, không dấu hoặc khai báo linh tinh trong trường RN. Đừng xin xỏ uỷ quyền, vì uỷ quyền hoàn toàn tự động cho Thành viên đọc được mọi thứ (không chỉnh bằng tay được), các thành viên khác sẽ không bao giờ được uỷ quyền.
    [You must be registered and logged in to see this image.]
    Trang phục may sẵn rẻ nhất Hà Nội ở 148 Vương Thừa Vũ
    ĐT: 043.568.1938

    [You must be registered and logged in to see this link.]
    [You must be registered and logged in to see this link.]
    http://khmt.123.st

    Admin


    Quản trị viên
    Quản trị viên
    Để tránh quên, tạm viết lại một số khái niệm vào đây để các bạn đỡ mất công tra, đồng thời thống nhất được các định nghĩa.
    Các biểu thức đại số được sử dụng hằng ngày đều được biểu diễn dưới dạng trung tố (infix). Cách biểu diễn này rất dễ hiểu với con người vì hầu hết các toán tử ( , -, *, /) đều là toán tử hai ngôi và chúng phân cách giữa hai toán hạng với nhau. Tuy nhiên đối với máy tính, để tính được giá trị của một biểu thức đại số theo dạng này không đơn giản như ta vẫn làm. Để khắc phục điều đó, máy tính cần chuyển cách biểu diễn các biểu thức đại số từ trung tố sang một dạng khác là tiền tố hoặc hậu tố.
    Trong bài này tôi sẽ giới thiệu kĩ thuật để giúp máy tính thực hiện điều này thông qua ngôn ngữ minh họa C#.

    Thế nào là biểu thức tiền tố, trung tố và hậu tố

    Trong đoạn giới thiệu trên có lẽ bạn cũng hình dung được thế nào là biểu thức trung tố, hiểu đơn giản tức là toán tử sẽ được đặt giữa hai toán hạng, dĩ nhiên đây phải là toán tử hai ngôi. Vậy dựa vào vị trí của toán tử, liệu ta có thể biểu diễn biểu thức đại số dưới dạng khác?
    Câu trả lời là được, và như đã nói, ta có ba cách là biểu thức tiền tố (prefix), trung tố (infix) và hậu tố (postfix). Hãy xem một chút giới thiệu về cách biểu diễn biểu thức tiền tố và hậu tố để hiểu rõ hơn về chúng.
    - Prefix: Biểu thức tiền tố được biểu diễn bằng cách đặt toán tử lên trước các toán hạng. Cách biểu diễn này còn được biết đến với tên gọi “ký pháp Ba Lan” do nhà toán học Ba Lan Jan Łukasiewicz phát minh năm 1920. Với cách biểu diễn này, thay vì viết x y như dạng trung tố, ta sẽ viết xy. Tùy theo độ ưu tiên của toán tử mà chúng sẽ được sắp xếp khác nhau, bạn có thể xem một số ví dụ ở phía sau phần giới thiệu này.
    - Postfix: Ngược lại với cách Prefix, tức là các toán tử sẽ được đặt sau các toán hạng. Cách biểu diễn này được gọi là “ký pháp nghịch đảo Ba Lan” hoặc được viết tắt là RPN (Reverse Polish notation), được phát minh vào khoảng giữa thập kỷ 1950 bởi một triết học gia và nhà khoa học máy tính Charles Hamblin người Úc.

    Một số ví dụ:

    InfixPrefixPostfix
    x y xyxy
    x y-z- xyzxy z -
    x y*z x*yzxyz*
    x (y-z) x-yzxyz-
    Phương pháp chuyển từ biểu thức trung tố sang tiền tố và hậu tố

    Có hai cách để chuyển một biểu thức từ trung tố sang hai loại còn lại đó là dùng:
    - Stack
    - Expression Tree (cây biểu thức)
    Việc dùng Stack phổ biến hơn có ưu điểm là dễ cài đặt, đơn giản còn dùng Expression Tree sẽ giúp việc chuyển đổi được dễ hiểu và trực quan hơn tuy nhiên lại mất thời gian cài đặt. Trong bài viết này chỉ trình bày kĩ thuật sử dụng Stack, kĩ thuật dùng Expression Tree sẽ được
    giới thiệu trong bài viết sau.

    Độ ưu tiên của các toán tử

    Một trong những điều quan trọng trước khi bắt đầu là phải tính toán được độ ưu tiên của các toán tử trong biểu thức nhập vào. Để đơn giản ta chỉ xét các toán tử hai ngôi và thường dùng bao gồm: multiply ( ),subtract (-), multiply (*), divide (/), Modulo (%). Theo đó các toán tử “*, /, %” có cùng độ ưu tiên và cao hơn hai toán tử “ , -”. Như vậy ta có phương thức lấy độ ưu tiên toán tử như sau:
    1Xác định mức ưu tiên toán tử nằm trong chuỗi biểu thức (toantu)
    2{
    3 if (toantu := "*" OR toantu := "/" OR toantu == "%")
    4 return 2;
    5 if (toantu := " " OR toantu == "-")
    6 return 1;
    7 return 0;
    8}
    Định dạng lại biểu thức Infix trước khi chuyển đổi
    Các biểu thức Infix khi nhập vào có thể dư thừa các khoảng trắng, các kí tự không phù hợp hoặc viết sai cú pháp. Phần kiểm tra cú pháp bạn có thể làm riêng hoặc để luôn trong các thuật toán chuyển đổi. Trong phần này yêu cầu định dạng để các phần tử của biểu thức (toán tử, toán hạng) phải được phân cách với nhau bằng một khoảng trắng. Các phần tử gọi là các token.
    Các phương thức kiểm tra toán tử và toán hạng

    Trong thuật toán chuyển đổi này ta cần có các phương thức kiểm tra xem một thành phần của chuỗi có phải là toán tử hoặc toán hạng không. Thay vì sử dụng các cấu trúc if hoặc switch dài dòng và bất tiện khi phát triển, ta sẽ dùng Regex để kiểm tra.
    Ngoài ra vì chuỗi nhập vào là một biểu thức đại số, nên các toán hạng ta sẽ xét không chỉ là các chữ số mà còn có chữ cái từ a-z và A-Z.
    Có một quy tắc nữa là khi dùng chữ cái thì chỉ cho phép duy nhất một chữ cái đại diện cho một toán hạng, còn khi dùng chữ số thì có thể nhiều chữ số ghép thành một toán hạng. Ví dụ viết ab phải hiểu là a*b, viết 123 không được hiểu là 1*2*3.
    1Chương_trình_con_Nhận_dạng_toán_tử_tên_là IsOperator(string str)
    2{
    3 Trả_về_đúng_khi_str_thuộc_một_trong_(str, @" |-|*|/|%");
    4}
    5Chương_trình_con_nhận_dạng_toán_hạng_là_chữ IsOperand(string str)
    6{
    7 Trả_về_đúng_khi_str_chứa_ký_tự_đầu_tiên_trong_(str, @"^d $|^([a-z]|[A-Z])$");
    8}
    Chuyển biểu thức Infix sang Postfix
    Lý do tôi trình bày thuật toán chuyển sang postfix trước vì thuật toán này phổ biến và dễ cài đặt hơn, bạn cũng sẽ thấy sự tương đồng của thuật toán này với thuật toán chuyển từ infix sang prefix khi tôi trình bày ở phần sau.
    Thuật toán để chuyển một biểu thức Infix sang dạn Prefix:
    Đọc từng token trong biểu thức infix từ trái qua phải, với mỗi token ta thực hiện các bước sau:
    Nếu là toán hạng: cho ra output.
    - 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 output 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 output.
    • Đưa toán tử hiện tại vào stack
    Sau khi duyệt hết biểu thức infix, nếu trong stack còn phần tử thì lấy các token trong đó ra và cho lần lượt vào output.</blockquote>Hãy xem ví dụ sau để hiểu rõ hơn thuật toán này.
    Chúng ta sẽ chuyển biểu thức A*B C*((D-E) F)/G từ dạng Infix sang dạng Postfix:
    TokenStackOutput
    A{Empty}A
    **A
    B*A B
    A B *
    C A B * C
    * *A B * C
    ( * (A B * C
    ( * ( (A B * C
    D * ( (A B * C D
    - * ( ( -A B * C D
    E * ( ( -A B * C D E
    ) * (A B * C D E -
    * ( A B * C D E -
    F * ( A B * C D E – F
    ) *A B * C D E – F
    / /A B * C D E – F *
    G /A B * C D E – F * G

    {Empty}A B * C D E – F * G /



    Được sửa bởi Admin ngày Sun May 15, 2011 7:01 am; sửa lần 1.

    http://khmt.123.st

    Admin


    Quản trị viên
    Quản trị viên
    So sánh thứ tự của các toán hạng khi viết một biểu thức ở dạng trung tố và hậu tố:
    Nếu ta không quan tâm đến toán tử, mà chỉ quan sát các toán hạng thôi thì sẽ thấy:
    Thứ tự các toán hạng ở cả 2 cách viết trung tố và hậu tố là như nhau.
    Ví dụ như ở trung tố thứ tự của toán hạng là A toán tử B toán tử C... dấu ngoặc ưu tiên lung tung.
    Thì thứ tự toán hạng ở hậu tố cũng lần lượt A B C nhưng toán tử của phép tính được sắp xếp cho phép tính thực hiện trước.

    http://khmt.123.st

    Admin


    Quản trị viên
    Quản trị viên
    [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;


    ELSE
    Push(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)

    http://khmt.123.st

    Admin


    Quản trị viên
    Quản trị viên
    Giải thuật tính toán một biểu thức trung tố

    Để tính toán một biểu thức trung tố bất kỳ, xen kẽ các toán tử, thì ta nên nhớ thứ tự ưu tiên các toán tử trước nếu không nhóm các dấu ngoặc lại. Còn có dấu ngoặc thì thực hiện các phép tính trong dấu ngoặc trong cùng trước.
    Ở đây ta sẽ sử dụng 2 ngăn xếp. Điều này cho phép tính toán dễ hơn và không gây nhầm lẫn.

    Ý tưởng:

    Giả sử xâu M là xâu trung tố cần tính. Ở đây có điều kiện là xâu M đúng đắn, các phép toán hoàn toàn hợp lệ và có thể thực hiện được.
    B1- Duyệt cho đến hết M.
    B2- Đọc một phần tử Mi.
    B3- Nếu gặp một toán hạng thì ghi nó vào stack S1.
    B4- Nếu gặp dấu mở ngoặc, đưa nó vào stack S2.
    B5- Nếu gặp một toán tử (gọi là o1), thực hiện hai bước sau:
    o Chừng nào còn có một toán tử o2 ở (đỉnh ngăn xếp S2) VÀ độ ưu tiên của o1 nhỏ hơn hay bằng độ ưu tiên của o2 thì lấy o2 ra khỏi S2 để tính toán với 2 toán hạng của S1
    o Push o1 vào ngăn xếp S2.
    - Nếu gặp dấu đóng ngoặc thì cứ lấy các toán tử trong ngăn xếp S2 ra và tính toán cho đến khi lấy được dấu mở ngoặc ra khỏi ngăn xếp S2.
    - Khi đã duyệt hết biểu thức trung tố, lần lượt lấy tất cả toán hạng (nếu còn) từ ngăn xếp S2 ra và tính toán với toán hạng trong S1.

    http://khmt.123.st

    Admin


    Quản trị viên
    Quản trị viên
    - Khởi tạo 2 Stack rỗng: S1, S2;

    - Xây dựng hàm con xét độ ưu tiên
    UT(x)


    CASE x


    *,/,%:
    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:
    Push (Mi, S1);


    Dấu "(":
    Push (Mi, S2);


    Toán tử:




    While UT(Top(S2) > UT(Mi)
    Do


    Begin



    Pop(s1,b);



    Pop(s2,x);



    Pop(s1,a);



    y:=a x b;



    Push(y, S1);


    End


    Push (Mi, S2);

    Dấu ")":
    While Top(S2)<>"("
    Do


    Begin
    Pop(s1,b);



    Pop(s2,x);



    Pop(s1,a);



    y:=a x b;



    Push(y, S1);


    End While



    Pop(S2,x)


    End Case


    While NOT
    Empty(S2)
    Do


    Begin
    Pop (S1,b);



    Pop (S2, x);



    Pop (S1, a);



    y:=a x b;



    Push(y, S1);


    End


    Pop (S1, x)



    Output (x);



    End.



    http://khmt.123.st

    7 Minh hoạ cho việc tính trung tố on Sun May 15, 2011 6:38 pm

    Admin


    Quản trị viên
    Quản trị viên
    Minh hoạ cho việc tính trung tố phần giải thuật trên
    Giả sử ta cần tính M = 9 + 31 * (7 - (6 + 5)* 4 - 3*2)*2
    Đọc được theo M
    Mi
    Công việc phải làm
    S1
    S2
    Ghi chú
    99
    Đưa 9 vào S1
    9


    9 +
    +
    Đưa + vào S2
    9
    +

    9 + 3131Đưa 31 vào S1
    9,31+

    9 + 31 *
    *
    Đưa * vào S2
    9,31+, *

    9 + 31 * ((
    Đưa ( vào S2
    9,31+,*,(

    9 + 31 * (7
    7
    Đưa 7 vào S1
    9,31,7
    +,*,(

    9 + 31 * (7 -
    -
    Đưa -vào S2
    9,31,7
    +,*,(,-

    9 + 31 * (7 - ((
    Đưa ( vào S2
    9,31,7
    +,*,(,-,(

    9 + 31 * (7 - (6
    6
    Đưa 6 vào S1
    9,31,7,6
    +,*,(,-,(
    9 + 31 * (7 - (6 +
    +
    Đưa + vào S2
    9,31,7,6+,*,(,-,(,+
    9 + 31 * (7 - (6 + 55
    Đưa 5 vào S1
    9,31,7,6,5+,*,(,-,(,+
    9 + 31 * (7 - (6 + 5))
    Lấy 5, 6 ở S1 ra và + ở S2 ra, tính 6+5 đưa kết quả là 11 vào S1, lấy ( ra khỏi S2
    9,31,7,11
    +,*,(,-

    9 + 31 * (7 - (6 + 5)*
    *
    Đưa * vào S2
    9,31,7,11+,*,(,-,*

    9 + 31 * (7 - (6 + 5)* 4
    4
    Đưa 4 vào S1
    9,31,7,11,4
    +,*,(,-,*
    9 + 31 * (7 - (6 + 5)* 4 --
    Lấy 4 và 11 ra khỏi S1, lấy * ra khỏi S2, tính 11*4, đưa kết quả 44 vào S1. Đưa dấu - vào tiếp S2
    9,31,7,44
    +,*,(,-,-
    Do dấu * trong S2 ưu tiên cao hơn dấu -
    9 + 31 * (7 - (6 + 5)* 4 - 33
    Đưa 3 vào S1
    9,31,7,44,3+,*,(,-,-
    9 + 31 * (7 - (6 + 5)* 4 - 3**
    Đưa * vào S2
    9,31,7,44,3+,*,(,-,-,*
    9 + 31 * (7 - (6 + 5)* 4 - 3*22
    Đưa 2 vào S19,31,7,44,3,2+,*,(,-,-,*
    9 + 31 * (7 - (6 + 5)* 4 - 3*2))
    1.Lấy 2,3 khỏi S1 và * khỏi S2, thực hiện 3*2 đưa kết quả là 6 vào S1.
    9,31,7,44,6+,*,(,-,-


    2. Lấy 6,44 ra khỏi S1 và - ra khỏi S2, thực hiện 44-6 đưa kết quả là 38 vào S1 9,31,7,38+,*,(,-


    3. Lấy 38,7 ra khỏi S1 và - ra khỏi S2, thực hiện 7-38 đưa kết quả là -31 vào S1. Lấy để bỏ dấu ( ở S2
    9,31,-31
    +,*
    Lấy đến dấu ( thì dừng
    9 + 31 * (7 - (6 + 5)* 4 - 3*2)**
    Đưa dấu * vào S2
    9,31,-31+,*,*

    9 + 31 * (7 - (6 + 5)* 4 - 3*2)*22
    Đưa 2 vào S1
    9,31,-31,2+,*,*Hết chuỗi


    Lấy 2 và -31 khỏi S1, lấy * khỏi S2, thực hiện -31*2 đưa kết quả là -62 vào S2
    9,31,-62
    +,*



    Lấy -62 và 31 ra khỏi S1 và * ra khỏi S2, tính 31+-62 ghi kết quả -31 vào S2
    9,-31+



    Lấy - 31 và 9 khỏi S1 và + khỏi F2 tính 9 + - 31 ghi kết quả là -22 vào S1
    -22

    Hết thao tác do chuỗi S2 rỗng


    Lấy kết quả - 22 ghi ra màn hình.



    http://khmt.123.st

    mrP


    Thành viên cao cấp
    Thành viên cao cấp
    Chương trình viết giả mã chuyển từ trung tố sang hậu tố
    - Ý tưởng viết thì đúng, nhưng lúc viết thì thiếu.
    + Pop(S,x) trước khi N:= N + x;
    + Sau khi xong thì phải xóa dấu "(" ra khỏi stack

    + Khi Mi là toán tử thì phải kiểm tra stack có rỗng không rồi mới thực hiện

    + Cuối cùng kiểm tra stack, nếu không rỗng thì đẩy ra

    Admin


    Quản trị viên
    Quản trị viên
    Chuyển biểu thức trung tố không dấu ngoặc thành hậu tố
    PROC Chuyen
    1) S := Ø; N = Ø;
    2)
    - Xây dựng hàm con xét độ ưu tiên
    UT(x)


    CASE x
    of

    *,/:
    UT=2

    -, + :
    UT=1

    END

    3) For i :=1 to /M/



    CASE Mi of


    a)Toán hạng:



    N = N + Mi;

    b) Toán tử:




    WHILE (S ≠ Ø) & (UT(Top(S)) ≥ UT(Mi)) DO



    Pop(S, x);



    N = N + x;



    Push(Mi, S)

    End Case


    4) Repeat




    Pop(S,x);
    N := N + x

    Until Empty(S)



    5) Output (N)


    ================
    Nếu Khách viếng thăm không đọc được các bài trong Kho bài chuẩn, là do Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.]. Sở dĩ nếu Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.] là vì Khách viếng thăm khai báo thiếu họ, thiếu tên, không dấu hoặc khai báo linh tinh trong trường RN. Đừng xin xỏ uỷ quyền, vì uỷ quyền hoàn toàn tự động cho Thành viên đọc được mọi thứ (không chỉnh bằng tay được), các thành viên khác sẽ không bao giờ được uỷ quyền.
    [You must be registered and logged in to see this image.]
    Trang phục may sẵn rẻ nhất Hà Nội ở 148 Vương Thừa Vũ
    ĐT: 043.568.1938

    [You must be registered and logged in to see this link.]
    [You must be registered and logged in to see this link.]
    http://khmt.123.st

    tieuthumeo


    Thành viên bắt đầu chia sẻ
    Thành viên bắt đầu chia sẻ
    Admin đã viết:Minh hoạ cho việc tính trung tố phần giải thuật trên
    Giả sử ta cần tính M = 9 + 31 * (7 - (6 + 5)* 4 - 3*2)*2
    Đọc được theo M
    Mi
    Công việc phải làm
    S1
    S2
    Ghi chú
    99
    Đưa 9 vào S1
    9


    9 +
    +
    Đưa + vào S2
    9
    +

    9 + 3131Đưa 31 vào S1
    9,31+

    9 + 31 *
    *
    Đưa * vào S2
    9,31+, *

    9 + 31 * ((
    Đưa ( vào S2
    9,31+,*,(

    9 + 31 * (7
    7
    Đưa 7 vào S1
    9,31,7
    +,*,(

    9 + 31 * (7 -
    -
    Đưa -vào S2
    9,31,7
    +,*,(,-

    9 + 31 * (7 - ((
    Đưa ( vào S2
    9,31,7
    +,*,(,-,(

    9 + 31 * (7 - (6
    6
    Đưa 6 vào S1
    9,31,7,6
    +,*,(,-,(
    9 + 31 * (7 - (6 +
    +
    Đưa + vào S2
    9,31,7,6+,*,(,-,(,+
    9 + 31 * (7 - (6 + 55
    Đưa 5 vào S1
    9,31,7,6,5+,*,(,-,(,+
    9 + 31 * (7 - (6 + 5))
    Lấy 5, 6 ở S1 ra và + ở S2 ra, tính 6+5 đưa kết quả là 11 vào S1, lấy ( ra khỏi S2
    9,31,7,11
    +,*,(,-

    9 + 31 * (7 - (6 + 5)*
    *
    Đưa * vào S2
    9,31,7,11+,*,(,-,*

    9 + 31 * (7 - (6 + 5)* 4
    4
    Đưa 4 vào S1
    9,31,7,11,4
    +,*,(,-,*
    9 + 31 * (7 - (6 + 5)* 4 --
    Lấy 4 và 11 ra khỏi S1, lấy * ra khỏi S2, tính 11*4, đưa kết quả 44 vào S1. Đưa dấu - vào tiếp S2
    9,31,7,44
    +,*,(,-,-
    Do dấu * trong S2 ưu tiên cao hơn dấu -
    9 + 31 * (7 - (6 + 5)* 4 - 33
    Đưa 3 vào S1
    9,31,7,44,3+,*,(,-,-
    9 + 31 * (7 - (6 + 5)* 4 - 3**
    Đưa * vào S2
    9,31,7,44,3+,*,(,-,-,*
    9 + 31 * (7 - (6 + 5)* 4 - 3*22
    Đưa 2 vào S19,31,7,44,3,2+,*,(,-,-,*
    9 + 31 * (7 - (6 + 5)* 4 - 3*2))
    1.Lấy 2,3 khỏi S1 và * khỏi S2, thực hiện 3*2 đưa kết quả là 6 vào S1.
    9,31,7,44,6+,*,(,-,-


    2. Lấy 6,44 ra khỏi S1 và - ra khỏi S2, thực hiện 44-6 đưa kết quả là 38 vào S1 9,31,7,38+,*,(,-


    3. Lấy 38,7 ra khỏi S1 và - ra khỏi S2, thực hiện 7-38 đưa kết quả là -31 vào S1. Lấy để bỏ dấu ( ở S2
    9,31,-31
    +,*
    Lấy đến dấu ( thì dừng
    9 + 31 * (7 - (6 + 5)* 4 - 3*2)**
    Đưa dấu * vào S2
    9,31,-31+,*,*

    9 + 31 * (7 - (6 + 5)* 4 - 3*2)*22
    Đưa 2 vào S1
    9,31,-31,2+,*,*Hết chuỗi


    Lấy 2 và -31 khỏi S1, lấy * khỏi S2, thực hiện -31*2 đưa kết quả là -62 vào S2
    9,31,-62
    +,*



    Lấy -62 và 31 ra khỏi S1 và * ra khỏi S2, tính 31+-62 ghi kết quả -31 vào S2
    9,-31+



    Lấy - 31 và 9 khỏi S1 và + khỏi F2 tính 9 + - 31 ghi kết quả là -22 vào S1
    -22

    Hết thao tác do chuỗi S2 rỗng


    Lấy kết quả - 22 ghi ra màn hình.



    Anh ơi anh cho em hỏi là nếu khi trình bày bài làm em chỉ sử dụng 1 ngăn xếp S chứ ko chia ra thành 2 ngăn xếp Sh và St thì có đc ko ạ?

    Admin: Câu này phải hỏi thầy giáo. Nhưng theo bọn mình được biết thì khi lời giải đúng thì dù Khách viếng thăm dùng 1 ngăn xếp hay n ngăn xếp thì vẫn được điểm. Chỉ có điều là cách giải không tối ưu sẽ không được điểm tối đa thôi. Vì những bài kiểm tra trên lớp dù cách giải gì đi nữa, miễn là đúng, thầy vẫn chấm rất cẩn thận. Khách viếng thăm nên nhớ là ở đây bài được chấm theo giải thuật chứ không phải chấm theo quy cách trình bày.

    11 [Ý kiến] on Thu Jul 28, 2011 9:00 pm

    daotrang


    Thành viên bắt đầu chia sẻ
    Thành viên bắt đầu chia sẻ
    Admin đã viết:Chuyển biểu thức trung tố không dấu ngoặc thành hậu tố
    PROC Chuyen
    1) S := Ø; N = Ø;
    2)
    - Xây dựng hàm con xét độ ưu tiên
    UT(x)


    CASE x
    of

    *,/:
    UT=2

    -, + :
    UT=1

    END

    3) FOR i :=1 to /M/



    CASE Mi of


    a)Toán hạng:



    N = N + Mi;

    b) Toán tử:




    WHILE (S ≠ Ø) & (UT(Top(S)) ≥ UT(Mi)) DO



    Pop(S, x);



    N = N + x;



    Push(Mi, S)

    End Case


    4) Repeat




    Pop(S,x);
    N := N + x

    Until Empty(S)



    5) Output (N)

    Theo mình nghĩ phần 3)b) Khi Mi là toán tử phải đưa hết các toán tử có độ ưu tiên cao hơn hoặc bằng Mi trong stack ra sau đó đưa toán tử Mi vào stack tức là việc Push(Mi,S) là công việc thực hiện có vai trò bình đẳng với vòng WHILE và nó đứng ngoài vòng WHILE thế này:
    b) Toán tử:
              b1)WHILE (S ≠ Ø) & (UT(Top(S)) ≥ UT(Mi)) DO
                        Pop(S, x);
                        N = N + x;
              b2)Push(Mi, S)

    Ban QT: Uh, Bạn nói đúng rồi đấy.

    ngoannhi


    Thành viên ít chịu khó
    Thành viên ít chịu khó
    Hic phần:
    Minh hoạ cho việc tính trung tố phần giải thuật trên
    Giả sử ta cần tính M = 9 + 31 * (7 - (6 + 5)* 4 - 3*2)*2 = -2657 ( tính bằng máy tính ) >>>>> SAI ... Các anh chị xem lại giải thuật dùm em với nhé

    sinhmd


    Quản trị viên
    Quản trị viên
    ngoannhi đã viết:Hic phần:
    Minh hoạ cho việc tính trung tố phần giải thuật trên
    Giả sử ta cần tính M = 9 + 31 * (7 - (6 + 5)* 4 - 3*2)*2 = -2657 ( tính bằng máy tính ) >>>>> SAI ... Các anh chị xem lại giải thuật dùm em với nhé


    Bạn ơi Admin trình bày là giải thuật dùng cho trung tố không dấu ngoặc, còn bài của bạn là trung tố không đầy đủ dấu ngoặc, thuật toán có khác một chút, bạn lưu ý phần mở và đóng dấu ngoặc ấy. Thời gian gấp quá ko tiện gõ lên diễn đàn, chúc bạn thi tốt.OK


    ================

    http://climategis.com/forum/

    trangmeomeo


    Thành viên bắt đầu chia sẻ
    Thành viên bắt đầu chia sẻ
    Admin đã viết:
    [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;


    ELSE
    Push(Mi,S)

    End Case


    Repeat




    Pop(S,x);



    IF x <>"("
    N:=N + x

    Until Empty(S)



    Output (N)


    anh chi k23 ơi.Anh chị nào có giải thuật chuẩn nhất up lên giúp em với. Em theo dõi trong giáo trình của thầy Đào Thanh Tĩnh và một số vở của các anh chị ghi lại nhưng có nhiều cách viết quá. Và ở bài này của anh admin em thấy nhiều chỗ thiếu dấu ';' kết thúc lệnh, chỗ "endcase" chỗ thì chỉ "end" không. hix.Mỗi ngôn ngữ có một cách viết khác nhau. Mong anh chị viết chuẩn hộ em để em có một đề cương ôn thi tốt. Cảm ơn anh chị nhiều.
    Mà ở phần giải thuật này em hiểu ý tưởng của anh nhưng chưa hiểu lắm về các bước của giải thuật. Mong anh admin giải thích giúp em hiểu sâu hơn về vấn đề.

    Anh Đức


    Thành viên cao cấp
    Thành viên cao cấp
    [You must be registered and logged in to see this image.]

    Anh Đức


    Thành viên cao cấp
    Thành viên cao cấp
    [You must be registered and logged in to see this image.]

    Anh Đức


    Thành viên cao cấp
    Thành viên cao cấp
    [You must be registered and logged in to see this image.]

    Anh Đức


    Thành viên cao cấp
    Thành viên cao cấp
    [You must be registered and logged in to see this image.]

    trangmeomeo


    Thành viên bắt đầu chia sẻ
    Thành viên bắt đầu chia sẻ
    anh Đức Anh ơi! giúp em giải thuật chuyển từ dạng trung tố sang dạng hậu tố có đầy đủ dấu ngoặc với, ở thuật toán này em thấy mọi người viết khác nhau quá.
    à. khi mình thực hiện thuật toán bằng tay, theo ý tưởng của giải thuật thì khi gặp dấu "(" thì ta đưa nó vào S, nhưng trong một số bài giải em xem của thầy và một số người k23 làm thì khi gặp "(" mọi người bỏ qua không đưa vào S. Vậy có được không ạ ?

    Anh Đức


    Thành viên cao cấp
    Thành viên cao cấp
    Gửi Trang!
    Với bài toán chuyển M từ dạng trung tố sang dạng hậu tố (M có đầy đủ dấu ngoặc)
    Có hai vấn đề sau đây:
    1. Vì M là biểu thức đầy đủ dấu ngoặc nên nếu gặp dấu ngoặc đóng thì đương nhiên trước đó đã phải có dấu ngoặc mở.
    2. Với phép toán có dấu ngoặc, thì đương nhiên phải thực hiện phép toán trong ngoặc trước.
    Vậy: Nếu gặp toán hạng thì đưa toán hạng vào N.
    Nếu gặp toán tử thì đưa toán tử vào S
    Khi gặp dấu ngoặc mở thì không cần đưa vào S. mà đọc tiếp...
    Nếu gặp dấu ngoặc đóng thì lấy toán tử ra khỏi S và đưa toán tử đó vào N.

    Anh Đức


    Thành viên cao cấp
    Thành viên cao cấp
    [You must be registered and logged in to see this image.]

    trangmeomeo


    Thành viên bắt đầu chia sẻ
    Thành viên bắt đầu chia sẻ
    Anh Đức anh: Trong phần Toán tử em thấy hình như anh thiếu xét tính ưu tiên của các toán tử trong S thì phải? Anh xem lại giúp em nhé. Thanks anh!

    Anh Đức


    Thành viên cao cấp
    Thành viên cao cấp
    Em ạ!
    Khi xét đến ưu tiên các toán tử trong S, thì chỉ xét với các biểu thức M "không có dấu ngoặc" hoặc "không đầy đủ dấu ngoặc" thôi nhé. Em phải cố gắng đọc thật kỹ lý thuyết và làm thật nhiều ví dụ bằng tay để dễ hiểu hơn nhé!

    Anh Đức


    Thành viên cao cấp
    Thành viên cao cấp
    [You must be registered and logged in to see this image.]

    Anh Đức


    Thành viên cao cấp
    Thành viên cao cấp
    [You must be registered and logged in to see this image.]

    Sponsored content


    Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang  Thông điệp [Trang 1 trong tổng số 2 trang]

    Chuyển đến trang : 1, 2  Next

    Permissions in this forum:
    Bạn không có quyền trả lời bài viết

     

    Ghi rõ nguồn khi copy các bài viết từ Website này.
    Bản quyền thuộc Khoa học Máy tính. Số lượt truy cập tính đến hiện tại:Website counter
    Modified skin by Nguyễn Anh Cường. Developed by Members of http://khmt.123.st

    Forumotion.com | © PunBB | Free forum support | Liên hệ | Report an abuse | Sosblogs