Algorthrim – Tính giá trị của biểu thức toán học có sử dụng biến

Dựa vào kĩ thuật tính toán giá trị biểu thức số học trong bài Algorithm – Tính giá trị của biểu thức tiền tố và hậu tố , bạn có thể phát triển để viết một chương trình tính toán đơn giản có sử dụng biến. Việc hiện thực không quá phức tạp cũng như không đòi hỏi những kĩ thuật nâng cao. Để minh họa, trong bài này tôi sẽ viết một trình thông dịch toán học với các chức năng tính toán và nhập xuất cơ bản với tên gọi: Y2 Math Interpreter.

Download sourcecode+demo (VS 2010)

Chương trình này sử dụng thư viện Y2Expression đi kèm với chương trình Y2 Expression Convertor 1.2.1 (update 25 March 2011) để tính giá trị của biểu thức. Thư viện này trong bài được tôi bổ sung thêm phương thức EvaluateInfix() để tính giá trị của chuỗi biểu thức trung tố. Phần điều khiển chính của chương trình nằm trong lớp Y2MathInterpreter.

Chương trình này là một ứng dụng kiểu Console cho phép người dùng nhập từng dòng lệnh và thực thi. Bạn cũng có thể thực thi một tập tin thuần văn bản bao gồm các lệnh mà chương trình hỗ trợ. Trong phần ví dụ bạn sẽ thấy rõ hơn cách mà chương trình hoạt động.

Chương trình hiện tại có ngữ pháp đơn giản như sau:

{String Char} = {Printable} – [“]
StringLiteral = ‘”‘{String Char}*'”‘
NumberLiteral = {Digit}+
| {Digit}+’.'{Digit}+
Identifier = {Letter}{AlphaNumeric}*

::= write
| writeln
| readn Identifier
| run StringLiteral
| Identifier ‘=’

::= Identifier
| NumberLiteral
|

!*
là biểu thức toán học được lược bỏ để đơn giản ngữ pháp
*!

Đầu tiên ta khai báo đối tượng Dictionary<TKey,TValue> để lưu biến (bao gồm tên và giá trị kiểu double). Có thể hiểu đây là một phiên bản thu nhỏ của bảng danh biểu (symbol table) được dùng để phân tích ngôn ngữ lập trình.

Dictionary<string, double> _variables;

Hai phương thức để lấy và thêm phần tử vào tập hợp trên:

private double GetValue(string name)
{
    if (_variables.ContainsKey(name))
        return _variables[name];
    throw new Exception("Could not find variable '" + name + "'");
}

private void SetValue(string name, double value)
{
    if (_variables.ContainsKey(name))
        _variables[name] = value;
    else
        _variables.Add(name, value);
}

Trước khi làm việc với biến, ta cần một phương thức để kiểm tra tính hợp lệ của tên biến. Tương tự như các ngôn ngữ lập trình khác, ta cho phép đặt tên biến bắt đầu với dấu dâu gạch dưới “_” (underscore) và chữ cái, theo sau đó có thể là chữ cái, chữ số và dấu “_”. Ngoài ra cần đảm bảo tên biến không trùng với một số từ khóa hoặc toán tử mà chương trình sử dụng. Phương thức sau đảm nhận công việc này bằng cách sử dụng một chuỗi pattern regex:

private bool IsValidName(string name)
{
    if (ExprHelper.IsOperator(name))
        return false;
    return Regex.Match(name, @"^[a-z|A-Z|_]\w*$").Success;
}

Một phương thức khác không thể thiếu là tính toán giá trị biểu thức, tất nhiên bạn có thể đoán ngay ra là ta sẽ là sử dụng thư viện Y2Expression như tôi đã nói trước. Tuy nhiên vì đây biểu thức có chứa biến, ta sẽ làm một thao tác nhỏ là tìm tất cả các token có dạng tên biến (dựa vào chuỗi pattern trong phương thức IsValidName() trên) và thay thế phần tên đó bằng giá trị của nó lấy từ đối tượng Dictionary.

private double EvaluateExpression(string expr)
{
    MatchCollection vars = Regex.Matches(expr, @"[a-z|A-Z|_]\w*");
    for (int i = 0; i < vars.Count; i++)
    {
        if (!ExprHelper.IsOperator(vars[i].Value))
            expr = expr.Replace(vars[i].Value, GetValue(vars[i].Value).ToString());
    }
    try
    {
        return Y2Expression.EvaluateInfix(expr);
    }
    catch
    {
        throw new Exception("Invalid expression: '" + expr + "'");
    }

}

Cơ chế hoạt động

Chương trình này sẽ phân tách từng câu lệnh theo dòng, vì thế ta không cần kí tự kết thúc. Phương thức sau sẽ đọc từng dòng của văn bản thông qua TextReader và thực thi chúng:

public void Process(TextReader reader)
{
    while (reader.Peek() >= 0)
        ProcessLine(reader.ReadLine());
}

Phương thức thực thi một dòng lệnh ProcessLine() dựa vào cú pháp của câu lệnh để chia các câu lệnh thành hai loại: gán giá trị cho biến và gọi hàm:

public void ProcessLine(string line)
{
    // [...]
    if (Regex.Match(line, "^[^\"]+=").Success)
        ProcessAssignment(line);
    else
        ProcessFunction(line);

    // [...]
}

