Algorithm – Tạo và sử dụng cây biểu thức (expression tree)

Các biểu thức toán học đều có thể được thể hiện dưới dạng cấu trúc cây, trong đó các node lá là những toán hạng (biến, hằng số) và các node còn lại là các toán tử (*, /, +, -). Với cách biểu diễn dạng này, ta có thể dễ dàng dùng các phép duyệt với cây nhị phân để tạo ra những biểu thức toán học dạng tiền tố, trung tố và hậu tố mà bài trước tôi đã trình bày qua.  Và khái niệm này được gọi là cây biểu thức, hãy thử tìm hiểu làm cách nào để tạo và tận dụng được các khả năng của nó.

Thế nào là cây biểu thức?

(Trước tiên xin nói trước đây là phải bài giới thiệu về chức năng Expression Tree trong .Net, đây chỉ phần giới thiệu về thuật toán).

Trong phần này ta hãy đi chi tiết hơn về cách biểu diễn và các đặc điểm của cây biểu thức.
Trước tiên ta hãy xem một biểu thức đại số đơn giản sau:

(a+b)*c-d/e

Dựa vào các quy tắc tính toán thông thường, ta có thể nhóm chúng lại bằng các cặp ngoặc đơn để thấy rõ hơn mức ưu tiên của chúng:

(((a+b)*c)-(d/e))

Như bạn thấy tất cả đều được phân cấp theo thứ tự ưu tiên một cách rõ ràng, dựa vào đó việc chuyển đổi biểu thức trên thành một cây biểu thức rất đơn giản với chúng ta.

Bạn thấy rằng cây biểu thức trên là một cây nhị phân vì các toán tử của nó là toán tử hai ngôi. Các node lá bao giờ cũng là toán hạng và các node còn lại phải là toán tử. Dựa vào độ sâu của các node này, ta biết được toán tử nào sẽ được thực hiện trước, tức là toán tử (+) nằm ở gốc của cây sẽ được thực hiện cuối cùng.
Việc duyệt cây do đó phải được bắt đầu từ các node dưới cùng đi dần lên trên trong cả hai mục đích: tính giá trị và tạo ra biểu thức tiền tố, hậu tố.

 

Cách cách duyệt cây biểu thức


Trong bài về cây nhị phân tìm kiếm (Binary Search Tree), tôi đã giới thiệu ba cách duyệt cây là:

In-Order Traversal: node.LeftChild -> node -> node.RighChild
Pre-Order Traversal: node -> node.LeftChild -> node.RighChild
Post-Order Traversal: node.LeftChild -> node.RighChild -> node

Bây giờ ta thử duyệt cây biểu thức ở ví dụ trên theo cả 3 cách:

– In-Order: a + b * c – d / e
– Pre-Order: – * + a b c / d e
– Post-Order: a b + c * d e / –

Bạn có thể thấy 3 biểu thức được tạo ra ở trên chính là ba dạng biểu thức trung tố (infix), tiền tố (prefix) và hậu tố (postfix). Đây chính là cơ sở của kĩ thuật chuyển từ biểu thức infix sang prefix và postfix mà tôi đã có dịp giới thiệu trong bài trước. Bằng cách sử dụng cây biểu thức, bạn có thể chuyển đổi qua các dạng biểu thức infix, prefix và postfix dễ dàng.
(Bạn có thể dùng chương trình Y2 Expression Converter nhập vào chuỗi biểu thức ( ( ( a + b ) * c ) – ( d / e ) ) để kiểm tra xem thử kết quả có đúng như trên không).

 

Tạo cấu trúc để lưu trữ cây biểu thức


Trong bài giới thiệu về cây nhị phân trước đây, tôi đã tạo ra một cấu trúc tương đối đầy đủ để lưu trữ thông tin và các phương thức thao tác với cây. Tuy nhiên trong bài này ta chỉ cần một lớp đơn giản để minh họa việc tạo cây biểu thức:

public class BinaryTreeNode
{
    public BinaryTreeNode LeftChild;
    public BinaryTreeNode RightChild;
    public string Value;

    public bool IsLeaf
    {
        get { return this.LeftChild == null && this.RightChild == null; }
    }

    public BinaryTreeNode(string value)
    {
        Value = value;
    }

}

Property IsLeaf trên được dùng để kiểm tra một node có phải lá không. Ta sẽ dựa vào property này để vẽ các node lá (là các toán hạng) khác với các node là toán tử.

 

