Thứ bảy, ngày 3 tháng 12 năm 2016

C# – Chuyển chuỗi biểu thức thành Expression Tree

Ngày đăng: 11/3/2012, 1:46:51AM | Lượt xem: 2,557
Hot!

ExpressionTree trong .Net là kĩ thuật rất hiệu quả để tính giá trị các biểu thức toán học. Tuy nhiên như trong bài Cơ bản về Expression Tree (C#) bạn cũng thấy là API này không cho phép ta parse một chuỗi văn bản thành ExpressionTree. Vậy mục đích của tôi trong bài viết là xây dựng một thư viện cho phép thực hiện điều này, qua đó bạn có thể phát triển và dùng Expression Tree như một trình thông dịch vô cùng hiệu quả.

ExpressionTree trong .Net là kĩ thuật rất hiệu quả để tính giá trị các biểu thức toán học. Tuy nhiên như trong bài Cơ bản về Expression Tree (C#) bạn cũng thấy là API này không cho phép ta parse một chuỗi văn bản thành ExpressionTree. Vậy mục đích của tôi trong bài viết là xây dựng một thư viện cho phép thực hiện điều này, qua đó bạn có thể phát triển và dùng Expression Tree như một trình thông dịch vô cùng hiệu quả.

Thay vì cung cấp link để tải tôi sẽ cung cấp source code đầy đủ chỉ trong 4 tập tin Token.cs, Scanner.cs, Parser.cs và Program.cs.


Phân tích ngữ pháp


Một bước quan trọng mà ta cần làm trước khi xây dựng chương trình là tìm hiểu và phân tích cú pháp của biểu thức toán học. May mắn thay, việc xây dựng ngữ pháp cho các biểu thức không tốn quá nhiều thời gian vì bạn có thể tìm thấy dễ dàng trong các tài liệu về trình biên dịch hoặc ngôn ngữ lập trình. Trích đoạn ngữ pháp dưới đây tôi sử dụng phần mềm GOLD Parser Builder để tạo ra. Phần mềm này nằm trong dự án “Design And Development Of A Grammar Oriented Parsing System” của Devin D. Cook. Nếu có hứng thú với dự án này, bạn có thể tham khảo đầy đủ tài liệu, ví dụ mẫu cũng như các công cụ cần thiết tại địa chỉ sau: http://www.devincook.com/goldparser/.

Quay lại vấn đề chính, ta sẽ phân tích đoạn ngữ pháp sau:

Mathematical and Comparision Expressions Grammar

Đầu tiên kí hiệu ::= được hiểu nôm na là “được định nghĩa bởi”, có thể coi những dòng có chứa kí hiệu này là luật hoặc luật sinh. Kí hiệu “|” cũng tương tự như OR hoặc “|” trong regular expression. Ví dụ với luật đơn giản sau:

<Value>       ::= NumberLiteral | ‘(‘ <Expression> ‘)’

Được hiểu là <Value> có thể được tạo thành bởi một dãy chữ số HOẶC một biểu thức được bao trong cặp ngoặc đơn.

Như bạn thấy <Expression> được tạo ra từ các biểu thức với các toán tử so sánh hoặc cộng/trừ (1). Biểu thức cộng/trừ lại được tạo thành từ những biểu thức nhân/chia (2) và biểu thức này lại được tạo ra từ các <Value> và -<Value> với các toán tử unary (+/-).

Như vậy các loại biểu thức được tạo nên từ những loại biểu thức khác với độ ưu tiên cao hơn. Độ ưu tiên lớn nhất là biểu thức trong cặp ngoặc đơn, tiếp đến là toán tử unary (+/-). Vấn đề này rất cơ bản nên không cần bàn nhiều tới, vấn đề chính của ta là làm sao hiện thực đoạn ngữ pháp trên để xây dựng cấu trúc cho một chuỗi biểu thức. Bạn có thể dễ dàng hiểu toàn bộ mã nguồn của chương trình bằng cách so sánh với đoạn ngữ pháp trên.

Lớp Token

Chứa các định nghĩa và cấu trúc về token:

using System;

namespace String2ExpressionTree
{

    enum TokenType
    {
        EOF = 0,

        Number,

        Add,
        Subtract,
        Multiply,
        Divide,
        LParen, // (
        RParen, // )
        Equal,
        GreaterThan,
        GreaterThanOrEqual,
        LessThan,
        LessThanOrEqual,
    }
    struct Token
    {
        public string Value;
        public TokenType Type;

        public Token(string value, TokenType type)
        {
            Value = value;
            Type = type;
        }
        public override string ToString()
        {
            return Value;
        }

        #region Static Properties

        public static Token EOF
        {
            get { return new Token("EOF", TokenType.EOF); }
        }
        public static Token Add
        {
            get { return new Token("+", TokenType.Add); }
        }
        public static Token Subtract
        {
            get { return new Token("-", TokenType.Subtract); }
        }
        public static Token Multiply
        {
            get { return new Token("*", TokenType.Multiply); }
        }
        public static Token Divide
        {
            get { return new Token("/", TokenType.Divide); }
        }
        public static Token LParen
        {
            get { return new Token("(", TokenType.LParen); }
        }
        public static Token RParen
        {
            get { return new Token(")", TokenType.RParen); }
        }
        public static Token Equal
        {
            get { return new Token("==", TokenType.Equal); }
        }
        public static Token GreaterThan
        {
            get { return new Token(">", TokenType.GreaterThan); }
        }
        public static Token GreaterThanOrEqual
        {
            get { return new Token(">=", TokenType.GreaterThanOrEqual); }
        }
        public static Token LessThan
        {
            get { return new Token("<", TokenType.LessThan); }
        }
        public static Token LessThanOrEqual
        {
            get { return new Token("<=", TokenType.LessThanOrEqual); }
        }
        #endregion
    }

}

Lớp Scanner


Lớp này dùng để đọc từng token từ biểu thức thông qua phương thức Next().

using System;
using System.IO;
using System.Text;

namespace String2ExpressionTree
{
    class Scanner
    {
        const char EOF = '\0';
        string _input;
        int _index = -1;
        char _ch;

        public Scanner(string input)
        {
            _input = input;
        }
        private void Read()
        {
            _index++;
            if (_index < _input.Length)
                _ch = _input[_index];
            else
                _ch = EOF;
        }

        public Token Next()
        {
            Read();

            if (_index < _input.Length)
            {
                while (Char.IsWhiteSpace(_ch))
                {
                    Read();
                }

                if (char.IsDigit(_ch)) // number
                {
                    StringBuilder str = new StringBuilder();

                    while (Char.IsDigit(_ch) || _ch == '.')
                    {
                        str.Append(_ch);
                        Read();
                    }
                    _index--;

                    return new Token(str.ToString(), TokenType.Number);
                }
                else
                {
                    switch (_ch)
                    {
                        case '+':
                            return Token.Add;
                        case '-':
                            return Token.Subtract;
                        case '*':
                            return Token.Multiply;
                        case '/':
                            return Token.Divide;
                        case '(':
                            return Token.LParen;
                        case ')':
                            return Token.RParen;
                        case '=':
                            Read();
                            if (_ch == '=') return Token.Equal;
                            throw new InvalidOperationException("equalily operator must be '=='");
                        case '>':
                            Read();
                            if (_ch == '=') return Token.GreaterThanOrEqual;
                            _index--;
                            return Token.GreaterThan;
                        case '<':
                            Read();
                            if (_ch == '=') return Token.LessThanOrEqual;
                            _index--;
                            return Token.LessThan;
                        default:
                            throw new Exception("Invalid character: " + _ch);
                    }

                }

            }
            return Token.EOF;

        }

    }
}

Lớp Parser


Đây là “trái tim” của chương trình  với chức năng chính là chuyển đổi chuỗi biểu thức thành một đối tượng System.Linq.Expressions.Expression duy nhất. Với các phương thức sau:

-          bool Read(): Đọc token tiếp theo, trả về false nếu đã đọc đến token kết thúc (EOF- End Of File)

-          bool Read(Token): đọc token tiếp theo và kiểm tra nó có cùng loại token truyền vào không, nếu không sẽ ném ra ngoại lệ để ngừng việc xử lý. Phương thức này dùng kiểm tra tính hợp lệ của biểu thức trong một số trường hợp.

-          Các phương thức để tạo các Binary Expression: các phương thức này có chung đặc điểm là tạo Expression bên trái (left hand side), sau đó tạo Expression bên phải và dựa vào kiểu của token mà kết hợp hai Expression này để tạo thành một Expression mới. Nếu như toán tử đọc được không phù hợp, phương thức chỉ trả về Expression bên trái toán tử.

-          Phương thức ValueExpression(): trả về ConstantExpression (số) hoặc một biểu thức trong cặp ngoặc đơn (luật 5).

Mô hình làm việc của lớp này được minh họa như hình sau, đây là cơ chế mà hầu hết các chương trình tính giá trị biểu thức sử dụng.

Parser Class-Methods Simulation

using System;
using System.Linq.Expressions;

namespace String2ExpressionTree
{
    class Parser
    {
        private Scanner _scanner;
        private Token _token;

        public Parser(Scanner scanner)
        {
            this._scanner = scanner;
        }

        public Expression Parse()
        {
            _token = _scanner.Next();

            Expression expr = CompareExpression();

            Check(Token.EOF);

            return expr;
        }

        private bool Read()
        {
            if (_token.Type == TokenType.EOF)
                return false;

            _token = _scanner.Next();

            return _token.Type != TokenType.EOF;
        }

        private bool Check(Token token)
        {
            if (!_token.Equals(token))
                throw new Exception("'" + token + "' expected.");

            return Read();
        }

        private Expression CompareExpression()
        {
            Expression lhs = AddExpression();

            if (_token.Type == TokenType.Equal ||
                _token.Type == TokenType.GreaterThan || _token.Type == TokenType.LessThan ||
                _token.Type == TokenType.GreaterThanOrEqual || _token.Type == TokenType.LessThanOrEqual)
            {
                TokenType type = _token.Type;

                Read();

                Expression rhs = CompareExpression();

                switch (type)
                {
                    case TokenType.Equal:
                        lhs = Expression.Equal(lhs, rhs);
                        break;
                    case TokenType.GreaterThan:
                        lhs = Expression.GreaterThan(lhs, rhs);
                        break;
                    case TokenType.GreaterThanOrEqual:
                        lhs = Expression.GreaterThanOrEqual(lhs, rhs);
                        break;
                    case TokenType.LessThan:
                        lhs = Expression.LessThan(lhs, rhs);
                        break;
                    case TokenType.LessThanOrEqual:
                        lhs = Expression.LessThanOrEqual(lhs, rhs);
                        break;
                }

            }

            return lhs;
        }

        private Expression AddExpression()
        {
            Expression lhs = MultiplyExpression();

            while (_token.Type == TokenType.Add || _token.Type == TokenType.Subtract)
            {
                TokenType type = _token.Type;

                Read();

                Expression rhs = MultiplyExpression();

                lhs = type == TokenType.Add ? Expression.Add(lhs, rhs) : Expression.Subtract(lhs, rhs);

            }

            return lhs;
        }

        private Expression MultiplyExpression()
        {
            Expression lhs = UnaryExpression();

            while (_token.Type == TokenType.Multiply || _token.Type == TokenType.Divide)
            {
                TokenType type = _token.Type;

                Read();

                Expression rhs = UnaryExpression();

                lhs = type == TokenType.Multiply ? Expression.Multiply(lhs, rhs) : Expression.Divide(lhs, rhs);

            }

            return lhs;
        }

        private Expression UnaryExpression()
        {
            Expression ret = null;

            if (_token.Type == TokenType.Add || _token.Type == TokenType.Subtract)
            {
                TokenType type = _token.Type;
                Read();

                Expression expr = UnaryExpression();

                ret = type == TokenType.Add ? Expression.UnaryPlus(expr) : Expression.Negate(expr);
            }
            else
                ret = ValueExpression();

            return ret;
        }

        private Expression ValueExpression()
        {
            Expression ret = null;

            if (_token.Type == TokenType.Number)
            {
                ret = Expression.Constant(double.Parse(_token.Value));

                Read();
            }
            else if (_token.Type == TokenType.LParen)
            {
                Read();

                ret = CompareExpression();

                Check(Token.RParen);
            }
            else
                throw new Exception("Unexpected token: " + _token);

            return ret;
        }
    }
}

Kiểm tra kết quả

Program.cs:

/**********************************************************************
 * Y2 String2ExpressionTree
 * Author: Yin Yang
 * yinyang.it@gmail.com
 * http://yinyangit.wordpress.com
 *
 * Date: 27 March 2011
 * Lasted Update: 27 March 2011
 * Version 1.0
 **********************************************************************/
using System;
using System.Linq.Expressions;
using System.IO;

namespace String2ExpressionTree
{
class Program
{
    const string PROMPT = "# ";
    public static void Main()
    {
        Console.WriteLine("Y2 String to Expression Tree");
        Console.WriteLine("http://yinyangit.wordpress.com");

        while (true)
        {
            Console.Write(PROMPT);
            string input = Console.ReadLine().Trim();
            if (input == "")
            {
                Console.CursorTop--;
                continue;
            }

            if (string.Compare(input, "exit", true) == 0)
                break;

            Console.ForegroundColor = ConsoleColor.DarkCyan;
            try
            {
                Scanner scanner = new Scanner(input);
                Parser parser = new Parser(scanner);
                Expression expr = parser.Parse();

                Delegate func = Expression.Lambda(expr).Compile();

                Console.WriteLine("  "+func.DynamicInvoke());

            }
            catch (Exception e)
            {
                Console.WriteLine(e.Message);
            }
            Console.ResetColor();
        }
    }
}
}

Output một vài ví dụ của chương trình:
Y2 String 2 ExpressionTree

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
Copyright © 2011 - 2012 vietshare.vn by phamkhuong102@gmail.com doanhkisi2315@gmail.com. All rights reserved.