Bài Tập chương 6: Cây biểu thức

BÀI TẬP CÂY BIỂU THỨC 1. Tạo cây biểu thức từ dạng Prefix (hậu tố) và Postfix (tiền tố) Các chuỗi prefix và postfix không chứa các dấu ngoặc đơn nên việc xây dựng cây nhị phân rất dễ dàng, các bước thực hiện cũng tương tự như việc bạn tính toán giá trị của hai dạng biểu thức \ Cụ thể thuật toán như sau: Lặp qua từng token trong chuỗi postfix - Tạo một đối tượng BinaryTreeNode với tên node cho token này - Nếu là toán hạng: Push node vào stack - Nếu là toán tử: o Pop một toán hạng ra khỏi stack và đặt làm RightChild của node o Pop toán hạng kế tiếp ra khỏi stack và đặt làm LeftChild của node o Push node vào stack Sau khi vòng lặp kết thúc, phần tử cuối cùng còn lại trong stack là node gốc của cây biểu thức. 2. Tạo cây biểu thức từ dạng Infix (trung tố) Tạo cây biểu thức trực tiếp từ biểu thức infix. Tuy nhiên chi phí cho việc tạo này sẽ lớn hơn so với việc tạo từ biểu thức dạng prefix và postfix, đặc biệt là phải xử lý các dấu ngoặc đơn. Bạn có thể coi phương pháp mà tôi sắp sử dụng là sự kết hợp giữa hai thuật toán chuyển đổi sang postfix và tạo cây biểu thức cùng một lúc. Thuật toán này yêu cầu sử dụng 2 stack: - OperatorStack: chứa các toán tử - NodeStack: chứa các node tạo nên cấu trúc cây (node gốc của các cây con được xây dựng từ dưới lên) Các bước tiến hành thuật toán Tạo một phương thức phụ CreateSubTree() có nhiệm vụ tạo một cây biểu thức gồm 3 node. Node gốc là toán tử Pop ra từ OperatorStack, hai node lá là toán hạng Pop từ NodeStack. Cuối cùng đưa node gốc vào lại NodeStack. Lặp qua từng token trong biểu thức infix - Nếu là toán hạng: push vào NodeStack - Nếu là dấu mở ngoặc “(“: push vào OperatorStack - Nếu là dấu đóng ngoặc “)”: o Lặp cho đến khi lấy được dấu mở ngoặc “(“ trong OperatorStack, mỗi lần lặp gọi phương thức CreateSubTree(). o Pop dấu mở ngoặc ra khỏi OperatorStack. - Nếu là toán tử: o Lặp cho đến khi OperatorStack rỗng hoặc độ ưu tiên của toán tử ở đỉnh OperatorStack nhỏ hơn độ ưu tiên của toán tử hiện tại. Mỗi lần lặp gọi phương thức CreateSubTree() o Push toán tử vào OperatorStack. Khi hết vòng lặp, nếu OperatorStack còn phần tử, gọi phương thức CreateSubTree() cho đến khi OperatorStack rỗng. Node cuối cùng nằm trong NodeStack là node gốc của cây. Ví dụ chuyển biểu thức infix sau thành cây biểu thức: (a+b)*c-d/e Token OperatorStack NodeStack Description ( ( {Empty} Push “(“ vào OperatorStack a ( a Push “a” vào NodeStack + (+ a Push “+” vào OperatorStack b (+ ab Push “b” vào NodeStack ) {Empty} + Cho “a”, “b” ra thành node con của “+” Push “+” vào NodeStack * * + Push “*” vào OperatorStack c * +c Push “c” vào NodeStack Cho “+”, “c” thành node con của “*” - - * Push “*” vào node Stack Push “-“ vào OperatorStack d - *d Push “d” vào NodeStack / -/ *d Push “/” vào OperatorStack e -/ *de Push “e” vào NodeStack -/ *de Kết thúc vòng lặp - */ Cho “d” và “e” thành node con của “/” Push “/” vào NodeStack Cho “*” và “/” thành node con của “-“ {Empty} - Push “-“ vào NodeStack Như vậy cuối cùng chỉ còn lại node “-“ ở NodeStack, đây chính là node gốc của cây biểu thức cần tạo. Ví dụ minh họa hình dưới đây để hiểu rõ hơn. Các node có màu đỏ đậm là các node đang nằm trong NodeStack. 3. Tính giá trị của cây biểu thức Chúng ta sẽ xét từ node gốc xuống, bằng cách sử dụng đệ quy ta sẽ duyệt qua tất cả các node. Nếu là node lá (toán hạng) thì trả về giá trị của chúng, nếu là node toán tử thì thực hiện tính toán dựa trên các node con của chúng.