Serão agora descritos os processos para obter um leitor de expressões que envolvam conjuntos de objectos. De modo a atingir este objectivo é necessário, em primeiro lugar, definir a classe que representa o tipo de símbolo. Neste caso, será utilizado um enumerável no qual estão definidos todos os tipos de símbolos necessários à leitura.
enum ESymbolSetType
    {
        /// <summary>
        /// Qualquer carácter.
        /// </summary>
        ANY,

        /// <summary>
        /// O fim do ficheiro.
        /// </summary>
        EOF,

        /// <summary>
        /// A chaveta de abertura.
        /// </summary>
        LBRACE,

        /// <summary>
        /// A chaveta de fecho.
        /// </summary>
        RBRACE,

        /// <summary>
        /// O parêntesis recto de abertura.
        /// </summary>
        LBRACK,

        /// <summary>
        /// O parêntesis recto de fecho.
        /// </summary>
        RBRACK,

        /// <summary>
        /// Parêntesis de abertura.
        /// </summary>
        OPAR,

        /// <summary>
        /// Parêntesis de fecho.
        /// </summary>
        CPAR,

        /// <summary>
        /// O parêntesis angular de abertura.
        /// </summary>
        LANGLE,

        /// <summary>
        /// O parêntesis angular de fecho.
        /// </summary>
        RANGLE,

        /// <summary>
        /// A barra vertical.
        /// </summary>
        VBAR,

        /// <summary>
        /// A vírgula.
        /// </summary>
        COMMA,

        /// <summary>
        /// O espaço.
        /// </summary>
        SPACE,

        /// <summary>
        /// A mudança de linha.
        /// </summary>
        CHANGE_LINE,

        /// <summary>
        /// O símbolo de união.
        /// </summary>
        UNION,

        /// <summary>
        /// O símbolo de intersecção.
        /// </summary>
        INTERSECTION
    }

Facilmente se conclui que os símbolos UNION e INTERSECTION são aqueles que irão representar as respectivas operações sobre os conjuntos e os parêntesis curvos permitirão alterar a precedência. Os outros tipos de parêntesis irão delimitar expressões que representam os objectos do conjunto. Neste caso, como cada conjunto é delimitado por chavetas, estas terão de constituir parêntesis externos. Por exemplo, na expressão ({2*(1+3),4} union {1}) intersect {2}, os parêntesis curvos contidos no interior das chavetas, como parte da expressão 2*(1+3) serão delegados para o leitor de objectos pelo leitor de expressões.
O segundo passo consiste em implementar a classe que define os objectos que constituem os símbolos.
    class SetSymbol : ISymbol<string, ESymbolSetType>
    {
        private string symbolValue;

        private ESymbolSetType symbolType;

        public string SymbolValue
        {
            get
            {
                return this.symbolValue;
            }
            set
            {
                this.symbolValue = value;
            }
        }

        public ESymbolSetType SymbolType
        {
            get
            {
                return this.symbolType;
            }
            set
            {
                this.symbolType = value;
            }
        }
    }

