Interpreter pattern: Object-oriented Expression Trees

Bài viết này nối tiếp bài “Tính giá trị một biểu thức” đã đăng hồi 2008.

CoolExpression

Trong số 23 design pattern của Gang of Four thì Interpreter ít được dùng nhất vì sự “algorithm” của nó :) Cùng xem lại lược đồ UML của Interpreter:

Trong bài này chúng ta sẽ tìm hiểu một ứng dụng của Interpreter: tính giá trị một biểu thức đại số, như hình demo phía trên cùng.

Thuật toán rất đơn giản như sau:

Xét mỗi một biểu thức (biểu diễn dưới dạng string) ta sẽ tìm cách ngắt nó thành một hoặc hai biểu thức nhỏ hơn. Sau đó bằng đệ quy, tính tiếp giá trị của các biểu thức nhỏ này và kết hợp chúng lại. (*)

Đối với những biểu thức hằng số như (1+2)*(3-4/5) thì giá trị của biểu thức đã tính được ngay khi quá trình (*) kết thúc.

Nhưng với những biểu thức đại số như (x+y)*(x-4/sin(y)) thì không đơn giản như vậy. Chúng ta cần tạo ra và lưu lại một cấu trúc dữ liệu tương ứng với biểu thức đó. Cấu trúc này chính là một cây mà nút lá của cây là những biến x, y hoặc hằng số như 4. Quá trình (*) sẽ tạo ra cây này:

ExpressionTree

Ta thấy ngay áp dụng Interpreter như nào:

  • Một object Expression chính là đại diện cho một nút của cây.
  • Context là một string cho biết giá trị của các biến, ví dụ context = "x=1,y=2".
  • Có các loại nút sau đây:
    • Nút lá (TerminalExpression) chứa một string biểu diễn một biến hoặc hằng số (x, y, 4). Method interpret(string context) của nút này sẽ tìm giá trị của x, y trong context và return giá trị tìm thấy.
    • Nút “cộng” (SumExpression) chứa tham chiếu tới hai nút con (e1, e2) có kiểu cụ thể là gì không cần biết. Method interpret(string context) của nút này đơn giản return e1.interpret(context) + e2.interpret(context).
    • Tương tự cho các nút khác …
  • Sau khi đã tạo ra cây biểu thức, để tính giá trị biểu thức với một context nào đó, chỉ việc gọi rootExpression.interpret(context).

Download source code viết bằng C#

Advertisements

One thought on “Interpreter pattern: Object-oriented Expression Trees

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s