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

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

1. Hiện thực stack liên tục 11 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 2: Stack
2. Khai báo stack liên tục const int maxstack = 10; //small number for testing template class Stack { public: Stack( ); bool empty( ) const; Error_code pop( ); Error_code top(Entry &item) const; Error_code push(const Entry &item); private: int count; Entry entry[maxstack]; }; 12 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 2: Stack
3. Đẩy một phần tử vào stack Giải thuật: 1. Nếu còn chỗ trống trong stack 1.1. Tăng vị trí đỉnh lên 1 1.2. Chứa giá trị vào vị trí đỉnh của stack 1.3. Tăng số phần tử lên 1 7 top 5 1 count=3count=2 13 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 2: Stack
4. Bỏ phần tử trên đỉnh stack Giải thuật: 1. Nếu còn phần tử trong stack 1.1. Giảm vị trí đỉnh đi 1 1.2. Giảm số phần tử đi 1 top 7 5 1 count=2count=3 14 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 2: Stack
5. Thêm/Bỏ phần tử - Mã C++ template Error_code Stack :: push(const Entry &item) { if (count >= maxstack) return overflow; else entry[count++] = item; return success; } template Error_code Stack :: pop() { if (count == 0) return underflow; else count ; return success; } 15 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 2: Stack
6. Lấy giá trị trên đỉnh stack Giải thuật: 1. Nếu còn phần tử trong stack 1.1. Trả về giá trị tại vị trí đỉnh Mã C++: template Error_code Stack :: top(Entry &item) { if (count == 0) return underflow; else item = entry[count - 1]; return success; } 16 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 2: Stack
7. Reverse Polish Calculator Mô tả bài toán: Các toán hạng được đọc vào trước và đẩy vào stack Khi đọc vào toán tử, lấy hai toán hạng ra từ stack, tính toán với toán tử này, rồi đẩy kết quả vào stack Thiết kế phần mềm: Cần một stack để chứa toán hạng Cần hàm get_command để nhận lệnh từ người dùng Cần hàm do_command để thực hiện lệnh 17 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 2: Stack
8. Reverse Polish Calculator – Thiết kế chức năng Tập lệnh: ‘?’: đọc một giá trị rồi đẩy vào stack Toán tử ‘+’, ‘-’, ‘*’, ‘/’: lấy 2 giá trị trong stack, tính toán và đẩy kết quả vào stack Toán tử ‘=’: in đỉnh của stack ra ‘q’: kết thúc chương trình 18 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 2: Stack
9. Reverse Polish Calculator – Ví dụ Tính toán biểu thức: 3 5 + 2 * = 5 5 3 3 3 8 Ban đầu Toán tử ? Toán tử ? Toán tử + Đẩy 8 vào Nhập vào 3 Nhập vào 5 Lấy ra 5 và 3 Tính 3 + 5 => 8 2 2 8 8 16 16 Toán tử ? Toán tử * Đẩy vào 16 Toán tử = Nhập vào 2 Lấy ra 2 và 8 In ra 16 Tính 8 * 2 => 16 19 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 2: Stack
10. Reverse Polish Calculator – Hàm get_command char get command( ) { char command; bool waiting = true; cout :"; while (waiting) { cin >> command; command = tolower(command); if (command == ‘?’ || command == ‘=‘ || command == ‘+’ || command == ‘−’|| command == ‘*’ || command == ‘/’ || command == ‘q’) waiting = false; else { cout << "Please enter a valid command:" << endl << "[?]push to stack [=]print top" <<endl << "[+] [−] [*] [/] are arithmetic operations" << endl << "[Q]uit." << endl; } } return command; } 20 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 2: Stack
11. Reverse Polish Calculator – Giải thuật tính toán với toán tử Algorithm Op_process Input: toán tử op, stack chứa các toán hạng Output: stack chứa các toán hạng sau khi tính xong toán tử op 1. Nếu stack không rỗng 1.1. Lấy đỉnh stack ra thành p 1.2. Bỏ phần tử trên đỉnh stack 1.3. Nếu stack rỗng 1.3.1. Đẩy p ngược lại 1.3.2. Báo lỗi và thoát 1.4. Lấy đỉnh stack ra thành q 1.5. Bỏ phần tử trên đỉnh stack 1.6. Tính toán (q op p) 1.7. Đẩy kết quả vào stack End Op_process 21 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 2: Stack
12. Reverse Polish Calculator – Mã C++ cho toán tử cộng if (numbers.top(p) == underflow) cout << "Stack rỗng"; else { numbers.pop( ); if (numbers.top(q) == underflow) { cout << "Stack chỉ có 1 trị”; numbers.push(p); } else { numbers.pop( ); if (numbers.push(q + p) == overflow) cout << "Stack đầy”; } } 22 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 2: Stack
13. Reverse Polish Calculator – Chương trình chính #include "stack.cpp" //prototype void introduction( ); void instructions( ); char get_command( ); bool do_command(char command, Stack &numbers); int main( ) { Stack stored_numbers; introduction( ); instructions( ); while (do_command(get_command( ), stored_numbers)); } //implementation 23 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 2: Stack
14. Reverse Polish Calculator – Hàm do_command bool do_command(char command, Stack &numbers) { double p, q; switch (command) { case '?’: cout > p; if (numbers.push(p) == overflow) cout << "Warning: Stack full, lost number" << endl; break; case '=‘: if (numbers.top(p) == underflow) cout << "Stack empty" << endl; else cout << p << endl; break; // Add options for further user commands. case ‘q’: cout << "Calculation finished.\n"; return false; } return true; } 24 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 2: Stack