Reverse Polish Notation

Reverse Polish Notation - Thuật toán tính giá trị biểu thức

Ngô Minh Đức

Reverse Polish Notation (ký pháp nghịch đảo Ba Lan) là một loại ký pháp toán học dùng

để biểu thị biểu thức đại số, rất thuận lợi trong giải thuật tính giá trị biểu thức, có nghĩa là

bạn nhập vào một chuỗi, chẳng hạn ″(1+2)*3″, chương trình sẽ tính ra kết qủa bằng 9.

Reverse Polish Notation (gọi tắt là RPN) có hai loại, tiền tố (preffix) và hậu tố (suffix),

trong bài này tôi chỉ đề cập đến dạng suffix.

Để hiểu rõ hơn và dễ dàng tiếp cận với thuật toán này trước tiên chúng ta xét một ví dụ đơn

giản sau đây:

Chẳng hạn xét biểu thức sau:

(1 + 2) x 3 thì dạng RPN - hậu tố - của biểu thức trên là: 1 2 + 3 x

Chương trình có thể tính toán rất dễ dàng với biểu thức dạng RPN. Bạn để ý trong biểu

thức RPN không còn dấu ngoặc nữa, khi tính toán chỉ cần duyệt các toán tử từ trái sang

phải và thực hiện với các toán hạng đứng trước nó.

Đây là mô tả qúa trình tính toán biểu thức RPN trên:

Bước 1: Duyệt đến dấu +, ngừng lại.

Bước 2: Cộng hai toán hạng đứng trước nó: 1+2=3.

Bước 3: Xóa các phần tử 1, 2, + thay bằng số 3

Quay lại bước 1: Duyệt đến dấu x, ngừng lại

Quay lại bước 2: Nhân hai toán hạng đứng trước nó: 3x3=9

Quay lại bước 3: Thay các phần tử 3, 3, x bởi số 9. Chỉ còn một phần tử nên kết thúc.

Kết qủa chính là phần tử duy nhất còn lại: Đó là số 9

Do đó vấn đề chỉ còn là chuyển biểu thức từ dạng thông thường sang dạng RPN. Sau đây

tôi sẽ trình bày giải thuật chuyển đổi dưới hai phần.

1. Phần cơ bản.

Giải thuật này do các bạn trên TTVNOnline (www.ttvnol.com) và Diễn Đàn Tin Học

(www.diendantinhoc.com) cung cấp.

Xin các bạn chú ý một điều là: các phần tử trong biểu thức được chia ra làm hai loại: toán

hạng (số) và toán tử (bao gồm dấu và hàm)

Trong các loại toán tử, chúng ta cần lưu ý đến toán tử cộng trừ một ngôi (unary

plus/minus). Đây là một loại toán tử chỉ tác dụng lên một toán hạng đứng trước nó, khác

với toán tử cộng trừ bình thường tác dụng lên hai toán hạng đứng trước nó

ví dụ: -2 + 5 thì ″-″ là toán tử một ngôi, ″+″ là toán tử bình thường

Để xác định ″+″, ″-″ là một ngôi hay hai ngôi, khi duyệt biểu thức ta chỉ cần xem phần tử

đứng trước nó là số hay là một toán tử khác

Mức ưu tiên của các toán tử (từ nhỏ đến lớn): (, +, -, *, /, ^, + một ngôi, - một ngôi

Thuật toán:

Ta sử dụng hai stack (ngăn xếp): rpnStack dùng để lưu dạng RPN, oprStack dùng để tạm

lưu các toán tử trong qúa trình xử lý. Đọc lần lượt từ đầu đến cuối biểu thức để xử lý theo

từng loại:

Dấu mở ngoặc: đưa vào oprStack

Toán hạng: đưa vào rpnStack