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 University
1
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 University
2
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 University
3
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 University
4
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 University
5