Um símbolo é definido por um valor e uma classificação, a qual permite reduzir o número de estados necessários à máquina de estados que está na base do leitor.
Após a definição do símbolo, é necessária a criação de um leitor de símbolos a partir de uma cadeia de carácteres.
class SetSymbolReader : SymbolReader<CharSymbolReader<ESymbolSetType>, string, ESymbolSetType>
    {
        public SetSymbolReader(TextReader inputReader) : 
            base(new CharSymbolReader<ESymbolSetType>(inputReader))
        {
            this.inputStream.EndOfFileType = ESymbolSetType.EOF;
            this.inputStream.GenericType = ESymbolSetType.ANY;
            this.inputStream.RegisterCharType('{', ESymbolSetType.LBRACE);
            this.inputStream.RegisterCharType('}', ESymbolSetType.RBRACE);
            this.inputStream.RegisterCharType('[', ESymbolSetType.LBRACK);
            this.inputStream.RegisterCharType(']', ESymbolSetType.RBRACK);
            this.inputStream.RegisterCharType('(', ESymbolSetType.OPAR);
            this.inputStream.RegisterCharType(')', ESymbolSetType.CPAR);
            this.inputStream.RegisterCharType('<', ESymbolSetType.LANGLE);
            this.inputStream.RegisterCharType('>', ESymbolSetType.RANGLE);
            this.inputStream.RegisterCharType('|', ESymbolSetType.VBAR);
            this.inputStream.RegisterCharType(',', ESymbolSetType.COMMA);
            this.inputStream.RegisterCharType('\n', ESymbolSetType.CHANGE_LINE);
            this.inputStream.RegisterCharType(' ', ESymbolSetType.SPACE);
        }

        public override ISymbol<string, ESymbolSetType> Peek()
        {
            if (!this.started)
            {
                this.started = true;
            }

            if (this.bufferPointer == this.symbolBuffer.Count)
            {
                this.AddNextSymbolFromStream();
            }

            var result = new SetSymbol()
            {
                SymbolType = this.symbolBuffer[this.bufferPointer].SymbolType,
                SymbolValue = this.symbolBuffer[this.bufferPointer].SymbolValue
            };

            return result;
        }

        public override ISymbol<string, ESymbolSetType> Get()
        {
            if (!this.started)
            {
                this.started = true;
            }

            var result = this.Peek();
            if (this.bufferPointer < this.symbolBuffer.Count)
            {
                ++this.bufferPointer;
            }

            return result;
        }

        public override void UnGet()
        {
            if (this.bufferPointer > 0)
            {
                --this.bufferPointer;
            }
        }

        public override bool IsAtEOF()
        {
            return this.Peek().SymbolType.Equals(ESymbolSetType.EOF);
        }

        public override bool IsAtEOFSymbol(ISymbol<string, ESymbolSetType> symbol)
        {
            if (symbol == null)
            {
                throw new ArgumentNullException("symbol");
            }
            else
            {
                return symbol.SymbolType.Equals(ESymbolSetType.EOF);
            }
        }

        private void AddNextSymbolFromStream()
        {
            var readed = string.Empty;
            var state = 0;
            while (state != -1)
            {
                if (state == 0)
                {
                    var readedChar = this.inputStream.Get();
                    if (readedChar.SymbolType == ESymbolSetType.EOF)
                    {
                        this.symbolBuffer.Add(readedChar);
                        state = -1;
                    }
                    else if (readedChar.SymbolType == ESymbolSetType.ANY)
                    {
                        readed += readedChar.SymbolValue;
                        state = 1;
                    }
                    else
                    {
                        this.symbolBuffer.Add(readedChar);
                        state = -1;
                    }
                }
                else if (state == 1)
                {
                    var readedChar = this.inputStream.Peek();
                    if (readedChar.SymbolType == ESymbolSetType.ANY)
                    {
                        readed += readedChar.SymbolValue;
                        this.inputStream.Get();
                    }
                    else
                    {
                        var result = new SetSymbol() { SymbolValue = readed, SymbolType = ESymbolSetType.ANY };

                        if (readed == "union")
                        {
                            result.SymbolType = ESymbolSetType.UNION;
                        }
                        else if (readed == "intersection")
                        {
                            result.SymbolType = ESymbolSetType.INTERSECTION;
                        }

                        this.symbolBuffer.Add(result);
                        state = -1;
                    }
                }
            }
        }
    }