Tạo cây biểu thức từ dạng Prefix và Postfix


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 (xem tại đây).
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.

Mã nguồn C# cài đặt cho phương thức này như sau:

public static BinaryTreeNode Postfix2ExpressionTree(string postfixExpression)
{
    Stack stack = new Stack();

    IEnumerable enumer = postfixExpression.Split(' ');

    foreach (string s in enumer)
    {
        BinaryTreeNode node = new BinaryTreeNode(s);
        if (IsOperand(s))
            stack.Push(node);
        else if (IsOperator(s))
        {
            node.RightChild = stack.Pop();
            node.LeftChild= stack.Pop();
            stack.Push(node);
        }
    }
    return stack.Pop();
}

Bạn có thể tự viết mã nguồn tạo cây biểu thức từ dạng prefix, thuật toán tương tự như trên.

 

Tạo cây biểu thức từ dạng Infix


Sẽ hợp lý hơn nếu ta có thể 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 (+ a b 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 – / * d e Push “e” vào NodeStack
– / * d e Kết thúc vòng lặp
* / Cho “d” và “e” thành node con của “/”
Push “/” vào NodeStack
{Empty} Cho “*” và “/” thành node con của “-“
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. Bạn có thể xem 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.

Cuối cùng ta có mã C# cài đặt cho thuật toán này:

///
/// Tạo một cây nhị phân 3 node với node gốc là toán tử, 2 node lá là toán hạng
///
/// <param name="node" />
/// <param name="opStack" />
/// <param name="nodeStack" />
private static void CreateSubTree(Stack opStack, Stack nodeStack)
{
    BinaryTreeNode node = opStack.Pop();
    node.RightChild = nodeStack.Pop();
    node.LeftChild = nodeStack.Pop();
    nodeStack.Push(node);
}

public static BinaryTreeNode Infix2ExpressionTree(string infixExpression)
{
    List prefix = new List();
    Stack operatorStack = new Stack();
    Stack nodeStack = new Stack();

    FormatExpression(ref infixExpression);

    IEnumerable enumer = infixExpression.Split(' ');

    foreach (string s in enumer)
    {
        if (IsOperand(s))
            nodeStack.Push(new BinaryTreeNode(s));
        else if (s == "(")
            operatorStack.Push(new BinaryTreeNode(s));
        else if (s == ")")
        {
            while (operatorStack.Peek().Value != "(")
                CreateSubTree(operatorStack, nodeStack);
            operatorStack.Pop();
        }
        else if (IsOperator(s))
        {
            while (operatorStack.Count > 0 && GetPriority(operatorStack.Peek().Value) >= GetPriority(s))
                CreateSubTree(operatorStack, nodeStack);

            operatorStack.Push(new BinaryTreeNode(s));
        }

    }

    while (operatorStack.Count > 0)
        CreateSubTree(operatorStack, nodeStack);

    return nodeStack.Peek();
}

Tính giá trị của cây biểu thức


Cách tính giá trị của biểu thức prefix và postfix đã được tôi giới thiệu trong bài này. Ở đây tôi giới thiệu thêm cách tính giá trị của cây biểu thức, thuật toán rất đơn giản nếu như bạn đã hiểu rõ về các thuật toán làm việc với cây nhị phân.

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.

Mã nguồn C# như sau:

public static float EvaluateExpressionTree(BinaryTreeNode node)
{
    float t=0;
    if (node.IsLeaf)
        t= float.Parse(node.Value);
    else
    {
        float x = EvaluateExpressionTree(node.LeftChild);
        float y = EvaluateExpressionTree(node.RightChild);

        switch (node.Value)
        {
            case "+": t = x + y; break;
            case "-": t = x - y; break;
            case "*": t = x * y; break;
            case "/": t = x / y; break;
            case "%": t = x % y; break;
        }
    }
    return t;
}

Chương trình minh họa


Đây là chương trình Y2 Expression Converter được nâng cấp lên phiên bản 1.1 cho phép hiển thị cây biểu thức từ chuỗi infix, cùng các phương thức bổ sung và lớp Y2Expression để tạo và làm việc với cây biểu thức.
Bạn có thể download sourcecode và demo tại bài giới thiệu riêng về chương trình.

Y2 Expression Converter 1.1

Y2 Expression Converter 1.1

Phần kết


Trên đây chỉ là minh họa và thuật toán để bạn có thể hiểu cách thức tạo và làm việc với cây biểu thức. Trong .Net 3 có sẵn một build-in Expression Tree mà tôi đã nhắc tới trong bài về lambda expression.

https://yinyangit.wordpress.com

Advertisements

21 thoughts on “Algorithm – Tạo và sử dụng cây biểu thức (expression tree)

  1. Mình đang làm một bài tập về tìm kiếm và mình dùng phương pháp expression tree của bạn nhưng mình vướng phải phần tính giá trị của biểu thức.
    Ví dụ :
    – Nếu người ta đánh từ khóa “con and ga” thì không có vấn đề gì.
    – Nhưng khi đánh từ khóa “not ga” thì báo lỗi.

    Mong nhận được sự giúp đỡ từ bạn.

    Phản hồi
  2. Chưa hiểu ý bạn là gì, tuy nhiên có lẽ là giống như trong biểu thức toán, thay vì gõ 1+2 thì người dùng có thể gõ vào là -2 (số âm). Đây có thể coi là 1 token hoặc tách riêng ra là toán tử – (unary). Hiện tại chưa có thời gian trong tuần tới mình sẽ xem xét để cải tiến thuật toán làm việc với những toán tử có một toán hạng. Nếu không đúng vấn đề của bạn vui lòng nói rõ hơn.

    Phản hồi
  3. Oh mình xin lỗi !!! Mình nói câu cú không rõ ràng nên bạn chưa hiểu. Thật ra ý mình là thay vì toán hạng của bạn là số thì mình là chữ, các toán tử của bạn của là (+ – * /) của mình là (AND, OR, NOT).
    Ví dụ mình có 3 văn bản D1,D2,D3
    – Trong đó D1 có từ com,pho,chao,…
    – Trong đó D2 có từ ga,vit,heo,…
    – Trong đó D3 có từ com,vit,ghe,…
    Khi người dùng gõ vào : com AND vit thì mình kết quả sẻ là D3.
    Mình áp dụng thuật toán của bạn (express tree) để xử lý yêu cầu đề bài (mình đã xừ lý thành công). Nhưng mình gặp 1 trở ngại là :
    – Khi người dùng gõ : NOT com hoặc NOT com and NOT vit. Cũng giống như bài toán bạn làm là khi người dùng gõ số âm thì nó tách riêng thành 2 token vậy.

    Mình rất cảm ơn bạn đã xây dựng nhiều bài viết về thuật toán rất hay và bổ ích. Mình xin phép bạn cho mình được đưa bài viết qua 4rum lớp mình và đưa vào đề tài mà mình đang thực hiện. Mình sẽ ghi rõ nguồn gốc.
    Xin cảm ơn bạn !!!
    Chúc bạn một ngày tốt lành !!

    Phản hồi
  4. Chào bạn! theo nguyên tắc thì việc dùng toán hạng là số hay chữ cũng ảnh hưởng đến logic của thuật toán. Nguyên nhân lỗi trên là vì phiên bản thuật toán đó chưa hỗ trợ xử lý toán tử NOT như bạn đã biết. Hi vọng bài viết sau giúp được phần nào đó cho vấn đề của bạn:
    http://wp.me/ptl4u-iv

    Phản hồi
  5. Mình xin lỗi! Mình mới chỉ tiếp xúc với ngôn ngữ này được một thời gian. Chính vì thế mình vẫn chưa hiểu làm cách nào để đánh giá được infix. Ý mình là cho 1 biểu thức như thế này chẳng hạn:
    ((4*36/8-7)+(51-68+1*13))*(16-9)
    thì khi thực hiện chuyển đổi. Nó sẽ cho ra kết quả từng bước tính toán theo đúng quy trình tính toán cộng trừ nhân chia, trong ngoặc trước ngoài ngoặc sau. Mình không thể nào làm được.Mong bạn giúp đỡ và cho mình 1 bản demo để mình tìm hiểu nó kĩ hơn
    Mình rất cám ơn về những bài viết hay và bổ ích của bạn. Chúc bạn mạnh khỏe và mọi điều tốt lành!

    Phản hồi
  6. Ah, bạn YinYang, cho mình hỏi xíu. Mình đang áp dụng cây biểu thức để giải quyết vấn đề đạo hàm. Việc chuyển đổi biểu thức thành công như bạn hướng dẫn, vấn đề vướng mắc của mình là chưa biết cách tính đạo hàm, vì đạo hàm có nhiều loại và không theo chuẩn chung nào cả. Bạn có từng đọc hay suy nghĩ vấn đề này chưa? Bạn có thể cho mình xin ý kiến về cách tính Đạo hàm dựa trên Cây biểu thức.

    Phản hồi
    • Một vấn đề thú vị, mặc dù mình chưa tìm hiểu về vấn đề này trước đây nhưng có thể đưa ra một số ý kiến như sau:

      – Nếu như bạn có thể dựa vào cây biểu thức ban đầu, chuyển thành cây biểu thức mới thông qua các công thức đạo hàm thì coi như việc tính đạo hàm đã coi như thành công. Việc chuyển đối này được thực hiện từ node gốc và đi ngược đến các node lá.

      – Việc xử lý chủ yếu ở các node toán tử, cây biểu thức có thể bị thay đổi và thêm vào các node mới. Điều này đòi hỏi bạn phải viết nhiều phương thức chuyển đổi cho mỗi công thức.

      Ví dụ đơn giản nhất với một cây có 3 node, tương đương với biểu thức: u * v
      Một biểu thức có dạng (u*v)’ sẽ tạo ra một biểu thức mới u’v+v’u:

      *’
      / \
      u v
      Thành:
      +
      / \
      * *
      / \ / \
      u’ v v’ u

      Trường hợp u, v là các toán hạng thì công việc coi như hoàn tất, nếu không phải tiếp tục gọi phương thức chuyển đổi trên các node này.

      Mỗi node ta sẽ dùng 1 property kiểu boolean để xác định node đó cần tính đạo hàm hay không, tương đương với kí hiệu nháy đơn ‘ trong toán học.

      Đây chỉ là lý thuyết còn việc hiện thực dựa vào kiến thức và kinh nghiệm lập trình của bạn, đặc biệt bạn cần nắm rõ về cây biểu thức.

      Phản hồi
  7. Các công thức đạo hàm đã được biết đến từ hồi phổ thông. Chỉ cần dựa vào những công thức đó là giải quyết được, điểm quan trọng ở đây là xử lý, thao tác cây biểu thức chứ không phải các công thức. Mặc dù có thể không dùng đệ quy nhưng bản chất của cây là đệ quy nên chỉ cần áp dụng giải quyết cho cây đơn giản nhất. Khi bạn phân tích một node thì chỉ có các node con của nó mới bị ảnh hưởng.

    Phản hồi
  8. bạn ơi cho mình hỏi trong bài toán này thì độ ưu tiên của dấu phủ định(neg) cao hơn dấu “+,-” thế làm thế nào để viết hàm chuyển ừ trung tố sang hậu tố mà kết quả có phân biệt dấu trừ với dấu phủ định
    vd: (-x+y)
    hậu tố là:x-y+ nhung mình muốn xuất hiện là x neg y+ thì làm thế nào bạn chỉ cho mình cái nha.
    thanks bạn nhiều!

    Phản hồi
  9. Bạn có thể làm giúp mình bài tập này được không (Bạn có thể chỉ nói ý tưởng thôi):
    Viết chương trình tạo cây nhị phân để biểu diễn một biểu thức số học bất kỳ (chỉ chứa các phép toán (+, -, *, / và không có các ký hiệu xác định thứ tự ưu tiên) nhập từ bàn phím
    Ví dụ như nhập từ bàn phím biểu thức: “2+5*7-3+4/2”, thì sẽ tạo cây nhị phân như sau:


    + 3
    + 2
    * /
    5 7 4 2
    (Đây là đề thi cao học năm 2008 ở đại học đà nẵng)

    Phản hồi
  10. mọi ng ơi giúp em bài này với dc ko ak em cảm ơn rất nhiều :
    Xây dựng lớp cây nhị phân
    – Bổ sung phương thức tạo cây nhị phân từ biểu thức trung tố lưu trong một
    chuỗi
    – Bổ sung phức thức vẽ cây lên màn hình đồ họa
    – Viết chương trình cho phép quản lý một biểu thức với các chức năng sau:
    o Đọc một biểu thức dạng trung tố từ file vào một chuỗi
    o Chuyển biểu thức đó sang dạng tiền tố
    o Tạo cây nhị phân biểu diễn biểu thức
    o Xóa bỏ một nút trong của cây
    o Vẽ cây biểu thức lên màn hình đồ họa
    o Duyệt cây nhị phân in biểu thức lên màn hình theo 3 dạng (tiền tố, hậu
    tố, trung tố)

    Phản hồi

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Đăng xuất / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Đăng xuất / Thay đổi )

Connecting to %s