Partager via

Octobre 2015

Volume 30, numéro 10

Cet article a fait l'objet d'une traduction automatique.

C# - Un analyseur d’expression de fractionnement et de fusion en C#

Par Vassili Kaplan

J'ai publié un nouvel algorithme pour l'analyse d'une expression mathématique dans C++ dans les problèmes de mai à juillet 2015 du CVu Journal (voir les éléments 1 et 2 en « références »). Il a fallu deux articles, car un seul lecteur astucieux, Silas S. Brown, trouvé un bogue dans la première implémentation de l'algorithme, j'ai donc dû apporter des modifications à ce dernier. Grâce à ce lecteur, l'algorithme est devenu plus mature. J'ai également résolu quelques bogues plus petits depuis. Maintenant, je vais fournir une implémentation de l'algorithme corrigé dans c#.

Il n'est pas trop probablement jamais avoir à écrire du code pour analyser une expression mathématique, mais les techniques utilisés dans l'algorithme peuvent être appliquées à d'autres scénarios, tels que l'analyse des chaînes non standard. À l'aide de cet algorithme vous pouvez également facilement définir nouvelles fonctions de faire ce que vous voulez (par exemple, effectuer une requête Web pour commander une pizza). Avec légères modifications, vous pouvez également créer votre propre compilateur c# pour votre nouveau langage de script personnalisé. En outre, vous venez intéresser l'algorithme à part entière.

L'algorithme de Edsger Dijkstra publié plus de 50 ans en 1961, est souvent utilisé pour l'analyse des expressions mathématiques (voir l'article 3 dans « Références »). Mais il est intéressant de disposer d'une alternative qui, bien qu'il ait la complexité même du temps, est, à mon avis, plus facile à implémenter et à étendre.

Notez que je vais utiliser l'idiome « constructeur virtuel » pour l'implémentation de fabrique de fonction. Cet idiome a été introduit dans C++ par James Coplien (voir point 4 dans « Références »). J'espère que vous trouverez son utilisation intéressantes dans le langage c# monde, également.

L'algorithme de fractionnement et fusion

Le programme de démonstration dans Figure 1 illustre l'algorithme de fractionnement et fusion pour l'analyse d'une expression mathématique.

Une exécution de démonstration de l'algorithme de fractionnement et fusion
Figure 1 une démonstration exécution de l'algorithme de fractionnement et fusion

L'algorithme consiste en deux étapes. Dans la première étape, la chaîne contenant l'expression est divisée en une liste d'objets Cell, où chaque cellule est définie comme suit :

class Cell
{
  internal Cell(double value, char action)
  {
    Value = value;
    Action = action;
  }
  internal double Value  { get; set; }
  internal char   Action { get; set; }
}

L'action est un caractère unique qui peut être un des opérateurs mathématiques: ' *' (multiplication), « / » (division), '+' (addition), '-' (soustraction) ou ' ^' (power), ou un caractère spécial indiquant la fin d'une expression, dont je vous ai codé en dur comme '). » Le dernier élément dans la liste des cellules soient fusionnées est toujours avoir l'action spéciale »), », autrement dit, aucune action, mais vous pouvez utiliser n'importe quel autre symbole ou une parenthèse à la place.

Dans la première étape, l'expression est fractionnée en jetons qui sont ensuite converties en cellules. Tous les jetons sont séparées par une des expressions mathématiques ou une parenthèse. Un jeton peut être un nombre réel ou une chaîne avec le nom d'une fonction. La classe ParserFunction définie ultérieurement s'occupe de toutes les fonctions dans la chaîne à analyser, ou pour analyser une chaîne en nombre. Il peut également appeler la chaîne entière de l'analyse d'algorithme, de manière récursive. S'il y a pas de fonctions et sans parenthèses dans la chaîne à analyser, il n'y aura aucun récursivité.

Dans la deuxième étape, toutes les cellules sont fusionnées. Voyons tout d'abord la deuxième étape, car il est un peu plus simple que la première.

Fusion d'une liste des cellules

La liste des cellules est fusionné une par une en fonction des priorités des actions ; Autrement dit, les opérateurs mathématiques. Ces priorités sont calculées comme suit :

