Lecture 10 – Polish Notation
10.1. Reverse Polish Notation (RPN)
10.2. Chuyển đổi biểu thức dạng Infix sang Postfix
10.2.1. Chuyển đổi dạng Infix sang Postfix
10.2.2. Tính giá trị biểu thức dạng Postfix
10.3. Chuyển đổi biểu thức dạng Infix sang Prefix
10.3.1. Chuyển đổi dạng Infix sang Prefix
10.3.2. Tính giá trị biểu thức dạng Prefix
10.4. Một số vấn đề thực hành
8/28/14
Lecture 10 – Polish Notation
10.1. Reverse Polish Notation (RPN)
10.2. Chuyển đổi biểu thức dạng Infix sang Postfix
10.2.1. Chuyển đổi dạng Infix sang Postfix
10.2.2. Tính giá trị biểu thức dạng Postfix
10.3. Chuyển đổi biểu thức dạng Infix sang Prefix
10.3.1. Chuyển đổi dạng Infix sang Prefix
10.3.2. Tính giá trị biểu thức dạng Prefix
10.4. Một số vấn đề thực hành
8/28/14
10.1. Reverse Polish Notation

Ký pháp nghịch đảo Balan (RPN), 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

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.
8/28/14
10.1. Reverse Polish Notation

Một vài ví dụ:

VD1: 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 +.

VD2:
(1+2) * 3?

Trả lời: 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!!!
8/28/14

Xem xét ký pháp RPN sau:
4 5 + 6 *

10.1. Reverse Polish Notation

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.
8/28/14
Lecture 10 – Polish Notation
10.1. Reverse Polish Notation (RPN)
10.2. Chuyển đổi biểu thức dạng Infix sang Postfix
10.2.1. Chuyển đổi dạng Infix sang Postfix
10.2.2. Tính giá trị biểu thức dạng Postfix
10.3. Chuyển đổi biểu thức dạng Infix sang Prefix
10.3.1. Chuyển đổi dạng Infix sang Prefix
10.3.2. Tính giá trị biểu thức dạng Prefix
10.4. Một số vấn đề thực hành
8/28/14
10.2.1. Chuyển đổi dạng Infix sang Postfix

Thuật toán 1: 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

$
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/-
8/28/14
Lecture 10 – Polish Notation
10.1. Reverse Polish Notation (RPN)
10.2. Chuyển đổi biểu thức dạng Infix sang Postfix
10.2.1. Chuyển đổi dạng Infix sang Postfix
10.2.2. Tính giá trị biểu thức dạng Postfix
10.3. Chuyển đổi biểu thức dạng Infix sang Prefix
10.3.1. Chuyển đổi dạng Infix sang Prefix
10.3.2. Tính giá trị biểu thức dạng Prefix
10.4. Một số vấn đề thực hành
8/28/14
10.2.2. Tính gtbt dạng Postfix


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
+
+
* +
+
/
8/28/14
Lecture 10 – Polish Notation

1.4.2. Xét phần tử y ở đầu của stack.
1.4.3. y là phép toán thì loại y ra khỏi stack, đưa y vào stackkq, quay
về bước 1.4.2.
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 duyệt.
8/28/14
10.3.1. Chuyển đổi dạng Infix sang Prefix

Bước 3: Đưa tất cả các phần tử trong queue vào stackkq, tất cả
phần tử trong stack và stackkq.

Bước 4: Lấy từng phần tử trong stackkq ra, đó là kết quả dạng
Prefix.

Bước 5: Tính giá trị của biểu thức dưới dạng tiền tố.

Chú ý:
Pri(‘(‘)=Pri(‘)‘) <Pri(‘+‘)=Pri(‘-‘)<Pri(‘*‘)=<Pri(‘/‘)
8/28/14
10.3.1. Chuyển đổi dạng Infix sang Prefix

Cho biểu thức: E=a*b+c/d

Kết quả: +*ab/cd
Bước E Phần tử xét queue stack stackkq
0
a*b+c/d null empty empty empty
1
a*b+c/ d d empty empty

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.
8/28/14
10.3.2. Tính gtbt dạng Prefix

Ví dụ về tính biểu thức dạng Prefix:
/+7 8 + 6 * + 3 2 + 5 4
51
8
7
4 4
5
4
5
9 9
2
9
2
3
9
2
3
9
5
9
5
45 45
6

Một số vấn đề liên quan:
1. Chuyển đổi từ Postfix sang Infix.
2. Chuyển đổi từ Postfix sang Prefix.
3. Chuyển đổi từ Prefix sang Postfix.
4. Trường hợp toán hạng không phải là một số!!!

Một vài bài tập nâng cao:
1. Viết chương trình cho phép nhập vào một hàm dạng đa thức dưới dạng
chuỗi. Nhập giá trị x và in ra giá trị của hàm.
2. Viết chương trình cho phép nhập vào một số dạng hàm cơ bản và vẽ đồ thị
hàm.
3. Viết chương trình cho phép nhập vào công thức tính toán có sử dụng một số
phép toán như log, khai căn,…
8/28/14