Đồ Án Ký pháp nghịch đảo ba lan phương pháp tính giá trị biểu thức toán học

Giới thiệu về đề tài:
”KÝ PHÁP NGHỊCH ĐẢO BA LAN PHƯƠNG PHÁP TÍNH GIÁ TRỊ BIỂU THỨC TOÁN HỌC”
Khi lập trình, tính giá trị một biểu thức toán học là điều bình thường. Tuy nhiên, trong nhiều ứng dụng (như chương trình vẽ đồ thị hàm số chẳng hạn, trong đó chương trình cho phép người dùng nhập vào hàm số), 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 Ký Pháp Nghịch Đảo Ba Lan (Reserve Polish Notation – RPN), một thuật toán “kinh điển” trong lĩnh vực trình biên dịch.
Để đơ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; không có bất kỳ khoảng trắng nào giữa các ký tự.


Mục lục

Mục lục 1
I.Giới thiệu về đề tài: 2
Các phương pháp biểu diễn phép toán hai ngôi: 2
Cây biểu diễn biểu thức 2
Thế nào là ký pháp nghịch đảo Ba Lan? 4
II.Cấu trúc dữ liệu: 5
III. Thuật toán cơ bản: 5
IV. Mở rộng đề tài: 8
VI. Kết quả chương trình: 40
VII. Kết luận: 41
VIII. Nhận xét của giáo viên hướng dẫn: 42