Thứ sáu, ngày 15 tháng 12 năm 2017

Algorithm – Cải thiện thuật toán chuyển đổi và tính giá trị biểu thức số học

Ngày đăng: 12/3/2012, 13:48:17PM | Lượt xem: 2,179
Hot!

Trong một số bài viết trước đây tôi đã giới thiệu thuật toán chuyển đối biểu thức toán học giữa các dạng trung tố (infix), tiền tố (prefix) và hậu tố (postfix). Đồng thời tôi cũng trình bày phương pháp tính giá trị của các biểu thức này cũng như xây dựng cây biểu thức trực quan qua chương trình Y2 – Expression Converter Demo. Tuy nhiên thuật toán này chỉ mới hỗ trợ các toán tử hai ngôi (binary operation), trong bài viết này tôi sẽ mở rộng để thuật toán làm việc với các toán tử một ngôi (unary operation).

Y2 Expression Converter 1.2_tab2Trong một số bài viết trước đây tôi đã giới thiệu thuật toán chuyển đối biểu thức toán học giữa các dạng trung tố (infix), tiền tố (prefix) và hậu tố (postfix). Đồng thời tôi cũng trình bày phương pháp tính giá trị của các biểu thức này cũng như xây dựng cây biểu thức trực quan qua chương trình Y2 – Expression Converter Demo. Tuy nhiên thuật toán này chỉ mới hỗ trợ các toán tử hai ngôi (binary operation), trong bài viết này tôi sẽ mở rộng để thuật toán làm việc với các toán tử một ngôi (unary operation).

Cập nhật (23 March 2011):

Cảm ơn bạn ngngthanhmai đã góp ý về một số trường hợp lỗi với toán tử “-” (unary).

Giới thiệu

Do thời gian có hạn nên tôi chỉ minh họa với hai toán tử là “-“ (số âm) và “sqrt()” (căn bậc hai). Hai toán tử /hàm này có điểm chung là đứng trước toán hạng. Các toán tử đứng sau toán hạng như “!” (giai thừa) cũng có cơ chế xử lý tương tự.

Đối với các toán tử (hoặc hàm) như sqrt, sin, cos,… có hai cách viết là đặt các toán hạng bên trong dấu ngoặc đơn hoặc không (ví dụ: sqrt(x) hoặc sqrt x). Ở đây tôi chọn cách đầu tiên để có thể đặt một biểu thức vào trong cặp ngoặc đơn và làm biểu thức rõ ràng hơn.

Nội dung cập nhật

Các cập nhật sau nằm trong thư viện Y2ExprConverter.dll thuộc chương trình Y2-ExpressionConverter (version 1.2). Tôi chỉ sửa đổi một vài phương thức chuyển đổi và tính toán với postfix, tạo cây biểu thức từ infix. Các phương thức còn lại bạn có thể thực hiện tương tự. Tất cả các sửa đổi này đều được cập nhật đầy đủ mã nguồn và chức năng cho chương trình Y2-ExpressionConverter (version 1.2).

Các phương thức chung

Sửa đổi phương thức định dạng biểu thức để xử lý các trường hợp nhập nhiều toán tử liền nhau (chỉ cho phép hai toán tử với toán tử thứ hai là “-“):

public static string FormatExpression(string expression)
{
    expression = expression.Replace(" ", "");
    expression = Regex.Replace(expression, @"(\+|\-|\*|\/|\%){3,}", match => match.Value[0].ToString());

    expression = Regex.Replace(expression, @"(\+|\-|\*|\/|\%)(\+|\*|\/|\%)", match =>
        match.Value[0].ToString()
    );
    expression = Regex.Replace(expression, @"\+|\-|\*|\/|\%|\)|\(", match =>
        String.Format(" {0} ", match.Value)
    );
    expression = expression.Replace("  ", " ");
    expression = expression.Trim();

    return expression;
}

Sửa đổi phương thức lấy độ ưu tiên và kiểm tra toán tử (bổ sung toán tử sqrt):

public static int GetPriority(string op)
{
    if (op == "sqrt")
        return 3;
    if (op == "*" || op == "/" || op == "%")
        return 2;
    if (op == "+" || op == "-")
        return 1;
    return 0;
}
public static bool IsOperator(string str)
{
    return Regex.Match(str, @"^(\+|\-|\*|\/|\%|sqrt)$").Success;
}

Chuyển đổi từ biểu thức infix sang postfix

-          Khi gặp toán tử dấu âm “-“ (toán tử “-“ đứng liền sau toán tử khác), ta nối toán tử này với toán hạng ngay sau nó

-          Khi gặp toán tử “sqrt” ta push vào stack

