Oktober 2015

Band 30, Nummer 10

C# – Ausdrucksparser vom Typ "Split and Merge" in C#

Von Vassili Kaplan | Oktober 2015 | Code abrufen: C#VB

In den Ausgaben vom Mai und Juli 2015 des CVu-Journals (siehe die Punkte 1 und 2 unter "Referenzen") habe ich einen neuen Algorithmus für die Analyse eines mathematischen Ausdrucks in C++ veröffentlicht. Es waren zwei Artikel erforderlich, da ein aufmerksamer Leser, Silas S. Brown, einen Fehler im ersten Algorithmus gefunden hatte, den ich deshalb überarbeiten musste. Dank dieses Lesers ist der Algorithmus nun ausgereifter. Außerdem habe ich seitdem einige kleinere Fehler korrigiert. Nun stelle ich eine Implementierung des korrigierten Algorithmus in C# bereit.

Es ist nicht sehr wahrscheinlich, dass Sie jemals Code zum Analysieren eines mathematischen Ausdrucks schreiben müssen. Doch die in diesem Algorithmus verwendeten Techniken können auch auf andere Szenarien angewendet werden, z. B. auf die Analyse nicht standardmäßiger Zeichenfolgen. Mithilfe dieses Algorithmus können Sie mühelos neue Funktionen definieren, die gewünschte Aufgaben ausführen (beispielsweise eine Webanforderung zum Bestellen einer Pizza stellen). Mittels kleinerer Anpassungen können Sie auch Ihren eigenen C#-Compiler für Ihre neue benutzerdefinierte Skriptsprache erstellen. Aber vielleicht finden Sie auch nur den Algorithmus selbst interessant.

Der Edsger Dijkstra-Algorithm, der 1961, also vor 54 Jahren veröffentlicht wurde, dient häufig zum Analysieren mathematischer Ausdrücke (siehe Punkt 3 unter "Referenzen"). Doch es gut, über eine Alternative zu verfügen, die, obwohl sie dieselbe Zeitkomplexität aufweist, meiner Meinung nach einfacher zu implementieren und zu erweitern ist.

Beachten Sie, dass ich das Idiom "virtueller Konstruktor" für die Factory-Implementierung der Funktion verwende. Dieses Idiom wurde von James Coplien (siehe Punkt 4 unter "Referenzen") in C++ eingeführt. Ich hoffe, Sie finden seine Nutzung auch in der C#-Welt sinnvoll.

Der Split-and-Merge-Algorithmus

Das Demoprogramm in Abbildung 1 veranschaulicht den Split-and-Merge-Algorithmus zum Analysieren eines mathematischen Ausdrucks.

Abbildung 1: Eine Demoausführung des Split-and-Merge-Algorithmus

Der Algorithmus besteht aus zwei Schritten. Im ersten Schritt wird die Zeichenfolge mit dem Ausdruck in eine Liste von "Cell"-Objekten aufgeteilt, wobei jedes "Cell"-Objekt wie folgt definiert ist:

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

Die Aktion ist ein einzelnes Zeichen, bei dem es sich um einen der mathematischen Operatoren handeln kann: '*' (Multiplikation), '/' (Division), '+' (Addition), '-' (Subtraktion) oder '^' (Potenz) oder ein Sonderzeichen, das das Ende eines Ausdrucks angibt, das ich als ')' hart codiert habe. Das letzte Element in der Liste der zusammenzuführenden Zellen enthält stets die besondere Aktion ')', d. h. keine Aktion, doch Sie können stattdessen ein beliebiges anderes Symbol oder eine Klammer verwenden.

Im ersten Schritt wird der Ausdruck in Token aufgeteilt, die anschließend in Zellen umgewandelt werden. Alle Token sind durch einen der mathematischen Ausdrücke oder eine Klammer getrennt. Ein Token kann entweder eine reelle Zahl oder eine Zeichenfolge mit dem Namen einer Funktion sein. Die später definierte "ParserFunction"-Klasse verarbeitet alle in der Zeichenfolge zu analysierenden Funktionen oder übernimmt das Analysieren einer Zeichenfolge in eine Zahl. Sie kann auch den gesamten Analysealgorithmus für Zeichenfolgen rekursiv aufrufen. Wenn die Zeichenfolge keine zu analysierenden Funktionen oder Klammern enthält, erfolgt keine Rekursion.

