Trang ChínhTrang Chính  CalendarCalendar  Trợ giúpTrợ giúp  Tìm kiếmTìm kiếm  Thành viênThành viên  NhómNhóm  Đăng kýĐăng ký  Đăng NhậpĐăng Nhập  
  • Top posters
 Mr.Pakapun (256)
 ddtan90 (178)
 tvduong (147)
 dthnam90 (137)
 minhquankq (101)
 arianbo (70)
 DoanhNhan (54)
 chicken (53)
 stormit (52)
 gentle_storm (47)

Share | 
 

 Tính giá trị biểu thức bằng phương pháp Ký pháp nghịch đảo Ba Lan

Go down 
Tác giảThông điệp
ddtan90
Admin
Admin
avatar

Tổng số bài gửi : 178
Join date : 30/12/2010
Age : 27
Đến từ : SE 3 - K34

Bài gửiTiêu đề: Tính giá trị biểu thức bằng phương pháp Ký pháp nghịch đảo Ba Lan   Sun Jan 09, 2011 12:37 am

Làm cách nào để tính giá trị một chuỗi kiểu char ví dụ:
Code:
1+3+3*6+(3+8)/(7+8)+4+(3*7+8)
(Trong bài này mình chỉ áp dụng cho trường hợp các số chỉ có 1 chữa số, trường hợp mỗi số có nhiều chữ số, phải xử lý từng số trước)
Máy tính không thể hiểu và tính toán được trên chuỗi ở dạng trung tố này. Do đó, chúng ta phải chuyển nó về 1 dạng nào đó có các số và toán tử riêng. Sau đó chuyển nó về dạng hậu tố (tức là toán hạn trước rồi toán tử sau). Trong bài này mình dùng phương pháp nghị đảo Ba Lan để thực hiện. Đây là một giải thuật khá phổ biến trong trình biên dịch. Nguyên tắc làm việc của phương pháp này như sau:


Ý tưởng chung của thuật toán cũng là duyệt biểu thức từ trái sang phải:

- Nếu gặp một toán hạng (con số hoặc biến) thì ghi nó vào chuỗi kết quả
- Nếu gặp dấu mở ngoặc, đưa nó vào stack.
- Nếu gặp một toán tử (gọi là o1 ), thực hiện hai bước sau:
o Chừng nào còn có một toán tử o2 ở đỉnh ngăn xếp VÀ độ ưu tiên của o1 nhỏ hơn hay bằng độ ưu tiên của o2 thì lấy o2 ra khỏi ngăn xếp và ghi vào kết quả.

o Push o1 vào ngăn xếp

- Nếu gặp dấu đóng ngoặc thì cứ lấy các toán tử trong ngăn xếp ra và ghi vào kết quả cho đến khi lấy được dấu mở ngoặc ra khỏi ngăn xếp.

- Khi đã duyệt hết biểu thức trung tố, lần lượt lấy tất cả toán hạng (nếu có) từ ngăn xếp ra và ghi vào chuỗi kết quả.


Code cho giải thuật có thể tại tại đây: mediafire.com ?zujpj31haf09dxb

ví dụ:
- Chuỗi trung tố: 1+2-3*4-5
=>Hậu tố: 12+34*-5-
- CHuỗi trung tố: 1-7/(3+4)
=>hậu tố : 1734+/-

Sau khi đã có dạng hậu tố của biểu thức, các bạn có thể tiếp tục sử dụng cách đã học trong môn Cấu trúc dữ liệu để tìm giá trị của biểu thức (dùng Stack).
nếu còn thắc mắc thì có thể để lại comment cho mình.

Chúc các bạn thành công!

_____________________
Nothing is impossible!
Về Đầu Trang Go down
Xem lý lịch thành viên
 
Tính giá trị biểu thức bằng phương pháp Ký pháp nghịch đảo Ba Lan
Về Đầu Trang 
Trang 1 trong tổng số 1 trang
 Similar topics
-
» [Tin công nghệ] Công nghệ mới làm giảm tiêu thụ nhiên liệu cho đội tàu biển
» Từ con diều giấy đến chiếc máy vi tính
» Nghệ thuật 'dập lửa'
» Tin Công nghệ (Máy tính, di động,...)
» Cho em hỏi về Giám định quy trình nhận hàng hóa chất

Permissions in this forum:Bạn không có quyền trả lời bài viết
Câu lạc bộ Hỗ Trợ Học Tập :: CÁC MÔN ĐẠI CƯƠNG - CƠ SỞ NGÀNH :: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT-
Chuyển đến