Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 10: Ứng dụng của ngăn xếp - Ngô Hữu Phước

Giảng viên: TS. Ngo Huu Phuc Tel: 0438 326 077 Mob: 098 5696 580 Email: ngohuuphuc76@gmail.com Cấu trúc dữ liệu và giải thuật Bài 10: Ứng dụng của ngăn xếp PhD. Ngo Huu Phuc, Le Quy Don Technical University1 Bài 10. Một vài ứng dụng của Stack Nội dung: 10.1. Đảo mảng (3) 10.2. Đảo chuỗi (4) 10.3. Chuyển đổi hệ số (9) 10.4. Bracket Matching (5) 10.5. Balancing Act (4) Tham khảo: 1. Data structures and Algorithms Stacks.htm 2. Kyle Loudon Mastering Algorithms, Chapter 6 Stacks and Queues 3. Elliz Horowitz – Fundamentals of Data Structures, Chapter 3 Stacks and Queues 4. Deshpande Kakle – C and Data Structures, Chapter 19. Stacks and Queues 5. Bài giảng TS Nguyễn Nam Hồng PhD. Ngo Huu Phuc, Le Quy Don Technical University2 10.1. Đảo mảng (1/3)  Cho một mảng gồm một dãy các giá trị.  Để đảo thứ tự các phần tử trong mảng, sử dụng nguyên lý Last-In-First-Out của Stack.  Ví dụ về hoạt động của đảo mảng: PhD. Ngo Huu Phuc, Le Quy Don Technical University3 17 23 25 18 18 25 23 17 134 47 55 216 216 55 47 134 10.1. Đảo mảng (2/3) Ý tưởng thực hiện giải thuật: 1. Khởi tạo một Stack rỗng, có kiểu số. 2. Với n phần tử của mảng, lần lượt đưa vào Stack thông qua hàm Push: Push a[i] in to Stack. 3. Lần lượt lấy ra từ Stack n phần tử và đưa vào trở lại mảng ban đầu: Pop a item from nStack in to a[i]. 4. Kết thúc giải thuật. PhD. Ngo Huu Phuc, Le Quy Don Technical University4 10.1. Đảo mảng (3/3) Ví dụ về đảo mảng: void revArray(int a[],int n,int stack[]) { makeEmpty(stack); for(int i=0;i<n;i++) push(stack,a[i]); for(int i=0;i<n;i++) a[i]=pop(stack); } PhD. Ngo Huu Phuc, Le Quy Don Technical University5 10.2. Đảo chuỗi (1/4)  Cho một chuỗi gồm nhiều từ.  Đảo chuỗi thực hiện việc đảo các từ trong chuỗi, sử dụng ý tưởng Last-In-First-Out của Stack.  Ví dụ về đảo chuỗi: PhD. Ngo Huu Phuc, Le Quy Don Technical University6 Tôi Làm Bài Tập Tập Bài Làm Tôi Chăm Học Thì Giỏi Giỏi Thì Học Chăm 10.2. Đảo chuỗi (2/4) Ý tưởng xây dựng chương trình: 1. Tạo một wStack rỗng. 2. Với mỗi từ mWord đọc được từ string, đưa từ đó vào Stack: Push mWord into wStack. 3. Đọc từ wStack cho đến hết, thực hiện: Pop a word from wStack into mWord. Concate mWord to the end of outp string. 4. Dừng giải thuật. Chú ý: cần xây dựng hàm tách word từ string. PhD. Ngo Huu Phuc, Le Quy Don Technical University7 10.2. Đảo chuỗi (3/4) PhD. Ngo Huu Phuc, Le Quy Don Technical University8 #include #include #include #include "string.h" #define MAXSIZE 100 #define MAX 100 void push(char* stack[], char* value, int* top); char* pop(char* stack[], int* top); void main() { char* stack[MAXSIZE]; int top=-1; char mString[MAX]; char* mWord; printf("Nhap vao mot chuoi: "); gets(mString); mWord = strtok(mString," "); push(stack,mWord,&top); for(int i=1; i<strlen(mString); i++) { mWord = strtok(NULL," "); if(mWord) push(stack,mWord,&top); } char *p=pop(stack,&top); while(top>=0) { p=strcat(p," "); p=strcat(p,pop(stack,&top)); } printf("Chuoi ket qua \n"); puts(p); getch(); } 10.2. Đảo chuỗi (4/4) PhD. Ngo Huu Phuc, Le Quy Don Technical University9 void push(char* stack[], char* value, int* top) { if(*top < MAXSIZE) { *top=*top+1; stack[*top]=(char*)malloc(strlen(value)); strcpy(stack[*top],value); } else { printf("Khong the them vao STACK\n"); getch(); } } char* pop(char* stack[], int* top) { char* value; if(*top>=0) { value=(char*)malloc(strlen(stack[*top])); strcpy(value,stack[*top]); *top=*top-1; } else { printf("STACK rong\n"); value = NULL; } return value; } void makeEmpty(int* top) { *top=-1; } 10.3. Chuyển đổi hệ số (1/9)  Các hệ số hay sử dụng: hệ thập phân (Decimal), hệ nhị phân (Binary), hệ 16 (Hexadecimal).  Con người thường sử dụng hệ thập phân.  Đối với máy tính, thường sử dụng hệ nhị phân.  Hệ 16 là hệ trung gian giữa hệ thập phân và hệ nhị phân.  Ví dụ: 111 = (01101111)B = (6F)H PhD. Ngo Huu Phuc, Le Quy Don Technical University10 10.3. Chuyển đổi hệ số (2/9) Việc chuyển đổi giữa các hệ số thường xét: 1. Chuyển đổi từ hệ thập phân sang hệ nhị phân. 2. Chuyển đổi từ hệ nhị phân sang hệ thập phân. 3. Chuyển đổi từ hệ thập phân sang hệ 16. 4. Chuyển đổi từ hệ 16 sang hệ thập phân. PhD. Ngo Huu Phuc, Le Quy Don Technical University11 10.3. Chuyển đổi hệ số (3/9) Ý tưởng chuyển đổi từ hệ thập phân sang hệ nhị phân sử dụng Stack:  Khởi tạo một Stack rỗng.  Chuyển đổi số từ dạng thập phân sang nhị phân bằng phép div và mod cho 2.  Kết quả của phép mod được đưa vào Stack.  Đọc từ Stack cho đến hết, kết quả được nối với nhau để tạo thành chuỗi.  Kết thúc giải thuật. PhD. Ngo Huu Phuc, Le Quy Don Technical University12 10.3. Chuyển đổi hệ số (4/9) PhD. Ngo Huu Phuc, Le Quy Don Technical University13 Các hàm chính Dec to Binary: char* DecToBin(int a, char stack[]) { makeEmpty(stack); int n=0; while(a>0) { push(stack,a%2+'0'); a=a/2; n++; } char* mString; mString = (char*) malloc(n); int i=0; while(stack[0]>0) { mString[i]=pop(stack); i++; } mString[i]='\0'; return mString; } void push(char stack[], char value) { if(stack[0] < MAXSIZE) { stack[0]++; stack[stack[0]]= value; } else { printf("Khong the them vao STACK\n"); getch(); } } char pop(char stack[]) { char value; if(stack[0]>0) { value=stack[stack[0]]; stack[0]--; } else { printf("STACK rong\n"); value = -1; } return value; } 10.3. Chuyển đổi hệ số (3/9) Ý tưởng chuyển đổi từ hệ thập phân sang hệ 16 sử dụng Stack:  Khởi tạo một Stack rỗng.  Chuyển đổi số từ dạng thập phân sang nhị phân bằng phép div và mod cho 16.  Kết quả của phép mod được đưa vào Stack.  Đọc từ Stack cho đến hết, kết quả được nối với nhau để tạo thành chuỗi.  Kết thúc giải thuật. PhD. Ngo Huu Phuc, Le Quy Don Technical University14 10.3. Chuyển đổi hệ số (4/9) PhD. Ngo Huu Phuc, Le Quy Don Technical University15 Các hàm chính Dec to Hex: char* DecToHex(int a, char stack[]) { makeEmpty(stack); int n=0; while(a>0) { int t = a%16; if(t>=0 && t<=9) push(stack,t+'0'); else push(stack,t-10+'A'); a=a/16; n++; } char* mString; mString = (char*) malloc(n); int i=0; while(stack[0]>0) { mString[i]=pop(stack); i++; } mString[i]='\0'; return mString; } 10.4. Bracket Matching (1/6)  Một biểu thức sử dụng dấu ngoặc (Bracket) đúng nếu: • với mỗi dấu ngoặc trái sẽ có 1 dấu ngoặc phải gần nhất khớp với nó. • với mỗi dấu ngoặc phải sẽ có 1 dấu ngoặc trái gần nhất (bên trái) khớp với nó. • một đoạn biểu thức nằm giữa một cặp dấu ngoặc trái, phải được gọi là sử dụng đúng dấu ngoặc. PhD. Ngo Huu Phuc, Le Quy Don Technical University16 10.4. Bracket Matching (2/6)  Ví dụ về sử dụng dấu ngoặc trong biểu thức toán học: s * (s – a) * (s – b) * (s – c) → Well (– b + (b2 – 4*a*c)^0.5) / 2*a → Well s * (s – a) * (s – b * (s – c) → ??? s * (s – a) * s – b) * (s – c) → ??? (– b + (b^2 – 4*a*c)^(0.5/ 2*a)) → ??? PhD. Ngo Huu Phuc, Le Quy Don Technical University17 10.4. Bracket Matching (3/6) Giải thuật kiểm tra sử dụng dấu ngoặc: 1. Tạo một bStack rỗng (Stack chứa dấu ngoặc). 2. Với mỗi ký hiệu sym trong đoạn (từ trái sang phải) : 2.1. Nếu sym là dấu ngoặc trái: 2.1.1. Đưa sym vào bStack. 2.2. Nếu sym là dấu ngoặc phải: 2.2.1. Nếu bStack rỗng, return false. 2.2.2. Lấy dấu ngoặc ở bStack, đưa vào biến left. 2.2.3. Nếu left và sym không khớp được với nhau, return false. 3. Dừng giải thuật, trả về True nếu bStack rỗng, hoặc False với các trường hợp khác. PhD. Ngo Huu Phuc, Le Quy Don Technical University18 10.4. Bracket Matching (4/6) PhD. Ngo Huu Phuc, Le Quy Don Technical University19 #include #include #include #include "string.h" #define MAXSIZE 100 #define MAX 100 void push(char bStack[], char value, int *top); char pop(char bStack[], int *top); int isEmpty(char bStack[],int top); int isFull(char bStack[], int top); void makeEmpty(int bStack[],int* top); int bracketMatching(char* a,char bStack[], int *top); void main() { char bStack[MAXSIZE]; char a[MAX]; int top=-1; printf("Doc vao mot bieu thuc: "); gets(a); if(bracketMatching(a,bStack,&top)) printf("Bieu thuc su dung DUNG dau ngoac\n"); else printf("Bieu thuc su dung KHONG DUNG dau ngoac\n"); getch(); } 10.4. Bracket Matching (5/6) PhD. Ngo Huu Phuc, Le Quy Don Technical University20 int bracketMatching(char* a,char bStack[],int *top) { int kt=1; for(int i=0;i<strlen(a);i++) { if(a[i]=='(') push(bStack,a[i],top); if(a[i]==')') { if(isEmpty(bStack,*top)) kt=0; else char ch=pop(bStack,top); } } if(!isEmpty(bStack,*top)) kt=0; return kt; } void push(char bStack[], char value, int *top) { if(*top<MAXSIZE) { *top = *top + 1; bStack[*top] = value; } else { printf("Khong the them vao STACK\n"); getch(); } } 10.4. Bracket Matching (6/6) PhD. Ngo Huu Phuc, Le Quy Don Technical University21 char pop(char bStack[], int *top) { char value; if(*top>=0) { value = bStack[*top]; *top = *top - 1; } else { printf("STACK rong\n"); value = 0; } return value; } int isEmpty(char bStack[],int top) { if(top==-1) return 1; else return 0; } int isFull(char bStack[],int top) { if(top==MAXSIZE-1) return 1; else return 0; } void makeEmpty(char bStack[], int *top) { *top=-1; } 10.5. Balancing Act (1/4)  Với phương pháp trước mới chỉ đảm bảo được khớp dấu ngoặc ‘(‘ và ‘)’.  Trong thực tế, còn có nhiều dấu ngoặc khác cần khớp như: ‘(‘ và ‘)’; ‘[‘ và ‘]’; ‘{‘ và ‘}’.  Như vậy, trong giải thuật trên, cần lưu ý thêm quá trình push và pop vào bStack:  Nếu quá trình push vào bStack có dạng: (, [, {.  Quá trình pop từ bStack cần đúng thứ tự: }, ], ).  Nếu đã duyệt xong biểu thức và bStack rỗng → return True, ngược lại, return False. PhD. Ngo Huu Phuc, Le Quy Don Technical University22 10.5. Balancing Act (2/4) PhD. Ngo Huu Phuc, Le Quy Don Technical University23 void main() { char bStack[MAXSIZE]; char a[MAX]; int top=-1; printf("Doc vao mot bieu thuc: "); gets(a); if(balancingAct(a,bStack,&top)) printf("Bieu thuc su dung DUNG dau ngoac\n"); else printf("Bieu thuc su dung KHONG DUNG dau ngoac\n"); getch(); } int balancingAct(char* a,char bStack[],int *top) { int kt=1; for(int i=0;i<strlen(a);i++) { if(a[i]=='(' || a[i]=='[' || a[i] == '{') push(bStack,a[i],top); if(a[i]==')' || a[i]=='}' || a[i]==']') { if(isEmpty(bStack,*top)) kt=0; else { char ch=pop(bStack,top); if(!matching(ch,a[i])) kt=0; } } } if(!isEmpty(bStack,*top)) kt=0; return kt; } 10.5. Balancing Act (3/4) PhD. Ngo Huu Phuc, Le Quy Don Technical University24/24 int matching(char a, char b) { int kt=0; if(a=='(' && b==')') kt=1; if(a=='[' && b==']') kt=1; if(a=='{' && b=='}') kt=1; return kt; }