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)

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:22

Thêm vào BST

Báo xấu

57
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

"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)" thông tin về những kiến thức Reverse Polish Notation; chuyển đổi biểu dạng Infix sang RPN; ví dụ về chuyển đổi từ Infix sang RPN; Prefix Notation.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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)

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) Giảng viên: TS. Ngo Huu Phuc Tel: 0438 326 077 Mob: 098 5696 580 Email: ngohuuphuc76@gmail.com 1 PhD Ngo Huu Phuc, Le Quy Don Technical University
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 2 PhD Ngo Huu Phuc, Le Quy Don Technical University
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. 3 PhD Ngo Huu Phuc, Le Quy Don Technical University
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). Dạng Infix Dạng Postfix Dạng Prefix A-B/(C+D) ABCD+/- –A/B+CD 4 PhD Ngo Huu Phuc, Le Quy Don Technical University
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!!! 5 PhD Ngo Huu Phuc, Le Quy Don Technical University
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. 6 PhD Ngo Huu Phuc, Le Quy Don Technical University
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!!! 7 PhD Ngo Huu Phuc, Le Quy Don Technical University
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?  45+ → 4+5=9  96* → 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. 45+6* 2. 96* 3. 54 8 PhD Ngo Huu Phuc, Le Quy Don Technical University
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?  45+ → 4+5=9  69* → 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. 645+* 2. 69* 3. 54 9 PhD Ngo Huu Phuc, Le Quy Don Technical University
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. 10 PhD Ngo Huu Phuc, Le Quy Don Technical University
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? 45+67+/ 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? 45+23+*6+87+/ Với dạng RPN, cần gõ phím 13 lần. 11 PhD Ngo Huu Phuc, Le Quy Don Technical University
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)
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(‘$’)
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. 14 PhD Ngo Huu Phuc, Le Quy Don Technical University
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#. E S E1 E S E1 $* abc+ $ - $ abc+* a $ a $- abc+* * $* a d $- abc+*d ( $*( a / $-/ abc+*d b $*( ab e $-/ abc+*de + $*(+ ab # $- abc+*de/ c $*(+ abc $ abc+*de/- ) $*( abc+ 15 PhD Ngo Huu Phuc, Le Quy Don Technical University
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: 45+23+*6+87+/ 4 4 4 9 9 9 9 9 9 45 45 45 51 51 51 5 5 2 2 2 5 5 6 6 8 8 + 3 3 * + 7 + 51 51 51 3.4 8 15 15 7 / + 16 PhD Ngo Huu Phuc, Le Quy Don Technical University
11.3. Chương trình minh họa (1/5) #include "stdio.h" void main() { #include "conio.h" struct infix p; #include "string.h" char expr[MAX]; #include "ctype.h“ initinfix(&p); #define MAX 50 printf ("\nNhap bieu thuc dang Infix: "); struct infix gets(expr) ; { setexpr(&p, expr); char target[MAX] ; char stack[MAX] ; convert(&p); char *s, *t ; printf ( "\nBieu thuc dang Postfix: " ) ; int top ; }; show(p); void initinfix (struct infix *); getch(); 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); 17 PhD. Ngo Huu Phuc, Le Quy Don Technical University
11.3. Chương trình minh họa (2/5) /* Khoi tao cau truc dang Infix */ /* Push toan tu vao Stack*/ void initinfix (struct infix *p) void push(struct infix *p, char c) { { p->top = -1 ; if (p->top == MAX) strcpy(p->target,""); printf ("\nStack day\n"); strcpy(p->stack,""); else p->t = p->target; { p->s = ""; } p->top++; p->stack[p->top] = c; /* Lay thong tin cho bieu thuc */ } void setexpr (struct infix *p, char *str) } { p->s = str; } 18 PhD. Ngo Huu Phuc, Le Quy Don Technical University
11.3. Chương trình minh họa (3/5) /* Lay toan tu khoi Stack */ /* Chuyen doi bieu thuc tu Infix sang Postfix */ char pop(struct infix *p) void convert(struct infix *p) { { char opr; if (p->top == -1) while (*( p ->s)) { { printf ( "\nStack rong\n" ); if (*(p->s) == ' ' || *(p->s) == '\t') return -1; { } else p->s++; { continue ; char item = p->stack[p->top]; } p->top--; if (isdigit(*(p->s)) || isalpha (*(p->s))) return item; { } while (isdigit(*(p->s)) || isalpha(*(p->s))) } { *(p->t) = *(p->s); p->s++; p->t++ ; } 19 PhD. Ngo Huu Phuc, Le Quy Don Technical University }
11.3. Chương trình minh họa (4/5) if (*(p->s) == '(') else { push(p, *(p->s)); push(p,*(p->s)); p->s++; p->s++; } } if (*(p->s) == ')') if (*(p->s) == '*' || *(p->s) == '+' || *(p->s) == '/' || *(p- >s) == '%' || *(p->s) == '-' || *(p->s) == '$') { { opr = pop(p); if (p->top != -1) while (opr != '(') { { opr = pop(p); *(p->t) = opr; while ( priority(opr)>= priority (*(p->s))) p->t++; { opr = pop(p); } *(p->t) = opr; p->s++; p->t++; } opr = pop(p); } } push(p, opr); push(p, *(p->s)); } 20 PhD. Ngo Huu Phuc, Le Quy Don Technical University