Observe-se que foi definida uma subclasse da SymbolReader parametrizada pela classe reponsável pela leitura de carácteres CharSymbolReader. No construtor do SymbolReader são mapeados os carácteres aos respectivos tipos. Convém notar que e leitura poderia ser realizada directamente sobre outras estruturas de dados sendo, portanto, o código da classe SymbolReader responsável pela respectiva interpretação.
Em quarto lugar, é necessário definir o leitor dos conjuntos.
class SetParser<ObjectType> : IParse<HashSet<ObjectType>, string, ESymbolSetType>
    {
        private ExpressionReader<HashSet<ObjectType>, string, ESymbolSetType> expressionReader;

        public SetParser(IParse<ObjectType, string, ESymbolSetType> elementsParser)
        {
            if (elementsParser == null)
            {
                throw new ArgumentNullException("elementsParser");
            }
            else
            {
                this.expressionReader = new ExpressionReader<HashSet<ObjectType>, string, ESymbolSetType>(
                    new HashSetParser(elementsParser));
                this.expressionReader.RegisterExternalDelimiterTypes(ESymbolSetType.OPAR, ESymbolSetType.CPAR);
                this.expressionReader.RegisterExternalDelimiterTypes(ESymbolSetType.LBRACK, ESymbolSetType.RBRACK);
                this.expressionReader.RegisterExternalDelimiterTypes(ESymbolSetType.LANGLE, ESymbolSetType.RANGLE);
                this.expressionReader.RegisterExternalDelimiterTypes(ESymbolSetType.LBRACK, ESymbolSetType.RANGLE);
                this.expressionReader.RegisterExternalDelimiterTypes(ESymbolSetType.LANGLE, ESymbolSetType.RBRACK);
                this.expressionReader.RegisterExternalDelimiterTypes(ESymbolSetType.VBAR, ESymbolSetType.VBAR);
                this.expressionReader.RegisterExternalDelimiterTypes(ESymbolSetType.VBAR, ESymbolSetType.RANGLE);
                this.expressionReader.RegisterExternalDelimiterTypes(ESymbolSetType.LANGLE, ESymbolSetType.VBAR);

                this.expressionReader.RegisterBinaryOperator(ESymbolSetType.COMMA, this.Concatenate, 0);

                this.expressionReader.AddVoid(ESymbolSetType.SPACE);
                this.expressionReader.AddVoid(ESymbolSetType.CHANGE_LINE);
            }
        }

        public bool TryParse(
            ISymbol<string, ESymbolSetType>[] symbolListToParse, 
            out HashSet<ObjectType> value)
        {
            var openSymbol = -1;
            for (int i = 0; i < symbolListToParse.Length; ++i)
            {
                var currentSymbol = symbolListToParse[i];
                if (currentSymbol.SymbolType == ESymbolSetType.LBRACE)
                {
                    openSymbol = i;
                    i = symbolListToParse.Length;
                }
                else if (currentSymbol.SymbolType != ESymbolSetType.SPACE && currentSymbol.SymbolType != ESymbolSetType.CHANGE_LINE)
                {
                    i = symbolListToParse.Length;
                }
            }

            if (openSymbol == -1)
            {
                value = default(HashSet<ObjectType>);
                return false;
            }
            else
            {
                var closeSymbol = -1;
                for (int i = symbolListToParse.Length - 1; i > openSymbol; --i)
                {
                    var currentSymbol = symbolListToParse[i];
                    if (currentSymbol.SymbolType == ESymbolSetType.RBRACE)
                    {
                        closeSymbol = i;
                        i = openSymbol;
                    }
                    else if (currentSymbol.SymbolType != ESymbolSetType.SPACE && currentSymbol.SymbolType != ESymbolSetType.CHANGE_LINE)
                    {
                        i = openSymbol;
                    }
                }

                if (closeSymbol == -1)
                {
                    value = default(HashSet<ObjectType>);
                    return false;
                }
                else
                {
                    var elementsNumber = closeSymbol - openSymbol - 1;
                    var elementsArray = new ISymbol<string, ESymbolSetType>[elementsNumber];
                    Array.Copy(symbolListToParse, openSymbol + 1, elementsArray, 0, elementsNumber);
                    var arraySymbolReader = new ArraySymbolReader<string, ESymbolSetType>(elementsArray, ESymbolSetType.EOF);
                    return this.expressionReader.TryParse(arraySymbolReader, out value);
                }
            }
        }

        /// <summary>
        /// Concatena dois conjuntos, isto é, determina a respectiva união.
        /// </summary>
        /// <param name="left">O primeiro conjunto.</param>
        /// <param name="right">O segundo conjunto.</param>
        /// <returns>O resultado da união.</returns>
        private HashSet<ObjectType> Concatenate(HashSet<ObjectType> left, HashSet<ObjectType> right)
        {
            var result = new HashSet<ObjectType>(left);
            result.UnionWith(right);
            return result;
        }

        private class HashSetParser : IParse<HashSet<ObjectType>, string, ESymbolSetType>
        {
            private IParse<ObjectType, string, ESymbolSetType> elementsParser;

            public HashSetParser(IParse<ObjectType, string, ESymbolSetType> elementsParser)
            {
                this.elementsParser = elementsParser;
            }

            /// <summary>
            /// Obtém o leitor dos elementos.
            /// </summary>
            public IParse<ObjectType, string, ESymbolSetType> ElementsParser
            {
                get
                {
                    return this.elementsParser;
                }
            }

            /// <summary>
            /// Tenta efectuar a leitura de um elemento e encapsulá-lo num conjunto.
            /// </summary>
            /// <param name="symbolListToParse">A lista de símbolos a ler.</param>
            /// <param name="value">O valor.</param>
            /// <returns>Verdadeiro caso a leitura seja bem sucedida e falso no caso contrário.</returns>
            public bool TryParse(ISymbol<string, ESymbolSetType>[] symbolListToParse, out HashSet<ObjectType> value)
            {
                var parsedObject = default(ObjectType);
                if (this.elementsParser.TryParse(symbolListToParse, out parsedObject))
                {
                    value = new HashSet<ObjectType>();
                    value.Add(parsedObject);
                    return true;
                }
                else
                {
                    value = default(HashSet<ObjectType>);
                    return false;
                }
            }
        }
    }

