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

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