public static string Infix2Postfix(string infix)
{
    infix = FormatExpression(infix);

    string[] tokens = infix.Split(' ').ToArray();
    Stack<string> stack = new Stack<string>();
    StringBuilder postfix = new StringBuilder();

    for (int i = 0; i < tokens.Length; i++)
    {
        string token = tokens[i];
        if (IsOperator(token))
        {
            if ((i==0) || (i > 0 && (IsOperator(tokens[i - 1]) || tokens[i - 1]=="(" )))
            {
                if (token == "-")
                {
                    postfix.Append(token + tokens[i + 1]).Append(" ");
                    i++;
                }
                else if (token == "sqrt")
                {
                    stack.Push(token);
                }
            }
            else
            {
                while (stack.Count > 0 && GetPriority(token) <= GetPriority(stack.Peek()))
                    postfix.Append(stack.Pop()).Append(" ");
                stack.Push(token);
            }
        }

        else if (token == "(")
            stack.Push(token);
        else if (token == ")")
        {
            string x = stack.Pop();
            while (x != "(")
            {
                postfix.Append(x).Append(" ");
                x = stack.Pop();
            }
        }
        else// (IsOperand(s))
        {
            postfix.Append(token).Append(" ");
        }
    }

    while (stack.Count > 0)
        postfix.Append(stack.Pop()).Append(" ");

    return postfix.ToString();
}

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

Ta chỉ lấy một toán hạng ra khỏi stack để tính thay vì hai toán hạng như đối với các toán tử binary

public static double EvaluatePostfix(string postfix)
{
    Stack<double> stack = new Stack<double>();
    postfix = postfix.Trim();

    IEnumerable<string> enumer = postfix.Split(' ');

    foreach (string s in enumer)
    {
        if (IsOperator(s))
        {
            double x = stack.Pop();

            if (s == "sqrt")
            {
                x = Math.Sqrt(x);
                stack.Push(x);
            }
            else
            {
                double y = stack.Pop();

                switch (s)
                {
                    case "+": y += x; break;
                    case "-": y -= x; break;
                    case "*": y *= x; break;
                    case "/": y /= x; break;
                    case "%": y %= x; break;
                }

                stack.Push(y);
            }
        }
        else  // IsOperand
        {
            stack.Push(double.Parse(s));
        }

    }
    return stack.Pop();
}

Chuyển biểu thức infix thành cây biểu thức

private static void CreateSubTree(Stack<BinaryTreeNode> opStack, Stack<BinaryTreeNode> nodeStack)
{
    BinaryTreeNode node = opStack.Pop();
    node.RightChild = nodeStack.Pop();
    if(node.Value!="sqrt")
        node.LeftChild = nodeStack.Pop();
    nodeStack.Push(node);
}

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

    infixExpression = FormatExpression(infixExpression);

    string[] tokens = infixExpression.Split(' ').ToArray();

    for (int i = 0; i < tokens.Count(); i++)
    {
         if (IsOperator(tokens[i]))
        {
            if (i > 0 && IsOperator(tokens[i - 1]))
            {
                if (tokens[i] == "-")
                {
                    nodeStack.Push(new BinaryTreeNode(tokens[i] + tokens[i + 1]));
                    i++;
                }
                else if(tokens[i]=="sqrt")
                    operatorStack.Push(new BinaryTreeNode(tokens[i]));
            }
            else
            {
                while (operatorStack.Count > 0 && GetPriority(operatorStack.Peek().Value) >= GetPriority(tokens[i]))
                    CreateSubTree(operatorStack, nodeStack);

                operatorStack.Push(new BinaryTreeNode(tokens[i]));
            }
        }

        else if (tokens[i] == "(")
            operatorStack.Push(new BinaryTreeNode(tokens[i]));
        else if (tokens[i] == ")")
        {
            while (operatorStack.Peek().Value != "(")
                CreateSubTree(operatorStack, nodeStack);
            operatorStack.Pop();
        }
         else //if (IsOperand(tokens[i]))
            nodeStack.Push(new BinaryTreeNode(tokens[i]));
    }

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

    return nodeStack.Peek();
}

Các đoạn mã nguồn trên được trích từ tập tin Y2Expression.cs trong thư viện Y2ExprConverter.dll. Bạn có thể xem mã nguồn hoàn chỉnh của tập tin này tại link sau:

C# – Y2Expression: Convertion, Evaluation and Build Expression Tree

http://yinyangit.wordpress.com

 Chia sẻ qua: 
Hot!
Ý kiến bạn đọc

These items will be permanently deleted and cannot be recovered. Are you sure?

Gallery

image

Maecenas viverra rutrum pulvinar

Maecenas viverra rutrum pulvinar! Aenean vehicula nulla sit amet metus aliquam et malesuada risus aliquet. Vestibulum rhoncus, dolor sit amet venenatis porta, metus purus sagittis nisl, sodales volutpat elit lorem…

Read more

Text Links

Thiết kế logo chuyên nghiệp Insky
DAFABET
W88 w88b.com/dang-ky-tai-khoan-w88
W88
ca do bong da online
Copyright © 2011 - 2012 vietshare.vn by phamkhuong102@gmail.com doanhkisi2315@gmail.com. All rights reserved.