Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 11: Ký pháp nghịch đảo Balan (Reverse Polish Notation) - 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 11: Ký pháp nghịch đảo Balan (Reverse Polish Notation) PhD Ngo Huu Phuc, Le Quy Don Technical University1 Bài 11: Ký pháp nghịch đảo Balan Nội dung: 11.1. Reverse Polish Notation (RPN) (6) 11.2. Chuyển đổi biểu dạng Infix sang RPN (7) 11.3. Ví dụ về chuyển đổi từ Infix sang RPN (9) 11.4. Prefix Notation (3) 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 11.1. Ký pháp nghịch đảo Balan (RPN) Nội dung phần 11.1: 11.1.1. Khái niệm về Ký pháp nghịch đảo Balan (RPN) 11.1.2. Tại sao sử dụng Ký pháp nghịch đảo Balan? 11.1.3. Một số ví dụ về Ký pháp nghịch đảo Balan. PhD Ngo Huu Phuc, Le Quy Don Technical University3 11.1.1. Khái niệm về Ký pháp nghịch đảo Balan  Ký pháp nghịch đảo Balan, còn được gọi là Postfix, do Charles Hamblin đề xuất vào những năm 1950s  Ký pháp này lấy ý tưởng của Polish notation, được đề xuất vào năm 1920 của nhà toán học người Balan có tên Jan Łukasiewicz. (Trong một số tài liệu còn gọi là ký pháp Łukasiewicz). PhD Ngo Huu Phuc, Le Quy Don Technical University4 Dạng Infix Dạng Postfix Dạng Prefix A-B/(C+D) ABCD+/- –A/B+CD 11.1.2. Tại sao sử dụng RPN? (1/3) RPN cho phép giảm thời gian trong việc tính một biểu thức. Người dùng không cần quan tâm đến dấu ngoặc trong biểu thức. Với ký pháp này cho phép thấy kết quả ngay sau phép toán. Với ký pháp này, việc thực hiện trên máy tính tỏ ra hiệu quả hơn!!! PhD Ngo Huu Phuc, Le Quy Don Technical University5 11.1.2. Tại sao sử dụng RPN?(2/3) Với việc cho thấy kết quả ngay, do đó, người sử dụng có thể kiểm tra kết quả dễ hơn, nhanh hơn. Với cách viết này, việc tính toán dựa trên thứ tự của biểu thức, kết hợp với thứ tự ưu tiên của phép toán. RPN có tính logic cao vì người dùng đưa biểu thức, sau đó đưa phép tính cần thực hiện. PhD Ngo Huu Phuc, Le Quy Don Technical University6 11.1.2. Tại sao sử dụng RPN?(3/3) Xem xét một biểu thức đại số dạng Infix sau: 1 + 2 * 3 = ? Kết quả là 7 hay 9? Trả lời: kết quả là 7 vì phép * có độ ưu tiên cao hơn phép +. Xem xét ví dụ: (1+2) * 3? Kết quả là 9. Rõ ràng, với dạng ký pháp này, người dùng dễ nhầm lẫn trong tính toán!!! PhD Ngo Huu Phuc, Le Quy Don Technical University7 11.1.3. Một số ví dụ về RPN (1/2) Xem xét ký pháp RPN sau: 4 5 + 6 *  Kết quả của biểu thức là bao nhiêu?  4 5 + → 4 + 5 = 9  9 6 * → 9 * 6 = 54 Biểu thức 4 5 + 6 * tương tự như biểu thức dạng Infix (4+5)*6. Các bước thực hiện: 1. 4 5 + 6 * 2. 9 6 * 3. 54 PhD Ngo Huu Phuc, Le Quy Don Technical University8 11.1.3. Một số ví dụ về RPN(2/2) Xem xét biểu thức dạng Postfix: 6 4 5 + *  Kết quả của biểu thức bằng?  4 5 + → 4 + 5 = 9  6 9 * → 6 * 9 = 54 Biểu thức 6 4 5 + * tương đương với biểu thức dạng Infix: 6 * (4 + 5). Các bước thực hiện: 1. 6 4 5 + * 2. 6 9 * 3. 54 PhD Ngo Huu Phuc, Le Quy Don Technical University9 11.2. Chuyển đổi biểu dạng Infix sang RPN 11.2.1. Ví dụ về chuyển đổi biểu thức dạng Infix sang RPN. 11.2.2. Thuật toán chuyển đổi biểu thức dạng Infix sang RPN. 11.2.3. Chương trình chuyển đổi biểu thức dạng Infix sang dạng RPN. PhD Ngo Huu Phuc, Le Quy Don Technical University10 11.2.1. Ví dụ về chuyển đổi biểu thức dạng Infix sang RPN  Cho biểu thức dạng Infix: (4 + 5) / (6 + 7) Làm thế nào để chuyển đổi từ dạng Infix sang RPN? 4 5 + 6 7 + / Cho biểu thức dạng Infix: ((4+5)*(2+3)+6)/(8+7) Cần gõ phím bao nhiêu lần? 21 Kết quả của phép biến đổi sang RPN? 4 5 + 2 3 + * 6 + 8 7 + / Với dạng RPN, cần gõ phím 13 lần. PhD Ngo Huu Phuc, Le Quy Don Technical University11 11.2.2. Thuật toán chuyển đổi biểu thức dạng Infix sang RPN (1/4) Thuật toán thứ nhất: chuyển đổi biểu thức từ Infix sang Postfix:  Bước 1 : Đọc một thành phần của biểu thức E (dạng Infix biểu diễn bằng xâu, đọc từ trái qua phải). Giả sử thành phần đọc được là x 1.1. Nếu x là toán hạng thì viết nó vào bên phải biểu thức E1 (xâu lưu kết quả của Postfix) 1.2. Nếu x là dấu ‘(’ thì đẩy nó vào Stack. 1.3. Nếu x là một trong các phép toán +, -, *, / thì 1.3.1. Xét phần tử y ở đỉnh Stack. 1.3.2. Nếu Pri(y)>=Pri(x) là một phép toán thì loại y ra khỏi Stack và viết y vào bên phải của E1 và quay lại bước 1.3.1 1.3.3. Nếu Pri(y)<Pri(x) thì đẩy x vào Stack. PhD Ngo Huu Phuc, Le Quy Don Technical University12 11.2.2. Thuật toán chuyển đổi biểu thức dạng Infix sang RPN (2/4) 1.4. Nếu x là dấu ‘)’ thì 1.4.1. Xét phần tử y ở đầu của Stack. 1.4.2. y là phép toán thì loại y ra khỏi Stack, viết y vào bên phải E1 và quay trở lại 1.4.1 1.4.3. Nếu y là dấu ‘(’ loại y ra khỏi Stack.  Bước 2 : Lập lại bước 1 cho đến khi toàn bộ biểu thức E được đọc qua  Bước 3 :Loại phần tử ở đỉnh Stack và viết nó vào bên phải E1. Lặp lại bước này cho đến khi Stack rỗng.  Bước 4: Tính giá trị của biểu thức dưới dạng hậu tố Chú ý: Hàm Pri(‘$’)<Pri(‘(‘)<Pri(‘+‘)=Pri(‘-‘)<Pri(‘*‘)=<Pri(‘/‘) $ ký hiệu đỉnh của Stack PhD Ngo Huu Phuc, Le Quy Don Technical University13 11.2.2. Thuật toán chuyển đổi biểu thức dạng Infix sang RPN (3/4) Thuật toán thứ hai: Tính giá trị biểu thức dạng Postfix:  Bước 1 : Đọc lần lượt các phần tử của biểu thức E1 (từ trái qua phải)  Nếu gặp toán hạng thì đẩy nó vào Stack.  Nếu gặp phép toán thì lấy hai phần tử liên tiếp trong Stack thực hiện phép toán, kết quả được đẩy vào trong Stack.  Bước 2 : Lập lại bước 1 cho đến khi hết tất cả các phần tử trong biểu thức E1. lúc đó đỉnh của Stack chứa giá trị của biểu thức cần tính  Bước 3. Kết thúc. PhD Ngo Huu Phuc, Le Quy Don Technical University14 11.3. Ví dụ về chuyển đổi từ Infix sang RPN (1/2) Cho biểu thức: E=a*(b+c)-d/e#. PhD Ngo Huu Phuc, Le Quy Don Technical University15 E S E1 $ a $ a * $* a ( $*( a b $*( ab + $*(+ ab c $*(+ abc ) $*( abc+ E S E1 $* abc+ - $ abc+* $- abc+* d $- abc+*d / $-/ abc+*d e $-/ abc+*de # $- abc+*de/ $ abc+*de/- 11.3. Ví dụ về tính biểu thức dạng RPN (2/2) Xét biểu thức dạng RPN: 4 5 + 2 3 + * 6 + 8 7 + / PhD Ngo Huu Phuc, Le Quy Don Technical University16 51 8 7 4 4 5 4 5 9 9 2 9 2 3 9 2 3 9 5 9 5 45 45 6 45 6 51 51 8 51 8 7 51 15 51 15 3.4 + + * + + / 11.3. Chương trình minh họa (1/5) PhD. Ngo Huu Phuc, Le Quy Don Technical University17 #include "stdio.h" #include "conio.h" #include "string.h" #include "ctype.h“ #define MAX 50 struct infix { char target[MAX] ; char stack[MAX] ; char *s, *t ; int top ; }; void initinfix (struct infix *); void setexpr (struct infix *, char *); void push (struct infix *, char); char pop (struct infix *); void convert (struct infix *); int priority (char); void show (struct infix); void main() { struct infix p; char expr[MAX]; initinfix(&p); printf ("\nNhap bieu thuc dang Infix: "); gets(expr) ; setexpr(&p, expr); convert(&p); printf ( "\nBieu thuc dang Postfix: " ) ; show(p); getch(); } 11.3. Chương trình minh họa (2/5) PhD. Ngo Huu Phuc, Le Quy Don Technical University18 /* Khoi tao cau truc dang Infix */ void initinfix (struct infix *p) { p->top = -1 ; strcpy(p->target,""); strcpy(p->stack,""); p->t = p->target; p->s = ""; } /* Lay thong tin cho bieu thuc */ void setexpr (struct infix *p, char *str) { p->s = str; } /* Push toan tu vao Stack*/ void push(struct infix *p, char c) { if (p->top == MAX) printf ("\nStack day\n"); else { p->top++; p->stack[p->top] = c; } } 11.3. Chương trình minh họa (3/5) PhD. Ngo Huu Phuc, Le Quy Don Technical University19 /* Lay toan tu khoi Stack */ char pop(struct infix *p) { if (p->top == -1) { printf ( "\nStack rong\n" ); return -1; } else { char item = p->stack[p->top]; p->top--; return item; } } /* Chuyen doi bieu thuc tu Infix sang Postfix */ void convert(struct infix *p) { char opr; while (*( p ->s)) { if (*(p->s) == ' ' || *(p->s) == '\t') { p->s++; continue ; } if (isdigit(*(p->s)) || isalpha (*(p->s))) { while (isdigit(*(p->s)) || isalpha(*(p->s))) { *(p->t) = *(p->s); p->s++; p->t++ ; } } 11.3. Chương trình minh họa (4/5) PhD. Ngo Huu Phuc, Le Quy Don Technical University20 if (*(p->s) == '(') { push(p,*(p->s)); p->s++; } if (*(p->s) == '*' || *(p->s) == '+' || *(p->s) == '/' || *(p- >s) == '%' || *(p->s) == '-' || *(p->s) == '$') { if (p->top != -1) { opr = pop(p); while ( priority(opr)>= priority (*(p->s))) { *(p->t) = opr; p->t++; opr = pop(p); } push(p, opr); push(p, *(p->s)); } else push(p, *(p->s)); p->s++; } if (*(p->s) == ')') { opr = pop(p); while (opr != '(') { *(p->t) = opr; p->t++; opr = pop(p); } p->s++; } } 11.3. Chương trình minh họa (5/5) PhD. Ngo Huu Phuc, Le Quy Don Technical University21 while (p->top != -1) { char opr = pop(p); *(p->t) = opr; p->t++; } *(p->t) = '\0'; } /* So sanh giua cac toan tu */ int priority(char c) { if (c == '$') return 3; if (c == '*' || c == '/' || c == '%') return 2; else { if (c == '+' || c == '-') return 1; else return 0; } } /* In ket qua */ void show (struct infix p) { printf (" %s", p.target); } 11.4. Một số dạng ký pháp khác  Ký pháp Prefix:  Ký pháp Prefix đặt toán tử trước các toán hạng của nó.  Ví dụ: /E F có nghĩa E/F + A * B C có nghĩa A + B * C  Một số vấn đề khác:  Chuyển đổi từ Infix sang Prefix.  Chuyển đổi từ Postfix sang Infix.  Chuyển đổi từ Postfix sang Prefix.  Chuyển đổi từ Prefix sang Postfix.  Trường hợp toán hạng không phải là một số!!! PhD Ngo Huu Phuc, Le Quy Don Technical University22