Im zweiten Schritt werden alle Zellen zusammengeführt. Lassen Sie uns zunächst auf den zweiten Schritt eingehen, da er ein weniger einfacher als der erste ist.

Zusammenführen einer Liste von Zellen

Die Zellen in der Liste werden nacheinander gemäß den Prioritäten der Aktionen, also den mathematischen Operatoren zusammengeführt. Diese Prioritäten werden wie folgt berechnet:

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

Zwei Zellen können nur zusammengeführt werden, wenn die Priorität der Aktion der Zelle links nicht niedriger als die Priorität der Zelle daneben ist:

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

Zusammenführen von Zellen bedeutet, dass die Aktion in der linken Zelle auf die Werte der linken und rechten Zelle angewendet wird. Die neue Zelle enthält dieselbe Aktion wie die rechte Zelle (siehe Abbildung 2).

Abbildung 2: Methode zum Zusammenführen von Zellen

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

Das Zusammenführen von Cell(8, '-#) und Cell(5, '+') führt zur neuen Cell(8 – 5, '+') = Cell(3, '+').

Doch was passiert, wenn zwei Zellen nicht zusammengeführt werden können, weil die Priorität der linken niedriger als die der rechten Zelle ist? Dann erfolgt ein temporäres Verschieben in die nächste, rechte Zelle, um zu versuchen, sie rekursiv mit der Zelle daneben usw. zusammenzuführen. Sobald die rechte Zelle mit der Zelle daneben zusammengeführt wurde, kehre ich zur ursprünglichen, linken Zelle zurück und versuche, sie erneut mit der neu erstellten rechten Zelle zusammenzuführen (siehe Abbildung 3).

Abbildung 3: Zusammenführen einer Liste von Zellen

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

Beachten Sie, dass diese Methode von außen mit auf "false" festgelegtem "mergeOneOnly"-Parameter aufgerufen wird, sodass die Rückgabe erst nach Vervollständigung des gesamten Zusammenführungsvorgangs erfolgt. Wenn die "merge"-Methode hingegen rekursiv aufgerufen wird (sobald die linke und die rechte Zelle aufgrund ihrer Prioritäten nicht zusammengeführt werden können), wird "mergeOneOnly" auf "true" festgelegt, da ich dahin zurückkehren möchte, wo ich war, sobald ich einen tatsächlichen Zusammenführungsvorgang in der "MergeCells"-Methode abschließen kann.

Beachten Sie auch, dass der von der "Merge"-Methode zurückgegebene Wert das tatsächliche Ergebnis des Ausdrucks ist.

Aufteilen eines Ausdrucks in eine Liste mit Zellen

Im ersten Teil des Algorithmus wird ein Ausdruck in eine Liste mit Zellen aufgeteilt. Bei diesem Schritt wird der Vorrang mathematischer Operatoren nicht berücksichtigt. Als Erstes wird der Ausdruck in eine Liste mit Token aufgeteilt. Alle Token werden durch einen beliebigen mathematischen Operator oder eine offene oder geschlossene Klammer getrennt. Die Klammern können, müssen aber nicht, eine dazugehörige Funktion aufweisen. Beispielsweise hat "1- sin(1-2)" eine dazugehörige Funktion, "1- (1-2)" hingegen nicht.

Lassen Sie uns zunächst untersuchen, was passiert, wenn es keine Funktionen oder Klammern gibt, sondern nur einen Ausdruck mit reellen Zahlen und mathematischen Operatoren dazwischen. In diesem Fall erstelle ich bloß Zellen mit einer reellen Zahl und einer nachfolgenden Aktion. Das Aufteilen von "3-2*4" führt beispielsweise zu einer Liste mit drei Zellen:

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

Die letzte Zelle weist stets eine spezielle "END_ARG"-Aktion auf, was ich so definiere:

const char END_ARG = ')';

Sie kann in etwas anderes geändert werden, doch in diesem Fall muss die entsprechende öffnende Klammer mit der START_ARG-Aktion ebenfalls berücksichtigt werden, was ich wie folgt definiere:

const char START_ARG = '(';

Wenn eines der Token eine Funktion oder ein Ausdruck in Klammern ist, wird der gesamte Split-and-Merge-Algorithmus unter Verwendung der Rekursion darauf angewendet. Beispiel: Wenn der Ausdruck "(3-1)-1" lautet, wird der gesamte Algorithmus in der Klammer zuerst auf den Ausdruck angewendet:

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

Die Funktion, die die Aufteilung durchführt, heißt "LoadAndCalculate", wie in Abbildung 4 gezeigt.

Abbildung 4: "LoadAndCalculate"-Methode

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

Die "LoadAndCalculate"-Methode fügt alle Zellen der Liste "listToMerge" hinzu und ruft dann den zweiten Teil des Analysealgorithmus auf, die "merge"-Funktion. Das "StringBuilder"-Element enthält das aktuelle Token und fügt diesem Zeichen nacheinander hinzu, sobald diese aus der Ausdruckszeichenfolge gelesen wurden.

Die "StillCollecting-"Methode prüft, ob die Zeichen für das aktuelle Token weiter erfasst werden. Dies ist nicht der Fall, wenn das aktuelle Zeichen "END_ARG" oder ein anderes Sonderzeichen von Typ "bis" ist (z. B. ein Komma, wenn die zu analysierenden Argumente durch ein Komma getrennt werden. Dazu stelle ich später ein Beispiel unter Verwendung der "power"-Funktion bereit). Außerdem wird das Token nicht länger erfasst, wenn das aktuelle Zeichen eine gültige Aktion oder ein START_ARG ist:

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 == '^';
}

