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: http://www.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!
Trang Chính 
Calendar
