Bài giảng Cấu trúc dữ liệu và giải thuật - Chương III: Stack và Queue

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Chương III: Stack và Queue

1. Cấu trúc dữ liệu và Giải thuật Cấutrúcdữ liệuvàGiảithuật Chương III: Stack và Queue Danh sách kiểungănxếp - Stack – Stack z Mộtkiểudanhsáchtuyến tính đặc biệt đỉnh z Phép bổ sung và phép loạibỏ tuân thủ theo cơ chế “vào sau ra trước” (last in first out) , đượcthựchiện ở đầu đỉnh đáy Đỗ Bích Diệp - Khoa CNTT - ĐHBK Hà nội 1
2. Cấu trúc dữ liệu và Giải thuật Danh sách kiểungănxếp - Stack – Hai thao tác cơ bản đốivới danh sách kiểungăn xếp z push(Element e) : bổ sung phầntử vào Stack z Element pop(): Loạibỏ và trả ra giá trị củaphầntửở đỉnh Stack – Các thao tác khác z Int size(): Trả ra số các phầntử trong Stack z Boolean isEmpty(): KiểmtraxemStack córỗng không z Element top(): Trả ra giá trị củaphầntửởđỉnh Stack Các thao tác cơ bảncủa Stack Push Đẩymộtphầntử Data vào stack Top Top Stack Stack Overflow Data Top Trường hợpStack đầy Stack Đỗ Bích Diệp - Khoa CNTT - ĐHBK Hà nội 2
3. Cấu trúc dữ liệu và Giải thuật Các thao tác cơ bảncủa Stack Pop Lấyraphầntửởđỉnh Data stack Top Top Stack Stack Underflow Trường hợp Stack cạn Top Stack Danh sách kiểungănxếp Thao tác Output Stack create() - [ ] push(5) - [5] push(3) - [5,3] pop() 3 [5] push(7) - [5,7] top() 7 [5,7] pop() 7 [5] pop() 5 [] isEmpty() true [] push(9) - [9] push(8) - [9,8] push(7) - [9,8,7] size() 3 [9,8,7] Đỗ Bích Diệp - Khoa CNTT - ĐHBK Hà nội 3
4. Cấu trúc dữ liệu và Giải thuật Ứng dụng củaStack – Lưutrữ các trang web đãtừng được duyệttrên Web browser – Cài đặt thao tác Undo trong các phầnmềmsoạn thảo – Lưudanhsáchcáclờigọi hàm trong Java Virtual Machine Lưutrữ kế tiếpcủa Stack z Stack có thểđượclưutrữ bởimộtvector lưutrữ S, gồmn ô nhớ kế tiếp nhau z Đỉnh stack đượcxácđịnh bởimộtchỉ số T – T sẽ đượccậpnhậtnếucóthaotácbổ sung hay loạibỏ đượcthựchiệntrênstack S 123 t N Đỗ Bích Diệp - Khoa CNTT - ĐHBK Hà nội 4
5. Cấu trúc dữ liệu và Giải thuật Lưutrữ kế tiếpcủa Stack z Giảithuậtbổ sung mộtphầntử vào Stack đượclưutrữ kế tiếp Procedure PUSH(S,T,X) Begin {S: vector lưutrữ có n ô nhớ; T: chỉ số củaphầntửđỉnh stack hiệnthời; X là giá trị cần thêm vào } 1. if T >= n then begin write(‘STACK TRÀN’); return; end; 2. T:= T+1; S[T] := X; End Lưutrữ kế tiếpcủa Stack z Giảithuậtlấyraphầntửởđỉnh củaStack đượclưutrữ kế tiếp Procedure POP(S,T, Y) Begin {S: stack đang xét ; T: chỉ số củaphẩntử tại đỉnh stack hiệnthời; Phầntửđượclấyrasẽđượcbảolưusử dụng biếnY } 1. if T = 0 then begin write(‘STACK CẠN’); return; end; 2. Y:= S[T]; S[T] := null; T:= T-1; End Đỗ Bích Diệp - Khoa CNTT - ĐHBK Hà nội 5
6. Cấu trúc dữ liệu và Giải thuật Hiệunăng và Hạnchế z Hiệunăng – n là số phầntử củastack – Không gian lưutrữ : O(n) – Cácthaotáccơ bảncóđộ phứctạpO(1) z Hạnchế – Kích thướctối đaphải đượcxácđịnh trướcvà không được thay đổi – Xảyratrànstack Lưutrữ móc nối đốivới Stack – Cách tiếpcận1 z Đỉnh của Stack được coi là phầntử nằm ởđầu danh sách z pop() : Lấyraphầntửđầu tiên trong danh sách móc nối z push(o) : Bổ sung mộtphầntử vào đầudanhsáchmócnối L Đỉnh Stack Đỗ Bích Diệp - Khoa CNTT - ĐHBK Hà nội 6
7. Cấu trúc dữ liệu và Giải thuật Lưutrữ móc nối đốivới Stack •Cáchtiếpcận2 •Phầntử cuối cùng đượccoilàđỉnh stack •pop() : Lấyraphầntử cuối cùng trong danh sách móc nối •push(o): Bổ sung mộtphầntử vào cuối danh sách móc nối L Đỉnh Stack zCách lưutrữ móc nối nào phù hợphơn đốivớicấutrúcdữ liệu Stack? Lưutrữ móc nối đốivới Stack – Khai báo Stack móc nối trong C struct stacknode { int item; struct stacknode *next; } ; typedef struct stacknode STACKNODE; typedef STACKNODE * STACKNODEPTR; STACKNODEPTR top = NULL; Đỗ Bích Diệp - Khoa CNTT - ĐHBK Hà nội 7
8. Cấu trúc dữ liệu và Giải thuật Lưutrữ móc nối đốivới Stack – Bổ sung vào Stack int push ( STACKNODEPTR *top , int value ) { STACKNODEPTR newnode; newnode = malloc sizeof (STACKNODE); if (nut == null) { printf(“\n No memory”); return 1; } else { newnode->item = value; newnode ->next = *top; *top = newnode; return 0; } } Lưutrữ móc nối đốivới Stack – Loạibỏ nút int pop ( STACKNODEPTR *top) { int item; STACKNODEPTR temp; temp = *top; item = (*top)->item; *top = (*top)->next; free (temp); return item; } Đỗ Bích Diệp - Khoa CNTT - ĐHBK Hà nội 8
9. Cấu trúc dữ liệu và Giải thuật Danh sách kiểuhàngđợi-Queue lối z Queue trước z Queue (Hàng đợi) là mộtkiểu danh sách tuyến tính đặcbiệt z Phép bổ sung và loạibỏ hoạt động theo cơ chế “vào trước ra trước” (first in first out) ; bổ sung ở một đầuthìloạibỏở đầukia lốisau Danh sách kiểuhàngđợi-Queue – Hai hàm cơ bản đốivới danh sách kiểuhàngđợi z enqueue(Element e) z Element dequeue() – Các hàm khác z create(): z size() : z isEmpty(): z Element front() Đỗ Bích Diệp - Khoa CNTT - ĐHBK Hà nội 9
10. Cấu trúc dữ liệu và Giải thuật Danh sách kiểuhàngđợi–Queue Thao tác Output Queue create() - [ ] enqueue(5) - [5] enqueue(3) - [5,3] dequeue() 5 [3] enqueue(7) - [3,7] front() 3 [3,7] dequeue() 3 [7] dequeue() 7 [] isEmpty() true [] enqueue(9) - [9] enqueue(8) - [9,8] enqueue(7) - [9,8,7] size() 3 [9,8,7] Ứng dụng củaQueue – Hàng đợi trong các phòng bán vé – Truy nhập vào các thiếtbị dùng chung tạivăn phòng (ví dụ máy in) Đỗ Bích Diệp - Khoa CNTT - ĐHBK Hà nội 10
11. Cấu trúc dữ liệu và Giải thuật Lưutrữ kế tiếp đốivớiQueue – Sử dụng mộtvector lưutrữ Q gồmn ô nhớ kế tiếpnhauđể biểudiễnmột Queue – Cầnnắm được hai chỉ số ‰ R: Chỉ số củaphầntử nằm ở lốisaucủaQ ‰ F: Chỉ số củaphầntửởlốitrướccủaQ Q 1 23 f r Lưutrữ kế tiếp đốivớiQueue z Khi Queue rỗng thì F = R = 0 z Khi bổ sung thêm mộtphầntử vào Queue thì R tăng lên 1 z Khi lấyramộtphầntử trong Queue thì F tăng lên 1 z Nhược điểmcủacáchtổ chứclưutrữ này – Các phầntử trong Queue sẽ dịch chuyểnkhắpkhônggiannhớ nếuliêntụcthựchiệnbổ sung rồiloạibỏ – Hiệntượng TRÀN vẫnxảy ra khi vector lưutrữ Q vẫncònchỗ nhưng R = n Đỗ Bích Diệp - Khoa CNTT - ĐHBK Hà nội 11
12. Cấu trúc dữ liệu và Giải thuật Lưutrữ kế tiếp đốivớiQueue z Khắcphụccácvấn đề bằng cách coi vector lưutrữ Queue đượctổ chứcdướidạng vòng F – Q[1] được coi nhưđứng sau Q[n] Q[n] Q[1 ] Q[2] Q[3] R Q 123 r f Các thao tác cơ bảncủa Queue Data D Enqueue A B A B D front rear front rear Queue Queue Đỗ Bích Diệp - Khoa CNTT - ĐHBK Hà nội 12
13. Cấu trúc dữ liệu và Giải thuật Các thao tác cơ bảncủa Queue Data A Dequeue A B D B D front rear front rear Queue Queue Lưutrữ kế tiếp đốivớiQueue z Giảithuậtbổ sung vào Queue đượclưutrữ trong vector Q gồmn phầntử và đượctổ chứcdướidạng thường Procedure ENQUEUE(Q,F,R,X) Begin 1. if (R >= n) then begin write(‘QUEUE TRÀN’); return; end; 2. {Q rỗng} if F = 0 then F:= R:= 1; 3. else R:= R+ 1; 4. Q[R] := X; End Đỗ Bích Diệp - Khoa CNTT - ĐHBK Hà nội 13
14. Cấu trúc dữ liệu và Giải thuật Lưutrữ kế tiếp đốivớiQueue z Giảithuậtlấyra(loạibỏ ) khỏi Queue Procedure DEQUEUE(Q,F,R, Y) Begin { Y là biếnlưutrữ phầntửđượclấyra} 1. if F = 0 then begin write(‘QUEUE CẠN’); return; end; 2. Y:= Q[F]; {lưu giá trị củaphầntử cầnlấy} 3. if F = R=1 then F:= R:= 0; { Queue chỉ còn mộtphầntử} 4. else F:= F+ 1; End Lưutrữ kế tiếp đốivớiQueue z Bài tập: Hãy viếtgiảithuậtthựchiệnbổ sung và loạibỏ trên Queue lưutrữ kế tiếpdướidạng vòng Đỗ Bích Diệp - Khoa CNTT - ĐHBK Hà nội 14
15. Cấu trúc dữ liệu và Giải thuật Lưutrữ móc nối đốivới Queue – Cách tiếpcận1: Sử dụng danh sách nối đơn z Lốitrướccủa Queue là đầu danh sách z enqueue(o): bổ sung phầntử vào cuối danh sách z dequeue() : loạibỏ phầntửởđầu danh sách F R L Lốitrước Lối sau của của Queue Queue z Luôn nắmgiữ hai con trỏ F trỏ tớiphầntửởlốitrước của queue, R trỏ tớiphầntửởlốisaucủa queue Lưutrữ móc nối đốivới Queue – Cách tiếpcận2: z Lốisaucủa Queue là đầu danh sách z enqueue(o): bổ sung phầntử vào đầu danh sách z dequeue() : loạibỏ phầntửởcuối danh sách R F L Lốisau Lối trước của của Queue Queue Đỗ Bích Diệp - Khoa CNTT - ĐHBK Hà nội 15
16. Cấu trúc dữ liệu và Giải thuật Lưutrữ móc nối đốivới Queue z Giảithuậtbổ sung mộtphầntử vào Queue lưutrữ trong danh sách móc nối–Bổ sung vào cuối danh sách Procedure ENQUEUE(F,R,X) Begin 1. {Khởitạo nút mới} Call New(p); INFO(p) := X; LINK(p) := Null; 2. {Danh sách đã cho rỗng} if F = Null then F:= R:= p; 3. else LINK(R) := p; R:= p; End Lưutrữ móc nối đốivới Queue z Giảithuậtloạibỏ phầntử khỏi Queue – Loạibỏ phầntử đầu tiên trong danh sách Procedure DEQUEUE(F,R, Y) Begin { Y là biếnlưutrữ phầntửđượclấyra} 1. p:= F; Y:= INFO(p); 2. {Danh sách ban đầuchỉ có mộtphầntử} if (F = R) and (F <> Null) then F:= R:= Null; 2. else F:= LINK(p); 3. Call Dispose(p) ; End Đỗ Bích Diệp - Khoa CNTT - ĐHBK Hà nội 16
17. Cấu trúc dữ liệu và Giải thuật Hàng đợihaiđầu-DEQueue z DeQueue – Hàng đợi hai đầulàmộtcấutrúcdữ liệudạng hàng đợi nhưng nó hỗ trợ phép bổ sung và loạibỏởcảđầuvàcuối z Các hàm cơ sở củahàngđợi hai đầuD – insertFirst(o) – insertLast(o) : – removeFirst() – removeLast() z Các hàm khác – first() – last() – size() – isEmpty() – create() Hàng đợihaiđầu-DeQueue Thao tác Output DeQueue create() - [ ] insertFirst(5) - [5] insertFirst(3) - [3,5] removeFirst() 3 [5] insertLast(7) - [5,7] removeFirst() 3 [7] removeLast() 7 [] removeLast() error [] isEmpty() true [] insertLast(9) - [9] insertFirst(8) - [8,9] insertLast(7) - [8,9,7] size() 3 [8,9,7] Đỗ Bích Diệp - Khoa CNTT - ĐHBK Hà nội 17
18. Cấu trúc dữ liệu và Giải thuật Lưutrữ móc nốivới DeQueue z DeQueue đượclưutrữ sử dụng cấu trúc danh sách móc nối kép (Doubly Linked – List) – Mỗi nút trong danh sách ngoài trường INFO chứadữ liệucòncó2 trường con trỏ z PREV z NEXT – Cầnnắm được hai con trỏ, con trỏ L trỏ tớinútcực trái, con trỏ R trỏ tới nút cựcphảicủa danh sách – Với danh sách rỗng , L = R = NULL L BCGHR Lưutrữ móc nối đốivới DeQueue z Giảithuậtbổ sung phầntử vào đầumột DeQueue lưu trữ trong một danh sách nốikép z Giảithuậtloạibỏ phầntửđầumột DeQueue lưutrữ trong mộtdanhsáchnốikép Đỗ Bích Diệp - Khoa CNTT - ĐHBK Hà nội 18
19. Cấu trúc dữ liệu và Giải thuật Bài toán đổisố cơ số – Bài toán: Viếtmộtsố trong hệ thập phân thành số trong hệ cơ số b bấtkỳ z Ví dụ: – (356)10 = (101100100)2 – (356)10 = (544)8 – (356)10 = (164)16 Bài toán đổicơ số sử dụng Stack z Ví dụ: – (356)10 = (101100100)2 356 2 0 178 2 0 89 2 1 44 2 0 22 2 0 11 2 1 5 2 1 2 2 0 1 2 1 0 Đỗ Bích Diệp - Khoa CNTT - ĐHBK Hà nội 19
20. Cấu trúc dữ liệu và Giải thuật Bài toán đổicơ số sử dụng Stack – Thuật toán: z Đầu vào: Số n trong hệ thậpphân z Đầura: Số tương ứng với n trong hệđếmcơ số b z Thựchiện 1. Lấychữ số tạobởin%b. ĐẩyvàoStack 2. Thay n bằng n/b để tiếptụclấycácchữ số tiếp theo trong kếtquả 3. Lặplạibước 1 và 2 cho đếnkhikếtquả của phép chia là 0 4. Lầnlượtlấycácchữ số ra khỏi Stack và in chúng ra kết quả Bài toán đổicơ số sử dụng Stack 1 6 6 4 4 4 n= 356 n%16 = 4 n%16 = 6 n%16 = 1 Empty stack n = n/16 = 22 n = n/16 = 1 n = n/16 = 0 Đỗ Bích Diệp - Khoa CNTT - ĐHBK Hà nội 20
21. Cấu trúc dữ liệu và Giải thuật Bài toán đổicơ số sử dụng Stack Procedure CONVERT(n, b) Begin 1. m = N; 2. { Tính số dư và nạp vào stack S} while m 0 do begin call POP(S,T,X); {lấysố ra khỏi stack} write(X); end End Bài toán kiểmtracặpngoặc – Kiểmtracặp ngoặc Mỗidấu “(”, “{”, or “[” đềuphảicómộtdấu đóng tương ứng “)”, “}”, or “[” z Đúng: ( )(( )){([( )])} z Đúng : ((( )(( )){([( )])} z Sai: )(( )){([( )])} z Sai: ({[ ])} z Sai: ( – Viếtgiảithuậtnhậnmộtxâuđầuvàogồmcácký tự mở , đóng ngoặc. Kiểmtraxâucóhợplệ không Đỗ Bích Diệp - Khoa CNTT - ĐHBK Hà nội 21
22. Cấu trúc dữ liệu và Giải thuật Function ParenMatch(X,n): { X là mộtxâubaogồm n ký tự mở, đóng ngoặc. Giảithuậttrả ra giá trị true nếuxâuX chứamộtsố hợplệ cặp ngoặc, nếu không trả ra giá trị false} KhởitạoS làmộtstack rỗng for i =1 to n do begin if X[i] là mộtngoặcmở then S.push(X[i]) else if X[i] là một ngoặc đóng then begin if S.isEmpty() then return false {không có ngoặcmở tương ứng} if S.pop() không hợpkiểuvới X[i] then return false {cặp ngoặc đóng mở khác kiểu} end end if S.isEmpty() then return true { tấtcả cặp ngoặchợplệ} else return false {vẫntồntạimộtsố ngoặcmở mà không tìm thấy ngoặc đóng tương ứng} Biểuthứcsố họcvới ký pháp Balan z Thông thường, mộtbiểuthứcsố học đượcbiểudiễn theo ký pháp trung tố (infix notation) – Dấu phép toán (toán tử) nằmgiữa 2 toán hạng z A+B*C – Thứ tự thựchiện các phép toán đượcxácđịnh sử dụng các cặpdấungoặchoặcquyđịnh mộtthứ tựưutiêngiữacác phép toán z Biểuthức A* B^2 – C/D + E đượcthựchiện theo thứ tự sau B^2 Æ A*(B^2)ÆC/DÆ (A*(B^2)) –(C/D)Æ ((A*(B^2)) – (C/D)) + E – Tính toán giá trị biểuthứcsẽ khá phứctạp Đỗ Bích Diệp - Khoa CNTT - ĐHBK Hà nội 22
23. Cấu trúc dữ liệu và Giải thuật Biểuthứcsố họcvới ký pháp Balan z Có thể biểudiễncácbiểuthức mà không dùng đếndấu ngoặcsử dụng ký pháp tiềntố (prefix notation) hoặcký pháp hậutố (postfix notation) z Biểuthứcdạng tiềntố và hậutố – Trong ký pháp dạng tiềntố: Toán tử luôn được đặttrước 2 toán hạng Toán tử Toán hạng 1 Toán hạng 2 – Trong ký pháp dạng hậutố: Toán tử luôn đặt sau 2 toán hạng Toán hạng 1 Toán hạng 2 Toán tử Biểuthứcsố họcvới ký pháp Balan Dạng trung tố Dạng tiềntố Dạng hậutố A+B + A B A B + (A+B) * C * + A B C A B + C * A + B* C + A * B C A B C * + (A + B ) / (C-D) / + A B – C D A B + C D - / A + B / C – D - + A / B C D A B C/ + D - Đỗ Bích Diệp - Khoa CNTT - ĐHBK Hà nội 23
24. Cấu trúc dữ liệu và Giải thuật Bài toán tính giá trị củabiểuthứcdạng hậutố z Tính giá trị củamộtbiểuthứcdạng hậutố sử dụng Stack – Đầuvào: Xâukýtự biểudiễnbiểuthứcdạng hậutố z A B + C – D E * / z Các giá trị của các biếnsố z Các bước chính trong giảithuật – Đọcbiểuthứcdạng hậutố từ trái qua phải – Nếukýtự được đọclàmột toán hạng thì lưugiátrị vào stack – Nếukýtự được đọclàmột toán tử X thì lầnlượtlấytừ stack ra 2 giá trị, thựchiệnphéptoánX với2 giátrịđó, nạpkết quả vào stack – Thựchiệncácbướctrênđến khi toàn bộ biểuthức đã được đọc Bài toán tính giá trị củabiểuthứcdạng hậutố Procedure EVALUATE (P, VAL) Begin { P là biểuthứcdạng hậutố cần tính, VAL là biếnsẽ lưugiátrị tính được} 1. Ghi thêm dấu‘)’vàocuốiP để đánh dấu điểmkếtthúc 2. repeat Đọckýtự X trong P (lầnlượttừ trái sang phải) ; if X là mộttoánhạng then call PUSH(S, T, X) ; else begin call POP(S, T, Y) ; call POP(S, T, Z); Thựchiệnphéptoánvới hai toán hạng Z,Y kếtquả là W; call PUSH (S, T, W) ; end; until Gặpdấukết thúc xâu ‘)’ ; 3. call POP (S,T, VAL); End Đỗ Bích Diệp - Khoa CNTT - ĐHBK Hà nội 24
25. Cấu trúc dữ liệu và Giải thuật Bài toán tính giá trị củabiểuthứcdạng hậutố z Ví dụ: A B + C – D E * / với A = 5, B = 14, C = 1, D = 2, E = 3 Ký tự được đọc A B + C - D E * / 5+14 19-1 2*3 18/6 Stack 3 14 1 2 2 6 5 5 19 19 18 18 18 18 3 VAL Chuyểnbiểuthứcdạng trung tố sang dạng hậutố – Bài toán z Xét biểuthứcsố họcdạng trung tố gồm các phép toán cộng, trừ, nhân, chia, lũythừa và các dấungoặc z Viếtbiểuthứcdạng hậutố tương ứng vớibiểuthức trung tốđầuvào – Để thựchiện, trong biểuthức trung tố cầnbiết z Thứ tựưutiêncủa các phép toán : Lũythừa Æ Nhân, Chia Æ Cộng, Trừ z Qui tắckếthợp: Nếu có hai phép toán cùng thứ tựưu tiên – Lũythừa: Phảitrước, trái sau. 2^3^4 = 2^(3^4) – Các phép toán khác : Trái trước, phảisau z Dầungoặc: Ưutiênnhất Đỗ Bích Diệp - Khoa CNTT - ĐHBK Hà nội 25
26. Cấu trúc dữ liệu và Giải thuật Chuyểnbiểuthứcdạng trung tố sang dạng hậutố – Thựchiện z Duyệtbiểuthức trung tố từ trái sang phải – Gặp toán hạng Æ Đưara – Gặp phép toán Æ Cần đợi toán hạng số 2 Æ Phảilưulại z Sử dụng Stack để lưutrữ z Cầnxácđịnh các trường hợp để đưa phép toán ra cho chính xác Chuyểnbiểuthứcdạng trung tố sang dạng hậutố z Tình huống: – Có các phép toán đang đượclưutrữ trong Stack – Khi duyệtbiểuthứcdạng trung tố, đang gặpphảimột phép toán khác – Xác định các trường hợp để đưa phép toán từ Stack ra cho chính xác vớibiểuthứcdạng hậutố z Giải pháp: So sánh phép toán đang xét với phép toán đượclưu ởđỉnh Stack về thứ tựưu tiên , qui tắckết hợp Đỗ Bích Diệp - Khoa CNTT - ĐHBK Hà nội 26
27. Cấu trúc dữ liệu và Giải thuật Chuyểnbiểuthứcdạng trung tố sang dạng hậutố – Qui tắc đưa các phép toán khỏi Stack: z Qui tắccơ bản: Nếu phép toán đang xét có thứ tựưu tiên thấphơn phép toán ởđỉnh Stack Æ Đưa phép toán ởđỉnh Stack ra + * 1+2 * 3 1*2 + 3 Đã đưara1 2 Đã đưara1 2 Đang xét * Đang xét + Không đưa+ ra Đưa* ra Chuyểnbiểuthứcdạng trung tố sang dạng hậutố – Qui tắc khi có hai phép toán cùng mức ưutiên z Nếuphéptoáncótínhchất kếthợptrái(cộng, trừ , nhân, chia ) thì đưa phép toán ởđỉnh ngănxếpra 1 – 2 + 3 Đang xét + Đưa–ra - Hậutố tương ứng 1 2 – 3 + z Nếuphéptoáncótínhchấtkếthợpphải(lũythừa) thì không đưa phép toán ởđỉnh ngănxếpra 2 ^ 3 ^ 4 Đang xét ^ thứ 2 Không đưa^ ởđỉnh Stack ra ^ Hậutố tương ứng 2 3 4 ^ ^ Đỗ Bích Diệp - Khoa CNTT - ĐHBK Hà nội 27
28. Cấu trúc dữ liệu và Giải thuật Chuyểnbiểuthứcdạng trung tố sang dạng hậutố – Trường hợp hàng loạt phép toán dờingănxếp 1 + 2 * 3 – 4 Đang xét – * Phải đưara* rồi+ Hậutố 1 2 3 * + 4 - + – Dấungoặc: z Khi đọcmở ngoặc, đẩy vào Stack , không đưabấtkỳ phép toán nào ra z Khi dấumở ngoặc trong Stack sẽ không đưanórakhiđang xét các phép toán z Khi đọc đóng ngoặc, đưatấtcả các phép toán trong Stack ra cho đếnkhigặpdầumở ngoặc z Các dấungoặc không đưa vào trong biểuthứchậutố Chuyểnbiểuthứcdạng trung tố sang dạng hậutố – Các bước trong giảithuật Duyệtbiểuthức trung tố từ trái sang phải 1. Gặp toán hạng đưarangay 2. Gặpdấu( Æ Đưa vào ngănxếp 3. Gặpdấu) Æ đưa các phầntử ra khỏingănxếpchođến khi gặpdấu ( , dấu( đượclấyrakhỏingănxếp 4. Nếugặpdấu phép toán : so sánh độ ưutiêncủaphép toán đang xét và phép toán ởđỉnh củastack z Nếuphéptoánđang xét có độ ưutiênlớnhơn phép toán ởđỉnh stack hoặc phép toán đang xét có độ ưu tiên bằng phép toán ởđỉnh và đólàphéptoán^, đẩy phép toán đang xét vào đỉnh stack z Nếu không, đưalầnlượt phép toán ởđỉnh stack ra cho đếnkhithấymột phép toán tại đỉnh stack có độ ưutiênthấphơn phép toán đang xét. z Đẩy phép toán đang xét vào đỉnh stack 5. Kết thúc biểuthức Æ Đưanốt các phép tóan trong ngăn xếpra Đỗ Bích Diệp - Khoa CNTT - ĐHBK Hà nội 28
29. Cấu trúc dữ liệu và Giải thuật (A + B - C) / D * E + + - ( ( ( ( / / * * A B + C - D / E * Đỗ Bích Diệp - Khoa CNTT - ĐHBK Hà nội 29