static int GetPriority(char action)
{
  switch (action) {
    case '^': return 4;
    case '*':
    case '/': return 3;
    case '+':
    case '-': return 2;
  }
  return 0;
}

Deux cellules peuvent être fusionnées uniquement si la priorité de l'action de la cellule sur la gauche n'est pas inférieure à la priorité de l'action de la cellule en regard de celle-ci :

static bool CanMergeCells(Cell leftCell, Cell rightCell)
{
  return GetPriority(leftCell.Action) >= GetPriority(rightCell.Action);
}

Fusion des moyens de cellules en appliquant l'action de la cellule située à gauche pour les valeurs de la cellule située à gauche et la cellule de droite. La nouvelle cellule aura la même action que la cellule de droite, comme vous pouvez le voir dans Figure 2.

Figure 2 fusionner les cellules (méthode)

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;
}

Par exemple, fusion de cellules (8, '-') et des cellules (5, « + ») entraînera une nouvelle cellule (8 – 5, « + ») = cellule (3, « + »).

Mais que se passe-t-il si deux cellules ne peuvent pas être fusionnés parce que la priorité de la cellule de gauche est inférieure à la cellule de droite ? Que se passe-t-il, est un objet temporaire déplacer vers la cellule suivante, à droite, afin de fusionner avec la cellule en regard de celle-ci et ainsi de suite, de manière récursive. Dès que la cellule de droite a été fusionnée avec la cellule en regard de celle-ci, je revenir à la cellule d'origine, gauche et essayez il remerge avec la cellule droite nouvellement créée, comme illustré dans Figure 3.

Figure 3 fusionner une liste de cellules

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;
}

Notez que, depuis l'extérieur, cette méthode est appelée avec le paramètre mergeOneOnly la valeur false, donc elle ne renvoie pas avant la fin de la fusion entière. En revanche, lorsque la méthode merge est appelée de manière récursive (lorsqu'il est impossible de fusionner les cellules de droite et de gauche en raison de leurs priorités), mergeOneOnly est fixé à true, car je souhaite revenir là où j'étais aussi terminer une fusion réelle dans la méthode MergeCells.

Notez également que la valeur retournée par la méthode Merge est le résultat réel de l'expression.

Fractionnement d'une Expression dans une liste de cellules

La première partie de l'algorithme fractionne une expression dans une liste de cellules. Priorité des opérateurs mathématiques n'est pas prise en compte dans cette étape. Tout d'abord, l'expression est divisée en une liste de jetons. Tous les jetons sont séparées par un opérateur mathématique ou une parenthèse open ou close. Les parenthèses peuvent, mais n'ont pas à avoir une fonction associée ; par exemple, « 1-sin(1-2) » a une fonction associée, mais « 1 - (1 - 2) « ne.

Tout d'abord, examinons ce qui se passe lorsqu'il n'y a aucune fonction ou les parenthèses, simplement une expression contenant des nombres réels et des opérateurs mathématiques entre eux. Dans ce cas, je crée simplement constitué d'un nombre réel et une action à la suite de cellules. Par exemple, si « 3-2 * 4 « prospects à une liste composée de trois cellules :

Split (“3-2*4”) = { Cell(3, ‘-’), Cell(2, ‘*‘), Cell(3, ‘)’) }

La dernière cellule aura toujours une action de END_ARG spéciale, définir comme :

const char END_ARG = ')';

Il peut être modifié à autre chose, mais dans ce cas la parenthèse ouvrante correspondante START_ARG doivent être prises en compte, ainsi, lequel définir comme :

const char START_ARG = '(';

Si un des jetons est une fonction ou une expression entre parenthèses, l'algorithme de toute division-et-fusion est appliqué à l'aide de la récursivité. Par exemple, si l'expression est "(3-1)-1, « l'algorithme entier entre parenthèses est appliqué en premier à l'expression :

Split(“(3-1)-1”) = Split( “[SplitAndMerge(“3-1”)] - 1”) = { Cell(2, ‘-’), Cell(1, ‘)’) }

