Outubro de 2015
Volume 30 - Número 10
C#: Um analisador de expressões de divisão e mesclagem em C#
Por Vassili Kaplan | Outubro de 2015 | Obter o Código: C#VB
Eu publiquei um novo algoritmo para analisar uma expressão matemática em C++ nas edições de maior e julho de 2015 no CVu Journal (consulte os itens 1 e 2 nas "Referências"). Foram precisos dois artigos porque um leitor atento, Silas S. Brown, encontrou um erro na implementação do primeiro algoritmo, então precisei realizar algumas alterações nele. Graças àquele leitor, o algoritmo amadureceu. Desde então, também corrigi outros erros menores. Agora, fornecerei uma implementação do algoritmo em C#.
Provavelmente você nunca precisará escrever códigos para analisar uma expressão matemática, mas as técnicas aplicadas no algoritmo podem ser usadas em outras situações, como para análise de cadeias de caracteres fora do padrão. Usando esse algoritmo você também pode definir novas funções para fazer qualquer coisa que possa desejar (como uma solicitação Web ou pedir uma pizza). Com pequenos ajustes, também pode criar seu próprio compilador C# para a sua nova linguagem de script personalizada. Além disso, você pode se interessar no próprio.
O algoritmo Edsger Dijkstra, publicado há mais de 50 anos em 1961, geralmente é usado para analisar expressões matemáticas (consulte o item 3 nas "Referências"). Mas é bom ter uma alternativa que, apesar de possuir a mesma complexidade, é mais fácil de implementar e estender, na minha opinião.
Observe que usarei o idioma "construtor virtual" para a implementação do alocador de função. Esse idioma foi introduzido em C++ por James Coplien (consulte o item 4 nas "Referências"). Espero que você também ache seu uso interessante no universo C#.
O algoritmo de divisão e mesclagem
O programa de demonstração na Figura 1 ilustra o algoritmo de divisão e mesclagem para análise de uma expressão matemática.
.png "Uma execução demonstrativa do algoritmo de divisão e mesclagem")
Figura 1 Uma execução demonstrativa do algoritmo de divisão e mesclagem
O algoritmo possui duas etapas. Na primeira etapa, a cadeia de caracteres que contém a expressão é dividida em uma lista de objetos Cell, em que cada Cell se define da seguinte maneira:
class Cell
{
internal Cell(double value, char action)
{
Value = value;
Action = action;
}
internal double Value { get; set; }
internal char Action { get; set; }
}
O action é um caractere único que pode ser um dos sinais matemáticos: '*' (multiplicação), '/' (divisão), '+' (adicão), '-' (subtração) ou '^' (potência), ou um caractere especial marcando o fim de uma expressão, que codifiquei como ')'. O último elemento na lista de células a serem mescladas sempre terá a ação especial ')', ou seja, nenhum action, mas você pode usar qualquer outro símbolo ou parênteses.
Na primeira etapa, a expressão é dividida em tokens, que, por usa vez, são convertidos em células. Todos os tokens são separados por uma das expressões matemáticas ou um parêntese. Um token pode ser um número real ou uma cadeia de caracteres com o nome de uma função. A classe ParserFunction definida mais tarde toma conta de todas as funções a serem analisadas na cadeia de caracteres, ou por analisar uma cadeia de caracteres em um número. Ela também pode chamar o algoritmo de analise de cadeia de caracteres inteiro, de maneira recursiva. Se não há funções ou parênteses a serem analisados na cadeia de caracteres, não ocorrerá recursão.
Na segunda etapa, todas as células foram mescladas juntas. Primeiro, vejamos a segunda etapa, por ser um pouco mais direta do que a primeira.
Mesclar uma lista de células
A lista de células é mesclada uma por uma, de acordo com as prioridades das ações; ou seja, os sinais matemáticos. Essas prioridades são calculadas da seguinte maneira:
static int GetPriority(char action)
{
switch (action) {
case '^': return 4;
case '*':
case '/': return 3;
case '+':
case '-': return 2;
}
return 0;
}
Duas células podem ser mescladas se, e apenas se, a prioridade da ação da célula à esquerda na for menor do que a prioridade da ação da célula perto dela:
static bool CanMergeCells(Cell leftCell, Cell rightCell)
{
return GetPriority(leftCell.Action) >= GetPriority(rightCell.Action);
}
Mesclar células significa aplicar a ação da célula à esquerda aos valores das células à esquerda e à direita. A nova célula terá a mesma ação da célula à direita, como você pode ver na Figura 2.
Figura 2 Método de mesclagem de células
static void MergeCells(Cell leftCell, Cell rightCell)
{
switch (leftCell.Action)
{
case '^': leftCell.Value = Math.Pow(leftCell.Value, rightCell.Value);
break;
case '*': leftCell.Value *= rightCell.Value;
break;
case '/': leftCell.Value /= rightCell.Value;
break;
case '+': leftCell.Value += rightCell.Value;
break;
case '-': leftCell.Value -= rightCell.Value;
break;
}
leftCell.Action = rightCell.Action;
}
Por exemplo, mesclar Cell(8, '-') e Cell(5, '+') levará a uma nova Cell(8 – 5, '+') = Cell (3, '+').
Mas o que acontece se duas células não puderem ser mescadas porque a prioridade da célula à esquerda for menor do que a da célula à direita? Nesse caso, ocorrerá uma movimentação temporária para a próxima célula, à direita, para tentar mesclar com a célula ao lado, e assim por diante, de maneira recursiva. Assim que a célula à direita for mesclada com a célula perto dela, eu retornarei para a célula original à esquerda e tentarei mesclá-la novamente com a nova célula criada à direita, como ilustrado na Figura 3.
Figura 3 Mesclar uma lista de células
static double Merge(Cell current, ref int index, List<Cell> listToMerge,
bool mergeOneOnly = false)
{
while (index < listToMerge.Count)
{
Cell next = listToMerge[index++];
while (!CanMergeCells(current, next))
{
Merge(next, ref index, listToMerge, true /* mergeOneOnly */);
}
MergeCells(current, next);
if (mergeOneOnly)
{
return current.Value;
}
}
return current.Value;
}
Observe que, do lado de fora, esse método é chamado com o parâmetro mergeOneOnly definido como false, para não retornar antes de completar a mesclagem inteira. Em comparação, quando o método de mesclagem for chamado de maneira recursiva (quando as células à esquerda e à direita não puderem ser mescladas devido às suas prioridades), mergeOneOnly será definido como true, pois quero retornar para onde estava assim que completar uma mesclagem com o método MergeCells.
Observe também que o valor retornado com método Merge é o próprio resultado da expressão.
Dividir uma expressão em uma lista de células
A primeira parte do algoritmo divide uma expressão em uma lista de células. Nessa etapa, a precedência do sinal matemático é desconsiderada. Primeiro, a expressão é dividida em uma lista de tokens. Todos os tokens são serparados por qualquer sinal matemático ou por um parêntese de abertura ou fechamento. Os parênteses podem, mas não precisam, ter uma função associada; por exemplo, "1- sin(1-2)" possui uma função associada, mas "1- (1-2)" não.
Primeiro, vejamos o que acontece quando não há funções ou parênteses, apenas uma expressão contendo números reais e sinais matemáticos entre eles. Nesse caso, apenas crio células com um número real e uma ação consequente. Por exemplo, dividir "3-2*4" leva a uma lista com três células:
Split (“3-2*4”) = { Cell(3, ‘-’), Cell(2, ‘*‘), Cell(3, ‘)’) }
A última célula terá sempre uma ação especial END_ARG que defino como:
const char END_ARG = ')';
Ela pode ser alterada para qualquer coisa, mas nesse caso o parêntese de abertura correspondente START_ARG também deve ser considerado, que defino como:
const char START_ARG = '(';
Se um dos tokens for uma função ou uma expressão entre parênteses, o algoritmo de divisão e mesclagem é aplicado a ele usando recursão. Por exemplo, se a expressão for "(3-1)-1," o algoritmo inteiro entre parênteses será aplicado à expressão antes:
Split(“(3-1)-1”) = Split( “[SplitAndMerge(“3-1”)] - 1”) = { Cell(2, ‘-’), Cell(1, ‘)’) }
A função que realiza a divisão é LoadAndCalculate, como exibida na Figura 4.
Figure 4 Método LoadAndCalculate
public static double LoadAndCalculate(string data, ref int from, char to = END_LINE)
{
if (from >= data.Length || data[from] == to)
{
throw new ArgumentException("Loaded invalid data: " + data);
}
List<Cell> listToMerge = new List<Cell>(16);
StringBuilder item = new StringBuilder();
do // Main processing cycle of the first part.
{
char ch = data[from++];
if (StillCollecting(item.ToString(), ch, to))
{ // The char still belongs to the previous operand.
item.Append(ch);
if (from < data.Length && data[from] != to)
{
continue;
}
}
// I am done getting the next token. The getValue() call below may
// recursively call loadAndCalculate(). This will happen if extracted
// item is a function or if the next item is starting with a START_ARG '(.'
ParserFunction func = new ParserFunction(data, ref from, item.ToString(), ch);
double value = func.GetValue(data, ref from);
char action = ValidAction(ch) ? ch
: UpdateAction(data, ref from, ch, to);
listToMerge.Add(new Cell(value, action));
item.Clear();
} while (from < data.Length && data[from] != to);
if (from < data.Length && (data[from] == END_ARG || data[from] == to))
{ // This happens when called recursively: move one char forward.
from++;
}
Cell baseCell = listToMerge[0];
int index = 1;
return Merge(baseCell, ref index, listToMerge);
}
O método LoadAndCalculate adiciona todas as células à lista listToMerge e depois chama a segunda parte do algoritmo de análise, a função de mesclagem. O item StringBuilder segurará o token atual, adicionando caracteres um por um a ele assim que forem lidos da cadeia de caracteres da expressão.
O método StillCollecting verifica se os caracteres para o token atual ainda estão sendo coletados. Este não é o caso se o caractere atual for END_ARG ou qualquer outro caractere "to" especial (como uma vírgula, se os argumentos de análise forem sepradados por uma vírgula; fornecerei um exemplo disso usando a função de potência mais tarde). Além disso, o token não está sendo mais coletado se o caractere atual for uma ação válida ou um START_ARG:
static bool StillCollecting(string item, char ch, char to)
{
char stopCollecting = (to == END_ARG || to == END_LINE) ?
END_ARG : to;
return (item.Length == 0 && (ch == '-' || ch == END_ARG)) ||
!(ValidAction(ch) || ch == START_ARG || ch == stopCollecting);
}
static bool ValidAction(char ch)
{
return ch == '*' || ch == '/' || ch == '+' || ch == '-' || ch == '^';
}
Eu descubro que o token atual parou de ser coletado ao receber um sinal matemático descrito no método ValidAction, ou parênteses definidos pelas constantes START_ARG ou END_ARG. Também há um caso especial que envolve um token "-" usado para denotar um número que começa com um sinal negativo.
Ao término dessa etapa de divisão, todas as subexpressões entre parênteses e todas as chamadas de função são eliminadas através das células recursivas para avaliação do algoritmo todo. Mas as ações resultantes dessas chamadas recursivas sempre terão a ação END_ARG, que não será correta no escopo global da expressão se a expressão calculada não estiver no final da expressão a ser avaliada. É por isso que a ação precisa ser atualizada após cada chamada recursiva, assim:
char action = ValidAction(ch) ? ch
: UpdateAction(data, ref from, ch);
O código para o método updateAction está na Figura 5.
Figure 5 Método Update Action
static char UpdateAction(string item, ref int from, char ch, char to)
{
if (from >= item.Length || item[from] == END_ARG || item[from] == to)
{
return END_ARG;
}
int index = from;
char res = ch;
while (!ValidAction(res) && index < item.Length)
{ // Look to the next character in string until finding a valid action.
res = item[index++];
}
from = ValidAction(res) ? index
: index > from ? index - 1
: from;
return res;
}
A análise do token extraído propriamente dita está no seguinte código na Figura 4:
ParserFunction func = new ParserFunction(data, ref from, item.ToString(), ch);
double value = func.GetValue(data, ref from);
Se o token extraído não for uma função, esse código tentará convertê-lo em uma cópia. Caso contrário, será chamada uma função adequada e registrada anteriormente, que, por sua vez, pode chamar o método LoadAndCalculate de maneira recursiva.
Funções definidas pelo usuário e padrão
Eu decidi implementar o alocador de função usando o idioma construtor virtual que foi primeiro publicado por James Coplien (consulte o item 4 nas "Referências"). No C#, geralmente isso é implementado usando um método alocar (consulte o item 5 nas "Referências") que usa uma classe alocar a mais para produzir o objeto necessário. Mas o padrão do projeto antigo de Coplien não necessita de um padrão de fachada para alocar a mais, e, ao invés disso, constrói um novo objeto imediatamente usando o membro de implementação m_impl, derivado da mesma classe:
private ParserFunction m_impl;
O construtor interno especial inicializa esse membro com a classe adequada. A classe atual do objeto de implementação m_impl criado depende dos parâmetros de entrada, como exibido na Figura 6.
Figura 6 Construtor virtual
internal ParserFunction(string data, ref int from, string item, char ch)
{
if (item.Length == 0 && ch == Parser.START_ARG)
{
// There is no function, just an expression in parentheses.
m_impl = s_idFunction;
return;
}
if (m_functions.TryGetValue(item, out m_impl))
{
// Function exists and is registered (e.g. pi, exp, etc.).
return;
}
// Function not found, will try to parse this as a number.
s_strtodFunction.Item = item;
m_impl = s_strtodFunction;
}
Um dicionário é usado para manter todas as funções do analisador. Esse dicionário mapeia o nome da cadeia de caracteres da função (como "sin") ao próprio objeto implementando essa função:
private static Dictionary<string, ParserFunction> m_functions =
new Dictionary<string, ParserFunction>();
Usuários do analisadores podem adicionar quantas funções quiserem, chamando o seguinte método na classe base ParserFunction:
public static void AddFunction(string name, ParserFunction function)
{
m_functions[name] = function;
}
O método GetValue é chamado na ParserFunction criada, mas o trabalho mesmo é feito na função implementar, que substitui o método avaliar da classe base:
public double GetValue(string data, ref int from)
{
return m_impl.Evaluate(data, ref from);
}
protected virtual double Evaluate(string data, ref int from)
{
// The real implementation will be in the derived classes.
return 0;
}
As classes de implementação de função, derivadas da classe ParserFunction, não usarão o construtor interno na Figura 6. Ao invés disso, usarão o seguinte construtor da classe base.
public ParserFunction()
{
m_impl = this;
}
Duas funções "padrão" especiais são usadas no construtor ParserFunction na Figura 6:
private static IdentityFunction s_idFunction = new IdentityFunction();
private static StrtodFunction s_strtodFunction = new StrtodFunction();
A primeira é a função identidade; será chamada para analisar qualquer expressão entre parênteses que não possua uma função associada.
class IdentityFunction : ParserFunction
{
protected override double Evaluate(string data, ref int from)
{
return Parser.LoadAndCalculate(data, ref from, Parser.END_ARG);
}
}
A segunda função é uma "catchall", chamada quando não for encontrada nenhuma função que corresponda ao último token extraído. Isso acontecerá quando o token extraído não for um número real nem uma função implementada. No segundo caso, uma exceção será incluída:
class StrtodFunction : ParserFunction
{
protected override double Evaluate(string data, ref int from)
{
double num;
if (!Double.TryParse(Item, out num)) {
throw new ArgumentException("Could not parse token [" + Item + "]");
}
return num;
}
public string Item { private get; set; }
}
Todas as outras funções podem ser implementadas pelo usuário; a mais simples é uma função pi:
class PiFunction : ParserFunction
{
protected override double Evaluate(string data, ref int from)
{
return 3.141592653589793;
}
}
Uma implementação mais comum é uma função exp:
class ExpFunction : ParserFunction
{
protected override double Evaluate(string data, ref int from)
{
double arg = Parser.LoadAndCalculate(data, ref from, Parser.END_ARG);
return Math.Exp(arg);
}
}
Há pouco disse que forneceria um exemplo usando uma função de potência, que requer dois argumentos separados por uma vírgula. Para escrever uma função que requer vários argumentos separados por um separador personalizado, faça assim:
class PowFunction : ParserFunction
{
protected override double Evaluate(string data, ref int from)
{
double arg1 = Parser.LoadAndCalculate(data, ref from, ',');
double arg2 = Parser.LoadAndCalculate(data, ref from, Parser.END_ARG);
return Math.Pow(arg1, arg2);
}
}
Qualquer número de funções pode ser adicionado ao algoritmo a partir do código do usuário, assim:
ParserFunction.AddFunction("pi", new PiFunction());
ParserFunction.AddFunction("exp", new ExpFunction());
ParserFunction.AddFunction("pow", new PowFunction());
Conclusão
O algoritmo de divisão e mesclagem apresentado aqui posso complexidade O(n) se n for o número de caracteres na cadeia da expressão. Isso ocorre porque cada token será somente leitura apenas uma vez durante a etapa de divisão, e então, no cenário mais pessimista, haverá no máximo comparações 2(m - 1) – 1 na etapa de mesclagem, em que m é o número de células criadas na primeira etapa.
Assim, o algoritmo tem a mesma complexidade de tempo do que o algoritmo de Dijkstra (consulte o item 3 nas "Referências"). Em comparação com o algoritmo de Dijkstra, pode haver uma pequena desvantagem, por usar recursão. Por outra mão, acredito que o algoritmo de divisão e mesclagem é mais fácil de implementar, exatamente devido à recursão, e também mais fácil de estender com a sintaxe, as funções e os sinais personalizados.
Referências
- V. Kaplan, "Split and Merge Algorithm for Parsing Mathematical Expressions", CVu, 27-2, maio de 2015, bit.ly/1Jb470l
- V. Kaplan, "Split and Merge Revisited", CVu, 27-3, julho de 2015, bit.ly/1UYHmE9
- E. Dijkstra, Shunting-yard algorithm, bit.ly/1fEvvLI
- J. Coplien, "Advanced C++ Programming Styles and Idioms" (p. 140), Addison-Wesley, 1992
- E. Gamma, R. Helm, R. Johnson e J. Vlissides, "Design Patterns: Elements of Reusable Object-Oriented Software,” Addison-Wesley Professional Computing Series, 1995
Vassili Kaplan é ex-desenvolvedor do Microsoft Lync. Ele é apaixonado pela programação em C# e C++. Atualmente, ele mora em Zurique, Suíça, e trabalha como autônomo para vários bancos Você pode encontrá-lo em iLanguage.ch.
Agradecemos ao seguinte especialista técnico da Microsoft pela revisão deste artigo: James McCaffrey