O leitor de conjuntos recebe como argumento do construtor um leitor de elementos. Este recorre-se da classe ExpressionReader para realizar a respectiva leitura considerando a vírgula que separa os objectos constituintes como sendo um operador de concatenação.
Finalmente, define-se o leitor da expressão.
class SetExpressionParser<ObjectType>
    {
        private ExpressionReader<HashSet<ObjectType>, string, ESymbolSetType> expressionParser;

        public SetExpressionParser(IParse<ObjectType, string, ESymbolSetType> elementParser)
        {
            if (elementParser == null)
            {
                throw new ArgumentNullException("elementParser");
            }
            else
            {
                this.expressionParser = new ExpressionReader<HashSet<ObjectType>, string, ESymbolSetType>(
                    new SetParser<ObjectType>(elementParser));
                this.expressionParser.RegisterExpressionDelimiterTypes(ESymbolSetType.OPAR, ESymbolSetType.CPAR);
                this.expressionParser.RegisterExternalDelimiterTypes(ESymbolSetType.LBRACE, ESymbolSetType.RBRACE);

                this.expressionParser.RegisterBinaryOperator(ESymbolSetType.UNION, this.Union, 0);
                this.expressionParser.RegisterBinaryOperator(ESymbolSetType.INTERSECTION, this.Intersection, 1);

                this.expressionParser.AddVoid(ESymbolSetType.SPACE);
                this.expressionParser.AddVoid(ESymbolSetType.CHANGE_LINE);
            }
        }

        public bool TryParse(SymbolReader<CharSymbolReader<ESymbolSetType>, string, ESymbolSetType> reader, out HashSet<ObjectType> value)
        {
            return this.expressionParser.TryParse(reader, out value);
        }

        /// <summary>
        /// Determina a reunião de dois conjuntos.
        /// </summary>
        /// <param name="left">O primeiro conjunto.</param>
        /// <param name="right">O segundo conjunto.</param>
        /// <returns>A união.</returns>
        private HashSet<ObjectType> Union(HashSet<ObjectType> left, HashSet<ObjectType> right)
        {
            var result = new HashSet<ObjectType>(left);
            result.UnionWith(right);
            return result;
        }

        /// <summary>
        /// Determina a intersecção de dois conjuntos.
        /// </summary>
        /// <param name="left">O primeiro conjunto.</param>
        /// <param name="right">O segundo conjunto.</param>
        /// <returns>A intersecção.</returns>
        private HashSet<ObjectType> Intersection(HashSet<ObjectType> left, HashSet<ObjectType> right)
        {
            var result = new HashSet<ObjectType>(left);
            result.IntersectWith(right);
            return result;
        }
    }

