Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Tham khảo tài liệu 'cấu trúc dữ liệu và giải thuật part 5', công nghệ thông tin, cơ sở dữ liệu phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Nếu ta đưa phép toán một ngôi vào chẳng hạn phép thềm dấu âm mà ta ký hiệu là 0 đổ dễ phân biệt thì vẫn có thể biểu diễn biểu thức có chứa phép đó bằng một cây nhị phân được nếu như ta ấn định thêm một qui ước ví dụ toán hạng của 0 luôn là con phải của nó. Như vậy Biểu thức a 0 b c 2 có thể được biểu diên bởi cây như hình 6.21 Hình 6.21 Để cho đơn giản dưới đây ta chỉ xét tới biểu thức mà dạng biểu diên của nó là cây nhị phân như ở hình 6.2 . Trước hết ta xét tới phép định giá trị của một biểu thức số. Ta sẽ tạo cây nhị phân biểu diễn biểu thức đó với qui cách một nút như hình 6.22. LPTR TYPE RPTR Hình 6.22 Ngoài hai trường hợp LPTR và RPTR giống như qui cách đã nêu trước đây thì trường thứ ba INFO được thay bởi trường TYPE. Nếu không phải là nút lá thì trường TYPE chỉ phép toán ứng với nút đó. Giá trị của TYPE trong trường này sẽ là 1 2 3 4 5 6 tương ứng với các phép - 0. Nếu là nút lá thì TYPE có giá tộ 0 để chỉ biến hoặc hằng tương ứng với nút đó. Trong trường hợp này RPTR trỏ tới địa chỉ trong bảng ký hiệu Symbol table của biêh hoặc hằng đó. 127 Nhớ rằng với qui cách như trên nút trôn cây SC hru trữ loại của phép toán chứ không phải dấu phép toán đó. Điều này SC làm cho quá trình xử lý cây đơn giản đi. Còn bảng ký hiệu thì được tổ chức để chứa tên của biến ở trường SYMBOL hoặc hằng và giá trị của chúng ở trường VALUE . Như với cây ở hình 6.21 thì biểu diễn cụ thể sẽ như hình 6.23. Sau đây là giải thuật định giá của một biểu thức biểu diễn bởi một cây nhị phân. Giải thuật này dược viốt dưới dạng một hàm đệ qui. Function EVAL E I Cho E là con tró trỏ lới gốc cây biểu diễn một biểu thức theo cách như đã nêu. Hàm này cho ta giá trị của biểu thức đó. F ờ đây là một biến trỏ phụ 1. Case TYPE E - 0 F RPTR E return VALUE E TYPE E 1 return EVAL LPTR E EVAL RPTR E TYPE E 2 return EVAL LPTR E - EVAL RPTR E TYPE E 3 return EVAL LPTR E EVAL RPTR E TYPE E 4 return EVAL LPTR E EVAL RPTR E TYPE E 5 return EVAL LPTR E T EVAL RPTR E TYPEí 6 return 0 EVAL RPTR E else return 00 .