Chuỗi regular expression “^[^\”]+=” nhằm kiểm tra phần văn bản đầu dòng lệnh tồn tại một dấu “=” và không có bất kì dấu nháy kép (“) nào trước nó. Nếu câu lệnh truyền vào thỏa điều kiện này, ta đưa nó vào nhóm lệnh gán và gọi phương thức ProcessAssignment() để tiếp tục, ngược lại phương thức ProcessFunction() sẽ tiếp tục công việc và coi đó như một lệnh gọi hàm.

Hai phương thức này được cài đặt như sau:

private void ProcessAssignment(string line)
{
    string[] str = line.Split('=');
    if (!IsValidName(str[0]))
        throw new Exception("Invalid variable name: '" + str[0] + "'");
    if (str.Length != 2)
        throw new FormatException("Invalid statement");
    SetValue(str[0], EvaluateExpression(str[1]));
}

private void ProcessFunction(string line)
{
    // [...]
    int index = line.IndexOf(' ');
    string func = line.Substring(0, index).Trim();
    string param = line.Substring(index + 1).Trim();

    switch (func.ToUpper())
    {
        case "WRITE":
        case "WRITELN":
        case "RUN":
            if (param.StartsWith("\"")) // string literal
            {
                // [...]
                if (func.Equals("RUN", StringComparison.OrdinalIgnoreCase))
                {
                    TextReader reader = new StreamReader(param.Trim('"'));
                    Process(reader);
                }
                else if (func.Equals("WRITE", StringComparison.OrdinalIgnoreCase))
                    Console.Write(param);
                else
                    Console.WriteLine(param);
            }
            else if (!func.Equals("RUN", StringComparison.OrdinalIgnoreCase))
                // "write expr" or "writeln expr"
                Console.Write(EvaluateExpression(param));
            else // run expr
                goto Error;
            break;

        case "READN":
            // [...]
            double d;
            if (!double.TryParse(Console.ReadLine(), out d))
                throw new FormatException("Incorrect input number.");
            SetValue(param, d);
            break;

        default:
            if (Regex.Match(param, @"[^\w]").Success)
                goto Error;
            throw new Exception("Could not find function '" + func + "'");
    }
    return;

Error:
    throw new Exception("Invalid statement: '" + line + "'");

}

Cuối cùng ta có phương thức Main() để chạy thử chương trình của mình:

private static void Main(string[] args)
{
    // [...]
    Y2MathInterpreter mathInter = new Y2MathInterpreter();
    while (true)
    {
        if (Console.CursorLeft > 0)
            Console.WriteLine();
        Console.Write(">>");
        string line = Console.ReadLine().Trim();

        if (line != "")
        {
            if (line.Equals("exit", StringComparison.OrdinalIgnoreCase))
                break;
            mathInter.ProcessLine(line);
        }

    }
}

Ví dụ

Bạn có thể nhập bất kì một biểu thức toán học này bao gồm các toán tử “*,/,+,-,%,^” bao gồm các hàm “sqrt, sin, cos” để gán cho một biến hoặc in kết quả ra bằng lệnh write. Ngoài ra bạn có thể tạo một file “a.txt” (hoặc tên bất kì) với các dòng sau để kiểm tra các lệnh của chương trình:

Writeln “”
Write “_Input a number: ”
Readn a
Write “sqrt(”
Write a
Write “) = ”
Write sqrt(a)

Đề phòng các lệnh đệ quy trong chương trình

Hàm (hay lệnh) Run trong chương trình để tiến hành thông dịch một tập tin dựa vào phương thức Process(TextReader). Như vậy bạn có thể tưởng tượng cơ chế hoạt động của chương trình có thể đi theo mô hình sau:

Thử tưởng tượng bạn có tập tin “a.txt” với lệnh sau:

Write “Test”

// […]

Run “a.txt”

Như thế khi bạn thực thi tập tin này trong chương trình thì sẽ là một vòng thực thi vô hạn cho đến khi tràn bộ nhớ: “Process is terminated due to StackOverflowException”.

Ta có thể “chữa cháy” cho vấn đề này một cách đơn giản bằng cách vô hiệu lệnh “run” trong tập tin. Như thế bất kì lời gọi từ một tập tin này đến một tập tin khác hay chính nó đều không thể thực hiện.:

public void Process(TextReader reader)
{
    while (reader.Peek() >= 0)
    {
        string line = reader.ReadLine();
        if (line.StartsWith("run ", StringComparison.OrdinalIgnoreCase) && !line.Contains("="))
            continue;
        ProcessLine(line);
    }
}

Phần kết

Mặc dù bạn thấy là chương trình hoạt động khá giống một trình biên dịch nhưng phần kiểm tra và xử lý mã lệnh (biểu thức) nhập từ người dùng khá rắc rối, khó phát triển và thiếu tính tổng quát. Nguyên nhân là do phần tính biểu thức tôi sử dụng lại của thư viện Y2Expression nên điều này là khó tránh khỏi. Trong bài viết sau tôi sẽ trình bày kĩ thuật phân tích và xây dựng biểu thức toán học theo một cấu trúc dữ liệu hoàn chỉnh.

https://yinyangit.wordpress.com