Esta classe recorre à classe ExpressionReader para efectuar a leitura da expressão. Esta é configurada no construtor utilizando o seguinte código.
this.expressionParser = new ExpressionReader<HashSet<ObjectType>, string, ESymbolSetType>(
                    new SetParser<ObjectType>(elementParser));
                this.expressionParser.RegisterExpressionDelimiterTypes(ESymbolSetType.OPAR, ESymbolSetType.CPAR);
                this.expressionParser.RegisterExternalDelimiterTypes(ESymbolSetType.LBRACE, ESymbolSetType.RBRACE);

                this.expressionParser.RegisterBinaryOperator(ESymbolSetType.UNION, this.Union, 0);
                this.expressionParser.RegisterBinaryOperator(ESymbolSetType.INTERSECTION, this.Intersection, 1);

                this.expressionParser.AddVoid(ESymbolSetType.SPACE);
                this.expressionParser.AddVoid(ESymbolSetType.CHANGE_LINE);

Registam-se os parêntesis curvos como sendo delimitadores de expressão. Estes permitem alterar a precedência na qual os operadores são aplicados. Por seu turno, as chavetas são registadas como sendo operadores externos. Neste caso, tudo o que for delimitado pelas chavetas é delegado para o leitor de conjuntos. As duas linhas subsequentes permitem registar os operadores de união e intersecção sendo a precedência do segundo superior à do primeiro. Finalmente são registados os símbolos que serão ignorados durante todo o processo.
O código que se segue permite expor um exemplo de utilização do que foi atrás apresentado.
public static void Main(string[] args)
        {
            var input = "  {1 , 5,  2,3}  intersection ({3,2} union {1,5})";
            var reader = new StringReader(input);
            var symbolReader = new SetSymbolReader(reader);
            var hashSetExpressionParser = new SetExpressionParser<int>(new IntegerParser<ESymbolSetType>());
            var parsed = default(HashSet<int>);
            if (hashSetExpressionParser.TryParse(symbolReader, out parsed))
            {
                Console.WriteLine("Elements in set are:");
                foreach (var element in parsed)
                {
                    Console.WriteLine(element);
                }
            }
            else
            {
                Console.WriteLine("Can't parse expression.");
            }
        }

Alguns leitores são disponibilizados pela livraria. Por exemplo, o código que se segue implementa uma função que permite realizar a leitura de um polinómio cujos coeficientes são fracções de números inteiros a partir de uma cadeia de carácters.
public UnivariatePolynomialNormalForm<Fraction<int>> Read(string polynomial)
        {
            var integerDomain = new IntegerDomain();
            var fractionField = new FractionField<int>(integerDomain);
            var integerParser = new IntegerParser<string>();
            var fractionParser = new FieldDrivenExpressionParser<Fraction<int>>(
                new SimpleElementFractionParser<int>(integerParser, integerDomain),
                fractionField);
            var conversion = new ElementFractionConversion<int>(integerDomain);
            var polInputReader = new StringReader(polynomial);
            var polSymbolReader = new StringSymbolReader(polInputReader, false);
            var polParser = new UnivariatePolynomialReader<Fraction<int>, CharSymbolReader<string>>(
                "x",
                fractionParser,
                fractionField);

            var result = default(UnivariatePolynomialNormalForm<Fraction<int>>);
            if (polParser.TryParsePolynomial(polSymbolReader, conversion, out result))
            {
                // O polinómio foi lido com sucesso.
                return result;
            }
            else
            {
                // Não é possível ler o polinómio.
                throw new Exception("Can't read integer polynomial.");
            }
        }

Para mais exemplos, o leitor é convidado a consultar as unidades de teste que são disponibilizadas com o código fonte.

Last edited Jul 3, 2014 at 9:52 PM by SergioMarques, version 3

Comments

No comments yet.