Đạ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.




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

    Admin

    Admin
    Quản trị viên
    Quản trị viên
    Đề bài trang 18, sách Cấu trúc dữ liệu và giải thuật của thầy Đào Thanh T~:
    Bài 1. Cho biểu thức:
    Code:
     M = (A + B)*(C/(U+V))
    dưới dạng hậu tố. Dùng bảng để minh hoạ hình ảnh của ngăn xếp được sử dụng để tính giá trị của biểu thức hậu tố nhận được nếu đặt A = 20, B = 12, C = 14 , U = 4, V = 3.

    Bài 2. Dùng bảng để minh hoạ hình ảnh của ngăn xếp được sử dụng, để tính giá trị của biểu thức
    Code:
    ((20+12)*(14/(4+3)))

    Bài 3. Viết thủ tục dạng giả mã chuyển một biểu thức dạng trung tố về dạng hậu tố, sử dụng ngăn xếp hỗ trợ.

    Bài 4. Dùng bảng để minh hoạ hình ảnh của ngăn xếp được sử dụng để chuyển một biểu thức dạng trung tố đầy đủ dấu ngoặc về dạng hậu tố.

    Bài 5. Trong một văn bản (chẳng hạn một chương trình nguồn viết trên Pascal, các ký hiệu và dấu ngoặc [({})] phải khớp từng cặp và lồng vào nhau một cách đúng đắn. Viết thủ tục giả mã để kiểm tra tính đúng đắn của dấu ngoặc trong một xâu ký tự, sử dụng ngăn xếp hỗ trợ.



    Được sửa bởi Admin ngày Sun Jul 03, 2011 8:09 pm; sửa lần 2.

    https://khmt.123.st

    2[Lời giải]Ngăn xếp mô tả hậu tố và giải thuật đối với ngăn xếp Empty Giải bài 1 Wed May 11, 2011 10:49 pm

    Admin

    Admin
    Quản trị viên
    Quản trị viên
    Giải bài 1.
    Biểu thức M được viết dưới dạng hậu tố như sau:
    Code:
    A  B+  C U V+    / *
    Thay các giá trị sẽ được:
    Code:
    20 12+  14 4 3+    / *

    Ý TƯỞNG

    Duyệt cho đến hết M
    a. Đọc một phần tử x
    b. Nếu x là biểu thức thì nạp vào stack
    c. Nếu x là toán tử thì lấy 2 phần tử trên đỉnh stack và tính, sau đó đưa kết quả vào stack.
    Lấy giá trị trong stack và viết ra màn hình.

    GIẢI THUẬT

    Khởi tạo stack rỗng
    REPEAT
    a. Đọc phần tử x từ biểu thức M
    b. IF x là toán tử Then
    i. Pop (S, a)
    ii. Pop (S, b)
    iii. w:= b x a
    iv. Push (w, S)
    Else Push(x, S)
    UNTIL Kết thúc biểu thức M;
    Pop (S, x)
    Write (x)

    Quá trình đọc và làm việc trong stack được minh hoạ như sau:

    Đã đọc theo M
    x
    Lệnh
    Công việc
    Stack
    20
    20
    push (x,S)
    Đưa 20 vào S
    20
    20 12
    12
    push (x,S)Đưa 12 vào S
    12
    20 12

    Pop(S, a)
    Lấy 12 đưa vào a



    Pop(S,b)
    Lấy 20 đưa vào b



    w=b x a
    Cộng 12 với 20



    Push (w, S)
    Đưa kết quả vào S
    22
    20 12 1414
    push (x,S)Đưa 14 vào S22,14
    20 12 14 44
    push (x,S)Đưa 4 vào S
    22, 14, 4
    20 12 14 4 3
    3
    push (x,S)Đưa 3 vào S
    22, 14, 4, 3
    20 12 14 4 3 /

    Pop(S, a)Lấy 3 đưa vào a



    Pop(S, b)Lấy 4 đưa vào b



    w=b x a
    Cộng 3 với 4



    Push (w, S)Đưa kết quả vào S
    22, 14, 7

    /
    Pop(S, a)Lấy 7 ra



    Pop(S, b)Lấy 14 ra


    w=b x aLấy 14/7



    Push (w, S)Đưa kết quả vào S22, 2

    *
    Pop(S, a)Lấy 2 ra



    Pop(S, b)Lấy 22 ra



    w=b x aLấy 22 * 2



    Push (w, S)Đưa kết quả vào S44



    Được sửa bởi Admin ngày Sun Jul 03, 2011 8:10 pm; sửa lần 1.

    https://khmt.123.st

    3[Lời giải]Ngăn xếp mô tả hậu tố và giải thuật đối với ngăn xếp Empty Giải bài 2 Sun May 15, 2011 8:57 am

    Admin

    Admin
    Quản trị viên
    Quản trị viên
    Admin đã viết:Đề bài trang 18, sách Cấu trúc dữ liệu và giải thuật
    Bài 2. Dùng bảng để minh hoạ hình ảnh của ngăn xếp được sử dụng, để tính giá trị của biểu thức
    Code:
    M=((20  12)*(14/(4  3)))
    Lời giải:
    Ý tưởng:
    - Duyệt cho đến hết M
    - Nếu Mi là ngoặc mở, bỏ qua
    - Nếu Mi là toán tử hoặc toán hạng: Đưa vào stack
    - Nếu là dấu đóng ngoặc thì lấy ra 3 phần tử trên đỉnh Stack, tính xong đưa vào stack.
    - Lấy giá trị trong stack đưa ra màn hình.
    Giải thuật để tính giá trị biểu thức trung tố:
    - Khởi tạo Stack rỗng.
    For i:=1 to /M/


    Case Mi of


    toán tử, toán hạng:



    Push(Mi, S)

    Dấu ")":



    Pop(S,c);


    Pop(S,b);


    Pop(S,a)


    x:=a b c;
    Push(x,S);
    Pop(S,x);
    Output (x)

    Quá trình đọc và làm việc được minh hoạ theo bảng:
    M=((20 +12)*(14/(4 +3)))
    Đọc được theo M
    Mi
    Công việc
    Stack
    (
    (
    Bỏ qua

    ((
    (
    Bỏ qua

    ((20
    20
    Đưa 20 vào S
    20
    ((20+
    Đưa vào + S
    20, +
    ((20 + 1212
    Đưa 12 vào S
    20, +,12
    ((20 +12))
    Lấy 12, + , 20 ra, tính 20 +12 đưa kết quả là 32 vào S
    32
    ((20 + 12)**
    Đưa * và S
    32, *
    ((20 +12)*((
    Bỏ qua
    32, *
    ((20 +12)*(1414
    Đưa 14 vào S
    32, *, 14
    ((20 +12)*(14//
    Đưa / vào S
    32,*,14,/
    ((20 +12)*(14/((
    Bỏ qua
    32,*,14,/
    ((20 +12)*(14/(44
    Đưa 4 vào S
    32,*,14,/,4
    ((20 +12)*(14/(4+
    Đưa +vào S
    32,*,14,/,4,+
    ((20 +12)*(14/(4 +33
    Đưa 3 vào S
    32,*,14,/,4, +,3
    ((20 +12)*(14/(4 +3))
    Lấy 3, + , 4 ra, tính toán 4 +3 đưa kết quả là 7 vào S
    32,*,14,/,7
    ((20 +12)*(14/(4 +3)))
    Lấy 7, /, 14 ra, tính 14/7 đưa kết quả là 2 vào S
    32,*,2
    ((20 +12)*(14/(4 +3))))
    Lấy 2, *, 32 ra tính 32 * 2, đưa kết quả là 64 vào S

    Sau đó đưa kết quả chính là số 64 ra màn hình
    64

    https://khmt.123.st

    Admin

    Admin
    Quản trị viên
    Quản trị viên
    Bài 5. Trong một văn bản (chẳng hạn một chương trình nguồn viết trên
    Pascal, các ký hiệu và dấu ngoặc [({})] phải khớp từng cặp và lồng vào
    nhau một cách đúng đắn. Viết thủ tục giả mã để kiểm tra tính đúng đắn
    của dấu ngoặc trong một xâu ký tự, sử dụng ngăn xếp hỗ trợ.
    Ý tưởng:
    - Duyệt cho đến hết M
    - Đọc một phần tử Mi để xử lý
    - Nếu là các dấu mở ngoặc đưa vào Stack.
    - Nếu là dấu đóng ngoặc thì lấy phần tử đầu tiên trên đỉnh ra kiểm tra xem có cùng cặp không. Nếu không đúng, thông báo sai và thoát khỏi vòng duyệt.
    - Các trường hợp khác của Mi, không làm gì cả.
    Kết thúc duyệt, S không rỗng thì thông báo thiếu dấu ngoặc đóng. Ngược lại thông báo OK.

    Giải thuật:
    - Khởi tạo Stack S rỗng.
    - Tạo lập hàm KT 2 phần tử dấu ngoặc, xác định đúng hoặc sai.
    KTL:=0 là không lỗi, KTL:=1 là có lỗi (Có thể đặt lỗi là các số khác để báo lỗi chi tiết)
    Function KTL(Dau1, Dau2);


    Case Dau1 of

    (:
    IF (Dau2=")" then KTL:=0;


    ELSE KTL:=1

    [:IF (Dau2="]" then KTL:=0;


    ELSE KTL:=1

    {:IF (Dau2="}" then KTL:=0;


    ELSE KTL:=1

    END
    END Function

    Bắt đầu chương trình
    For i:=1 to /M/



    Case Mi of


    (, [, {:



    Push (S, Mi);

    ),],}:


    IF Empty(S) then


    Output "Lỗi thiếu dấu ngoặc mở trước vị trí " i


    ELSE


    Pop(S,x);


    IF (KTL(x,Mi)<>0 Then


    Output "Dấu ngoặc không phù hợp"


    End IF

    End Case

    IF NOT Empty(S)
    then

    Output "Lỗi thiếu dấu
    ngoặc đóng"
    ELSE
    Output"OK".
    END.

    https://khmt.123.st

    sangminh

    avatar
    Thành viên bắt đầu chia sẻ
    Thành viên bắt đầu chia sẻ
    Bài 1 (trang 18).biểu thức hậu tố là : AB+CUV/* mới đúng chứ anh?
    anh coi lai nhé.

    namgshg1993

    namgshg1993
    Thành viên ít chịu khó
    Thành viên ít chịu khó
    Anh ơi!!anh có thể giải bài 3,4,5 được khộng ạ!

    Ban QT:
    Lời giải tương tự
    .

    vip8668

    vip8668
    Thành viên ít chịu khó
    Thành viên ít chịu khó
    Admin đã viết:Bài 5. Trong một văn bản (chẳng hạn một chương trình nguồn viết trên
    Pascal, các ký hiệu và dấu ngoặc [({})] phải khớp từng cặp và lồng vào
    nhau một cách đúng đắn. Viết thủ tục giả mã để kiểm tra tính đúng đắn
    của dấu ngoặc trong một xâu ký tự, sử dụng ngăn xếp hỗ trợ.
    Ý tưởng:
    - Duyệt cho đến hết M
    - Đọc một phần tử Mi để xử lý
    - Nếu là các dấu mở ngoặc đưa vào Stack.
    - Nếu là dấu đóng ngoặc thì lấy phần tử đầu tiên trên đỉnh ra kiểm tra xem có cùng cặp không. Nếu không đúng, thông báo sai và thoát khỏi vòng duyệt.
    - Các trường hợp khác của Mi, không làm gì cả.
    Kết thúc duyệt, S không rỗng thì thông báo thiếu dấu ngoặc đóng. Ngược lại thông báo OK.

    Giải thuật:
    - Khởi tạo Stack S rỗng.
    - Tạo lập hàm KT 2 phần tử dấu ngoặc, xác định đúng hoặc sai.
    KTL:=0 là không lỗi, KTL:=1 là có lỗi (Có thể đặt lỗi là các số khác để báo lỗi chi tiết)
    Function KTL(Dau1, Dau2);


    Case Dau1 of

    (:
    IF (Dau2=")" THEN KTL:=0;


    ELSE KTL:=1

    [:IF (Dau2="]" THEN KTL:=0;


    ELSE KTL:=1

    {:IF (Dau2="}" THEN KTL:=0;


    ELSE KTL:=1

    END
    END Function

    Bắt đầu chương trình
    FOR i:=1 to /M/



    Case Mi of


    (, [, {:



    Push (S, Mi);

    ),],}:


    IF Empty(S) THEN


    Output "Lỗi thiếu dấu ngoặc mở trước vị trí " i


    ELSE


    Pop(S,x);


    IF (KTL(x,Mi)<>0 THEN


    Output "Dấu ngoặc không phù hợp"


    End IF

    End Case

    IF NOT Empty(S)
    THEN

    Output "Lỗi thiếu dấu
    ngoặc đóng"
    ELSE
    Output"OK".
    END.


    Em nghĩ bài này còn thiếu. Nếu khi gặp dấu đóng ngoặc mà ngăn xếp rỗng không còn dấu mở ngoặc thì sao ạ.

    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ố 1 trang]

    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 https://khmt.123.st

    Create a forum on Forumotion | ©phpBB | Free forum support | Báo cáo lạm dụng | Thảo luận mới nhất