Ich weiß, dass das Erfassen des aktuellen Tokens abgeschlossen ist, sobald ich einen in der "ValidAction"-Methode beschriebenen mathematischen Operator oder Klammern erhalte, die von den Konstanten START_ARG oder END_ARG definiert werden. Es gibt auch einen Sonderfall mit dem Token "-", das verwendet wird, um eine mit einem negativen Vorzeichen beginnende Zahl zu kennzeichnen.

Am Ende dieses Aufteilungsschritts werden alle Teilausdrücke in Klammern und alle Funktionsaufrufe mithilfe der rekursiven Aufrufe der gesamten Algorithmusauswertung beseitigt. Doch die resultierenden Aktionen dieser rekursiven Aufrufe weisen stets die END_ARG-Aktion auf, was im Gültigkeitsbereich des globalen Ausdrucks nicht ordnungsgemäß ist, wenn sich der berechnete Ausdruck nicht am Ende des auszuwertenden Ausdrucks befindet. Deshalb muss die Aktion nach jedem rekursiven Aufruf wie folgt aktualisiert werden:

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

Den Code für die "updateAction"-Methode sehen Sie in Abbildung 5.

Abbildung 5: "updateAction"-Methode

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

Die tatsächliche Analyse des extrahierten Tokens erfolgt im folgenden Code von Abbildung 4:

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

Wenn das extrahierte Token keine Funktion ist, versucht dieser Code, es in einen "Double"-Wert umzuwandeln. Andernfalls wird eine geeignete, zuvor registrierte Funktion aufgerufen, die wiederum die "LoadAndCalculate"-Methode aufrufen kann.

Benutzerdefinierte und Standardfunktionen

Ich habe mit entschlossen, die Funktionsfactory mithilfe des Idioms "Virtueller Konstruktor" zu implementieren, das zuerst von James Coplien veröffentlicht wurde (siehe Punkt 4 unter "Referenzen"). In C# wird es häufig mithilfe einer "factory"-Methode (siehe Punkt 5 unter "Referenzen") implementiert, die eine zusätzliche "factory"-Klasse zum Generieren des benötigten Objekts verwendet. Doch Copliens älteres Entwurfsmuster benötigt keine zusätzliche "factory"-Fassadenklasse, sondern konstruiert stattdessen direkt ein neues Objekt mithilfe des Implementierungsmembers "m_impl", das von derselben Klasse abgeleitet ist:

private ParserFunction m_impl;

Der spezielle interne Konstruktor initialisiert dieses Member mit der entsprechenden Klasse. Die tatsächliche Klasse des erstellten Implementierungsobjekts "m_impl" hängt von den Eingabeparametern ab (siehe Abbildung 6).

Abbildung 6: Virtueller Konstruktor

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

Ein Wörterbuch dient zum Aufnehmen aller Parserfunktionen. Dieses Wörterbuch ordnet den Zeichenfolgennamen der Funktion (z. B. "sin") der tatsächlichen Objektimplementierung dieser Funktion zu:

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