La fonction qui exécute le fractionnement est LoadAndCalculate, comme indiqué dans Figure 4.

Figure 4 LoadAndCalculate (méthode)

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);
}

La méthode LoadAndCalculate ajoute toutes les cellules à la liste listToMerge et appelle ensuite la deuxième partie de l'algorithme d'analyse, la fonction de fusion. L'élément StringBuilder contiendra le jeton actuel, ajouter des caractères un par un dès qu'elles sont lues à partir de la chaîne d'expression.

La méthode StillCollecting vérifie si les caractères pour le jeton en cours sont toujours collectés. Ce n'est pas le cas si le caractère actuel est END_ARG ou n'importe quel autre spécial « to » de caractères (par exemple une virgule, si l'analyse des arguments sont séparés par une virgule ; Je vous propose un exemple à l'aide de la fonction power ultérieurement). En outre, le jeton n'est pas collecté plus si le caractère actuel est une action valide ou un 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 == '^';
}

Je sais que j'ai terminé collecte le jeton actuel dès que j'obtiens un opérateur mathématique décrit dans la méthode ValidAction ou parenthèses définissent par les START_ARG ou END_ARG constantes. Il existe également un cas spécial impliquant un «-» du jeton, qui est utilisé pour indiquer un nombre commençant par un signe négatif.

À la fin de cette étape de fractionnement, toutes les sous-expressions entre parenthèses et tous les appels de fonction sont éliminées via les appels récurrents à la version d'évaluation de l'algorithme entière. Mais les actions résultantes de ces appels récurrents toujours aura l'action END_ARG, qui n'est pas correcte dans la portée de l'expression globale si l'expression calculée n'est pas à la fin de l'expression à évaluer. C'est pourquoi l'action doit être mis à jour après chaque appel récurrent, comme suit :

char action = ValidAction(ch) ? ch
                                : UpdateAction(data, ref from, ch);

Le code de la méthode updateAction se trouve dans Figure 5.

Méthode d'Action de mise à jour de la figure 5

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;
}

Le code suivant de l'analyse du jeton extrait sera Figure 4:

ParserFunction func = new ParserFunction(data, ref from, item.ToString(), ch);
double value = func.GetValue(data, ref from);

Si le jeton extrait n'est pas une fonction, ce code essaie de convertir en une valeur double. Sinon, une fonction appropriée, précédemment enregistrée est appelée, qui peut à son tour récursive appeler la méthode LoadAndCalculate.

Fonctions définies par l'utilisateur et Standard

J'ai décidé d'implémenter la fabrique de fonction à l'aide de l'idiome de constructeur virtuel qui a été publié par James Coplien (voir point 4 dans « Références »). En c#, cela est souvent implémenté à l'aide d'une méthode de fabrique (voir point 5 dans « Références ») qui utilise une classe de fabrique supplémentaire pour produire l'objet si nécessaire. Mais, modèle de conception plus ancienne de Coplien n'a pas besoin une classe de fabrique supplémentaire de façade et à la place, simplement construit un nouvel objet à l'aide de le m_impl membre implémentation dérivée de la même classe :

private ParserFunction m_impl;

Le constructeur interne spécial initialise ce membre avec la classe appropriée. La classe réelle de le m_impl objet implémentation créée dépend des paramètres d'entrée, comme dans Figure 6.

Constructeur virtuel figure 6

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;
}

Un dictionnaire est utilisé pour contenir toutes les fonctions de l'analyseur. Ce dictionnaire mappe le nom de chaîne de la fonction (par exemple, « sin ») à l'objet réel, l'implémentation de cette fonction :

private static Dictionary<string, ParserFunction> m_functions =
      new Dictionary<string, ParserFunction>();

Les utilisateurs de l'analyseur peuvent ajouter autant de fonctions qu'ils le souhaitent en appelant la méthode suivante dans la classe de base ParserFunction :

public static void AddFunction(string name, ParserFunction function)
{
  m_functions[name] = function;
}

La méthode GetValue est appelée sur la ParserFunction créée, mais le véritable travail s'effectue dans la fonction de mise en œuvre, qui remplace la méthode evaluate de la classe de 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;
}

