Reserve Polish Notation

Khi lập trình, việc để cho máy tính tính giá trị một biểu thức toán học là điều quá đỗi bình thường, nhưng để trình bày làm sao cho máy tính có thể đọc và hiểu được quy trình tính toán đó không phải là điều đơn giản. Trong nhiều ứng dụng, ta cần phải tính giá trị của một biểu thức được nhập vào từ bàn phím dưới dạng một chuỗi. Với các biểu thức toán học đơn giản (như a+b) thì bạn có thể tự làm bằng các phương pháp tách chuỗi thủ công. Nhưng để “giải quyết” các biểu thức có dấu ngoặc, ví dụ như (a+b)*c + (d+e)*f , thì các phương pháp tách chuỗi đơn giản đều không khả thi. Trong tình huống này, ta phải dùng đến Reserve Polish Notation – RPN), một thuật toán kinh điển

Để đơn giản cho việc minh họa, ta giả định rằng chuỗi biểu thức mà ta nhận được từ bàn phím chỉ bao gồm: các dấu mở ngoặc/đóng ngoặc; 4 toán tử cộng, trừ, nhân và chia (+, -, *, /), các toán hạng đều chỉ là các con số nguyên từ 0 đến 9, chỉ có duy nhất một khoảng trắng nào giữa các ký tự.

Các bước của thuật toán như sau:

• Khởi tạo ta có một mảng utput và một statck
• Ta split chuỗi theo dấu cách được một mảng các ký tự input
• Cho vòng lặp chạy hết mảng input:
  • Nếu là toán hạng 0..9, ta push vào output
  • Nếu gặp toán tử + , - *, /:
    • Thực viện vòng lặp kiểm tra, nếu ở đỉnh stack là toán tử, mà nó có độ ưu tiên lớn hơn hoặc bằng toán tử hiện tại thì ta lấy toán tử đó ra (pop) khỏi mảng stack và push vào output
    • Push toán tử hiện tại vào stack.
  • Nếu gặp dấu (, ta push vào stack
  • Nếu gặp dấu ), ta thực hiện vòng lặp lấy các toán tử trong stack và push vào output cho đến khi gặp dấu ( (Lưu ý là cũng pop luôn cả dấu ( ra khỏi stack)
• Sau khi kết thúc vòng lặp, nếu trong stack vẫn còn toán tử, ta sẽ push hết vào mảng output

Để hiểu rõ hơn, ta xét ví dụ chuyển đổi một biểu thức sau sang dạng postfix sử dụng thuật toán RPN: 11 + ( ( 10 - 2 ) * 6 ) + 7. Thuật toán sẽ được thực hiện như bảng dưới đây:

Vậy kết quả output sẽ là một mảng như sau: 11, 10, 2, -, 6, *, +, 7, +

Ta đã chuyển đổi biểu thức sang Postfix, nhưng mục đích của ta là tính toán kết quả của một biểu thức thì phải làm sao?. Việc này được thực hiện hết sức đơn giản theo các bước sau:

• Khởi tạo stack
• Chạy vòng lặp mảng input:
  • Nếu gặp số, ta push vào stack
  • Nếu gặp toán tử, ta pop hai phần tử trong stack ra và thực hiện tính giá trị biểu thức với toán tử hiện tại, cuổi cùng push kết quả vào stack.
• Đến cuối vòng lặp, phần tử duy nhất trong stack chính là kết quả biểu thức.

Ta tiếp tục xét ví dụ trên, sau khi đã có mảng postfix là 11, 10, 2, -, 6, *, +, 7, +, ta thực hiện tính toán theo các bước như bảng dưới đây:

Như vậy kết quả của biểu thức sẽ là 66.

Trên đây là bài giới thiệu về Reserve Polish Notation, hy vọng nó sẽ giúp ích cho các bạn. Cảm ơn các bạn đã chú ý theo dõi!

http://mathworld.wolfram.com/ReversePolishNotation.html