Benutzer des Parsers können so viele Funktionen wie gewünscht hinzufügen, indem die folgende Methode der grundlegenden "ParserFunction"-Klasse aufgerufen wird:

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

Die "GetValue"-Methode wird für die erstellte "ParserFunction" aufgerufen, doch die eigentliche Arbeit erfolgt in der Implementierungsfunktion, die die Auswertungsmethode der Basisklasse überschreibt:

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

Die Funktionsimplementierungsklassen, die von der "ParserFunction"-Klasse abgeleitet sind, verwenden nicht den internen Konstruktor in Abbildung 6. Stattdessen verwenden sie den folgenden Konstruktor der Basisklasse:

public ParserFunction()
{
  m_impl = this;
}

Im "ParserFunction"-Konstruktor in Abbildung 6 werden zwei spezielle "Standardfunktionen" verwendet:

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

Die erste ist die "identity"-Funktion, die zum Analysieren von Ausdrücken in Klammern aufgerufen wird, denen keine Funktion zugeordnet ist:

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

Die zweite Funktion ist vom Typ "AlleAbfangen", die aufgerufen wird, wenn keine Funktion gefunden wird, die dem letzten extrahierten Token entspricht. Dies geschieht, wenn das extrahierte Token weder eine reelle Zahl noch eine implementierte Funktion ist. Im zweiten Fall wird eine Ausnahme ausgelöst:

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

Alle anderen Funktionen können vom Benutzer implementiert werden. Die einfachste ist eine "pi"-Funktion.

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

Eine typischere Implementierung ist eine "exp"-Funktion:

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

Zuvor habe ich erwähnt, dass ich ein Beispiel unter Verwendung einer "power"-Funktion bereitstelle, die zwei durch ein Komma getrennte Argumente erfordert. So wird eine Funktion geschrieben, die mehrere durch ein benutzerdefiniertes Trennzeichen getrennte Argument benötigt:

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

Dem Algorithmus können aus dem Benutzercode beliebig viele Funktionen wie folgt hinzugefügt werden:

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

Zusammenfassung

Der hier gezeigte Split-and-Merge-Algorithmus hat eine "O(n)"-Komplexität, wenn "n" die Anzahl der Zeichen in der Ausdruckszeichenfolge ist. Dies ist deshalb so, weil jedes Token während des Aufteilungsschritts nur einmal gelesen wird. Anschließend gibt es im schlechtesten Fall höchstens 2 Vergleiche des Typs "(m - 1) – 1" im Zusammenführungsschritt, wobei "m" die Anzahl der im ersten Schritt erstellten Zellen ist.

Deswegen hat der Algorithmus dieselbe Zeitkomplexität wie der Dijkstra-Algorithmus (siehe Punkt 3 unter "Referenzen"). Er hat im Vergleich zum Dijkstra-Algorithmus ggf. einen kleinen Nachteil, da Rekursion verwendet wird. Andererseits finde ich, dass der Split-and-Merge-Algorithmus gerade wegen der Rekursion einfacher zu implementieren und mit benutzerdefinierter Syntax sowie benutzerdefinierten Funktionen und Operatoren einfacher zu erweitern ist.

Referenzen

1. V. Kaplan, "Split and Merge Algorithm for Parsing Mathematical Expressions," CVu, 27-2, Mai 2015, bit.ly/1Jb470l
2. V. Kaplan, "Split and Merge Revisited," CVu, 27-3, Juli 2015, bit.ly/1UYHmE9
3. E. Dijkstra, Shunting-yard algorithm, bit.ly/1fEvvLI
4. J. Coplien, "Advanced C++ Programming Styles and Idioms" (p. 140), Addison-Wesley, 1992
5. E. Gamma, R. Helm, R. Johnson und J. Vlissides, "Design Patterns: Elements of Reusable Object-Oriented Software", Addison-Wesley Professional Computing Series, 1995

Vassili Kaplan ist ein ehemaliger Microsoft Lync-Entwickler. Seine Leidenschaft ist die Programmierung in C# und C++. Er lebt derzeit in Zürich in der Schweiz und arbeitet freiberuflich für verschiedene Banken. Sie erreichen ihn unter iLanguage.ch.

Unser Dank gilt dem folgenden technischen Experten bei Microsoft für die Durchsicht dieses Artikels: James McCaffrey