Les classes d'implémentation de fonction dérivant de la classe ParserFunction, ne sont pas utiliser le constructeur interne dans Figure 6. Au lieu de cela, ils utiliserez le constructeur de la classe de base suivant :

public ParserFunction()
{
  m_impl = this;
}

Deux fonctions « standard » spéciales sont utilisées dans le constructeur de ParserFunction en Figure 6:

private static IdentityFunction s_idFunction = new IdentityFunction();
private static StrtodFunction s_strtodFunction = new StrtodFunction();

La première est la fonction d'identité ; elle est appelée pour analyser une expression entre parenthèses qui n'a pas une fonction associée :

class IdentityFunction : ParserFunction
{
  protected override double Evaluate(string data, ref int from)
  {
    return Parser.LoadAndCalculate(data, ref from, Parser.END_ARG);
  }
}

La deuxième fonction est un « fourre-tout » qui est appelé lorsque aucune fonction n'est trouvée qui correspond au dernier jeton extrait. Cela se produit lorsque le jeton extrait est un nombre réel, ni une fonction implémentée. Dans ce cas, une exception est levée :

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; }
}

Toutes les autres fonctions peuvent être implémentées par l'utilisateur. la plus simple est une fonction pi :

class PiFunction : ParserFunction
{
  protected override double Evaluate(string data, ref int from)
  {
    return 3.141592653589793;
  }
}

Une implémentation plus classique est une fonction 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);
  }
}

Je l'ai dit précédemment que je fournirait un exemple d'utilisation d'une fonction de puissance, qui requiert deux arguments, séparés par une virgule. Il s'agit de l'écriture d'une fonction nécessitant plusieurs arguments séparés par un séparateur personnalisé :

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);
  }
}

N'importe quel nombre de fonctions qui peut être ajouté à l'algorithme à partir du code utilisateur, comme suit :

ParserFunction.AddFunction("pi",  new PiFunction());
ParserFunction.AddFunction("exp", new ExpFunction());
ParserFunction.AddFunction("pow", new PowFunction());

Synthèse

L'algorithme de fractionnement et fusion présenté ici a la complexité d'o (n) si n est le nombre de caractères dans la chaîne d'expression. Cela est, car chaque jeton est lu qu'une seule fois pendant l'étape de fractionnement et, dans le pire des cas, il y aura à la plupart des 2 (m - 1) – 1 comparaisons à l'étape de fusion, où m est le nombre de cellules créé dans la première étape.

Par conséquent, l'algorithme a la complexité même du temps en tant que l'algorithme de Dijkstra (voir l'article 3 dans « Références »). Elle peut avoir un léger inconvénient par rapport à l'algorithme de Dijkstra, car elle utilise la récursivité. En revanche, je pense que l'algorithme de fractionnement et fusion est plus facile à implémenter, précisément en raison de la récursivité et également d'étendre à l'aide de la syntaxe personnalisée, les fonctions et opérateurs.

Références

  1. V. Kaplan, « Fractionnement et fusion algorithme pour l'analyse des Expressions mathématiques, » CVu, 27-2, mai 2015, bit.ly/1Jb470l
  2. V. Kaplan, « Fractionnement et fusion Revisited, » CVu, 27-3, juillet 2015, bit.ly/1UYHmE9
  3. E. Dijkstra, algorithme Yard se Shunting, bit.ly/1fEvvLI
  4. J. Coplien, « Advanced Styles de programmation C++ et idiomes » (p. 140), Addison-Wesley, 1992
  5. E. Gamma, r STEER, R. Johnson et J. Vlissides, « modèles de conception : Éléments des logiciels réutilisables orientés objet, » Professional Addison-Wesley informatique série, 1995

Vassili Kaplanest un développeur de Microsoft Lync précédent. Il est passionné par programmation en c# et C++. Actuellement, il se trouve à Zürich en Suisse et fonctionne comme un journaliste indépendant pour différentes banques. Vous pouvez le contacter à l'adresse iLanguage.ch.

Merci à l'experte technique Microsoft suivante d'avoir relu cet article : James McCaffrey