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

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

https://yinyangit.wordpress.com

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

  1. Bạn xem lại chỗ này 1 tý :

    if (i > 0 && IsOperator(tokens[i – 1]))
    {
    if (token == “-“)
    {
    postfix.Append(token + tokens[i + 1]).Append(” “);
    }
    }

    Nếu đứng trước số âm là một toán tử thì nó mới hiểu đây là số âm :
    Ví dụ : 1 + -2 <= hoàn toàn đúng.

    Nhưng nếu người dùng nhập :
    Ví dụ : -2 + 1 thì nó hiểu -2 là một toán tử và một toán hạng và ta vẫn không tính được giá trị của biểu thức.

    Hoặc người dùng nhập : 1 + (-2) vẫn không thực hiện được.

    Nếu

    Trả lời
    • Cảm ơn bạn đã góp ý, do chưa test kĩ nên cũng không nhận ra các trường hợp này. Trước mắt bạn có thể khắc phục lỗi trên như sau:

      if ((i==0) || (i > 0 && (IsOperator(tokens[i - 1]) || tokens[i - 1]=="(" )))
      {
      	if (token == "-")
      	{
      		postfix.Append(token + tokens[i + 1]).Append(" ");
      		i++;
      	}
      	// [...]
      }
      

      Thân!

      Trả lời
  2. Bạn có thể cho mình hỏi 2 dòng lệnh sau có tác dụng gì ko ạ ?

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

    expression = Regex.Replace(expression, @”(\+|\-|\*|\/|\%)(\+|\*|\/|\%)”, match =>
    match.Value[0].ToString());

    Trả lời
  3. anh ơi nếu mà chuỗi infix có dạng số thực và có cả biến và mũ nữa thì phải làm sao??

    Nếu phải chuyển chuỗi
    0.02×2+15x+6
    thành chuỗi postfix thì sao?
    giả sử biến ở đây là x , và quy ước các con số nằm sau chữ x là số mũ của x,
    các toán hạng nếu đọc ra được phải là:
    0.02×2, 15x, 6

    giả sử mỗi toán hạng đều có hai trường là hệ số và số mũ, khi ko viết gì sau x thì coi mũ là 1, khi không có x thì coi mũ là 0, khi chỉ có x (và số sau x) thì coi hệ số là 1, dấu hiệu để biết kết thúc phần chữ số của số mũ là gặp dấu toán tử, dấu đóng (hay mở ngoặc). Giả thiết ko có mũ âm và mũ thập phân.

    các toán hạng có thể có dấu âm, biểu thức trong ngoặc có thể có dấu âm (dấu ngoài cặp ngoặc), biểu thức trong ngoặc có thể có mũ (con số đứng ngay sau dấu đóng ngoặc).

    Bây giờ vấn đề là phải chuyển được biểu thúc dạng trên sang kiểu postfix để tính toán ( tính toán trên các đa thức, phân thức )

    Thuật toán chuyển kiểu này thực sự là em nghĩ mãi ko ra, mong anh giúp giùm

    Trả lời
  4. Bạn có thể coi x là một toán tử 2 ngôi như thế sẽ dễ xử lý hơn. Vấn đề của bạn có thể dùng Regular expression để giải quyết tuy nhiên đây là cách không nên sử dụng nên như bài của bạn đặt nặng vấn đề thuật toán.

    Bạn có thể test thử đoạn mã sau:

    public static void Main(string[] args)
    {
    
    	string s="-0.02x2+15x+6+-(23)x3";
    	
    	foreach(Match item in Regex.Matches(s,@"-{0,1}\({0,1}(\d|\.)*\){0,1}x\d*|\d+"))
    		Console.WriteLine(item.Value);
    	
    	Console.ReadKey(true);
    }
    

    Output:

    -0.02×2
    15x
    6
    -(23)x3

    Trả lời
  5. Cho mình hỏi 1 vấn đề ngoài phạm vi bài viết 1 tý.
    Mình muốn tách từng từ trong 1 đoạn văn bản. Câu lệnh mình như sau :
    MatchCollection matches = Regex.Matches(source, @”\w+”);
    Với câu lệnh trên mình đã tách ra từng từ nhưng có 1 vấn đề ở con nháy.
    Ví dụ: I’ll be there for you
    Các từ khác được tách bình thường nhưng với từ I’ll nó tách thành : I và ll.
    Ko biết mình mắc lỗi ở đâu ? Mong nhận được sự giúp đỡ từ bạn.

    Trả lời
      • Bạn xem giúp mình phần source code này nhé. Mình vẫn chưa giải quyết được vấn đề tách từ:

        Đây là hàm mình đọc file word :

        private void ReadDoc(string Path)
        {
        Word.ApplicationClass wordApp = new ApplicationClass();
        object file = Path;
        object nullobj = System.Reflection.Missing.Value;
        Word.Document doc = wordApp.Documents.Open(
        ref file, ref nullobj, ref nullobj,
        ref nullobj, ref nullobj, ref nullobj,
        ref nullobj, ref nullobj, ref nullobj,
        ref nullobj, ref nullobj, ref nullobj);
        doc.ActiveWindow.Selection.WholeStory();
        doc.ActiveWindow.Selection.Copy();
        IDataObject data = Clipboard.GetDataObject();
        source = data.GetData(DataFormats.UnicodeText).ToString();
        doc.Close();
        }

        Đây là hàm tách từ của mình :

        public static Dictionary OneWord(string source)
        {
        Dictionary dic = new Dictionary();
        MatchCollection matches = Regex.Matches(source, @"(\w+'\w+)|(\w+)");
        foreach (Match m in matches)
        {
        if (dic.Keys.Contains(m.Value.ToLower()))
        dic[m.Value.ToLower()] = dic[m.Value.ToLower()] + 1;
        else
        dic.Add(m.Value.ToLower(), 1);
        }
        return dic;
        }

  6. Mình đang có vấn đề ở chỗ tìm kiếm tiếng việt. Khi người dùng đánh từ khóa vào
    Ví dụ : con meo thì làm sao để ra kết quả là con mèo hoặc con méo, con mẹo… Và dữ liệu lưu trữ là có dấu hay ko dấu ? Bạn giúp mình nhé.

    Trả lời

Gửi phản hồ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 Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s