• Vui lòng đọc nội qui diễn đàn để tránh bị xóa bài viết
  • Tìm kiếm trước khi đặt câu hỏi

Ký pháp nghịch đảo Ba Lan Reverse Polish Notation (RPN)

Các bài viết hướng dẫn, giúp các bạn hiểu và tiếp cận với Visual Basic nhanh hơn
User avatar
truongphu
VIP
VIP
Posts: 4764
Joined: Sun 04/11/2007 10:57 am
Location: Cam Đức, Khánh hòa
Has thanked: 14 times
Been thanked: 519 times

Ký pháp nghịch đảo Ba Lan Reverse Polish Notation (RPN)

Postby truongphu » Mon 12/05/2008 10:05 am

Tên bài viết: Ký pháp nghịch đảo Ba Lan Reverse Polish Notation (RPN)
Tác giả: gửi bởi MATH-INFO vào ngày Thứ 5 22/12/2005 5:34 pm
Cấp độ bài viết: Chưa đánh giá
Tóm tắt: Copy từ Diễn đàn cũ


Thuật toán (tham khảo từ diendantinhoc.com)

Địa chỉ truy cập : http://www.diendantinhoc.com/showthread ... eadid=7415

Reverse Polish Notation (RPN) - ký pháp nghịch đảo Ba Lan là giải thuật dùng để tính giá trị biểu thức, thường được sử dụng trong các trình biên dịch

Trọng tâm của giải thuật là đưa biểu thức về dạng "hậu tố" (suffix) để tiện tính toán

vd: 1 + 2 x 3 sau khi xử lý trở thành 1 2 3 x +

Về cơ bản, thuật toán có thể chia ra làm hai công đoạn chính sau:

Chuyển đổi: đưa biểu thức bình thường về dạng kpnđ Ba Lan
Tính toán: tính giá trị biểu thức dựa trên dạng kpnđ Ba Lan

Sau đây là các bước cơ bản của thuật toán:

Công đoạn chuyển đổi:

Ta sử dụng hai stack: rpnStack dùng để lưu dạng kpnđ Ba Lan, oprStack dùng để tạm lưu các toán tử trong qúa trình chuyển đổi biểu thức

Xin nói thêm: 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ử cần lưu ý toán tử cộng trừ một ngôi (unary sign). Toán tử cộng trừ một ngôi là toán tử chỉ tác dụng lên một toán hạng đứng trước nó, khác với cộng trừ bình thường tác dụng lên hai toán hạng đứng trước nó

vd: -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

Bây giờ là thuật toán: ta đọ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

Toán tử: trong trường hợp này ta phải xét toán tử đang được lưu cuối cùng trong oprStack: nếu mức ưu tiên cao hơn toán tử đang xét thì chuyển toán tử đó sang rpnStack; tiếp tục làm như vậy cho đến khi được toán tử có mức ưu tiên nhỏ hơn hoặc bằng toán tử đang xét; cuối cùng đưa toán tử đang xét vào oprStack

Dấu đóng ngoặc: lần lượt chuyển các toán tử được lưu trong oprStack sang rpnStack; nếu gặp dấu mở ngoặc thì dừng lại và xóa dấu mở ngoặc đó khỏi oprStack

Lưu ý: khi viết chương trình chỉ duyệt được từng ký tự, do đó phải thêm phần xử lý nhận biết nhóm ký tự hợp thành một số (hoặc một tên biến)

vd: 564 + 4, khi bắt đầu duyệt từ ký tự "5" sẽ nhận biết luôn số "564" và nhảy đến ký tự thứ tư

Đó là các bước cơ bản của công đoạn chuyển đổi, kết qủa được lưu vào rpnStack, chỉ cần đọc từ đầu đến cuối rpnStack sẽ được dạng kpnđ Ba Lan

Công đoạn tính toán:

Sau khi đã thu được dạng kpnđ Balan rồi, tính toán như sau tìm toán tử đầu tiên trong rpnStack và áp dụng tính với các toán hạng đứng trước nó xóa toán tử và các toán hạng đã tính, thay bằng kết qủa tính được tiếp tục cho đến khi nào không còn toán tử để tính nữa; kết qủa của biểu thức chính là phần tử đầu tiên của rpnStack.


o0o--truongphu--o0o

.........
Ghé thăm:
Chuyện Linh Tinh

Return to “[VB] Bài viết hướng dẫn”

Who is online

Users browsing this forum: No registered users and 1 guest