Ottobre 2015
Volume 30 Numero 10
Il presente articolo è stato tradotto automaticamente.
C# - Parser dell'espressione di suddivisione e unione in C#
Dopo la pubblicazione di un nuovo algoritmo per l'analisi di un'espressione matematica in C++ in problemi di maggio e luglio 2015 ufficiale CVu (vedere elementi 1 e 2 in "Riferimenti"). Perché un lettore attenti, Silas S. Brown, trovato un bug nell'implementazione del prima algoritmo, pertanto è necessario apportare alcune modifiche a tale impiegato due articoli. Grazie a tale lettore, l'algoritmo è diventato più "maturo". Da allora, è stata corretta anche alcuni bug più piccoli. Si esamineranno ora fornire un'implementazione dell'algoritmo corretto in c#.
Non è probabilmente troppo sarà mai necessario scrivere codice per analizzare un'espressione matematica, ma le tecniche utilizzate nell'algoritmo possono essere applicate a altri scenari, ad esempio l'analisi delle stringhe non standard. Utilizzo di questo algoritmo è possibile definire facilmente nuove funzioni che ritenuto (ad esempio, effettuare una richiesta Web per ordinare una pizza). Con piccole modifiche, è inoltre possibile creare un proprio compilatore c# per il nuovo linguaggio di script personalizzato. Inoltre, solo interessanti l'algoritmo in sé.
L'algoritmo Edsger Dijkstra, pubblicato da più di 50 anni in 1961, viene spesso utilizzato per l'analisi di espressioni matematiche (vedere "Riferimenti" elemento 3). Ma è buona norma disporre di un'alternativa che, se ha la stessa complessità tempo, è, a mio parere, facile da implementare e da estendere.
Si noti che devo utilizzare il linguaggio "costruttore virtuale" per l'implementazione della funzione factory. Questo linguaggio è stato introdotto in C++ da James Coplien (vedere l'articolo 4 in "Riferimenti"). Mi auguro che sono disponibili interessanti l'utilizzo del linguaggio c# mondo, nonché.
L'algoritmo di suddivisione e unione
Il programma demo in Figura 1 viene illustrato l'algoritmo di suddivisione e unione per l'analisi di un'espressione matematica.
.png "Un'esecuzione Demo dell'algoritmo di suddivisione e unione")
Figura 1 esecuzione Demo dell'algoritmo di suddivisione e unione
L'algoritmo è costituita da due passaggi. Nel primo passaggio la stringa contenente l'espressione è suddivisa in un elenco di oggetti cella, in ogni cella viene definita come segue:
class Cell
{
internal Cell(double value, char action)
{
Value = value;
Action = action;
}
internal double Value { get; set; }
internal char Action { get; set; }
}
L'azione è un singolo carattere che può essere uno degli operatori matematici: ' *' (moltiplicazione), '/' (divisione), '+' (addizione), '-' (sottrazione) o ' ^' (power) o un carattere speciale che indicano la fine di un'espressione, che è hardcoded come '). " L'ultimo elemento nell'elenco di celle da unire avranno sempre l'azione speciale '), ", ovvero nessuna azione, ma è possibile utilizzare qualsiasi altro simbolo o una parentesi invece.
Nel primo passaggio, l'espressione è suddiviso in token che vengono quindi convertiti in celle. Tutti i token sono separati da una delle espressioni matematiche o una parentesi. Un token può essere un numero reale o una stringa con il nome di una funzione. La classe ParserFunction definita in un secondo momento si occupa di tutte le funzioni di stringa da analizzare oppure per analisi di una stringa a un numero. Inoltre può chiamare l'intera stringa, l'analisi di algoritmo, in modo ricorsivo. Se sono presenti non funzioni e non le parentesi nella stringa da analizzare, esisterà ricorsione.
Nel secondo passaggio, tutte le celle vengono unite. Vediamo innanzitutto il secondo passaggio perché è un po' più semplice rispetto alla prima.
Unione di un elenco di celle
L'elenco delle celle viene unito singolarmente in base alle priorità delle azioni; vale a dire gli operatori matematici. Queste priorità vengono calcolate come segue:
static int GetPriority(char action)
{
switch (action) {
case '^': return 4;
case '*':
case '/': return 3;
case '+':
case '-': return 2;
}
return 0;
}
Due celle possono essere unite solo se la priorità dell'azione della cella a sinistra non è minore di priorità dell'azione di cella successiva:
static bool CanMergeCells(Cell leftCell, Cell rightCell)
{
return GetPriority(leftCell.Action) >= GetPriority(rightCell.Action);
}
Unione di applicare l'azione della cella a sinistra per i valori di cella a sinistra e quella destra significa di celle. La nuova cella avrà la stessa azione della cella a destra, come si può vedere nella Figura 2.
Figura 2 Unione celle metodo
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;
}
Ad esempio, l'unione di celle (8, '-') e di cella (5, '+') porterà a una nuova cella (8-5, '+') = cella (3, '+').
Ma cosa succede se non è possibile unire due celle perché la priorità della cella a sinistra è minore di cella destra? Cosa accade, è una variabile temporanea passa alla cella successiva, a destra per tentare di unire la cella successiva e così via, in modo ricorsivo. Non appena la cella a destra è stata unita con la cella successiva, tornare alla cella originale a sinistra e tenta di unire di nuovo, con la cella destra appena creata, come illustrato nella Figura 3.
Figura 3 unire un elenco di celle
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;
}
Si noti che, dall'esterno, questo metodo viene chiamato con il parametro mergeOneOnly impostato su false, in modo che non verrà restituito prima del completamento dell'unione intero. Al contrario, quando il metodo merge viene chiamato in modo ricorsivo (quando non è possibile unire celle destra e sinistro per le priorità), mergeOneOnly verrà impostato su true poiché si desidera tornare a cui sono stato appena è possibile completare un'unione effettiva nel metodo MergeCells.
Si noti inoltre che il valore restituito dal metodo di tipo Merge è il risultato effettivo dell'espressione.
Suddivisione di un'espressione in un elenco di celle
La prima parte dell'algoritmo suddivide un'espressione in un elenco di celle. Precedenza tra gli operatori matematici non viene preso in considerazione in questo passaggio. In primo luogo, l'espressione è suddiviso in un elenco di token. Tutti i token sono separati dagli operatori matematici o da una parentesi di apertura o chiusura. Le parentesi possono, ma non sono necessario disporre di una funzione associata. ad esempio, "sin(1-2) 1" ha una funzione associata, ma "1 - (1 - 2)" non.
In primo luogo, vediamo cosa succede quando non sono presenti funzioni o le parentesi, semplicemente un'espressione che contiene i numeri reali e operatori matematici tra di essi. In questo caso, sufficiente creare celle costituito da un numero reale e un'azione conseguente. La divisione, ad esempio, "3-2 * 4" lead a un elenco costituito da tre celle:
Split (“3-2*4”) = { Cell(3, ‘-’), Cell(2, ‘*‘), Cell(3, ‘)’) }
L'ultima cella disporrà sempre un'azione END_ARG speciale, che è possibile definire come:
const char END_ARG = ')';
Può essere modificata in modo diverso, ma in tal caso la corrispondente parentesi START_ARG devono essere presi in considerazione, anche, che è possibile definire come:
const char START_ARG = '(';
Se uno dei token è una funzione o un'espressione tra parentesi, l'algoritmo intera divisione-e-merge viene applicato mediante la ricorsione. Ad esempio, se l'espressione è "(3-1)-1," l'algoritmo intero tra parentesi viene applicato per primo all'espressione:
Split(“(3-1)-1”) = Split( “[SplitAndMerge(“3-1”)] - 1”) = { Cell(2, ‘-’), Cell(1, ‘)’) }
La funzione che esegue la divisione è LoadAndCalculate, come illustrato nella Figura 4.
Figura 4 LoadAndCalculate metodo
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);
}
Il metodo LoadAndCalculate aggiunge tutte le celle all'elenco listToMerge e quindi chiama la seconda parte dell'algoritmo di analisi, la funzione di tipo merge. L'elemento StringBuilder conterrà il token corrente, aggiungendovi caratteri uno alla volta non appena vengono letti dalla stringa di espressione.
Il metodo StillCollecting controlla se i caratteri per il token corrente vengono sempre raccolti. Non è il caso se il carattere corrente è END_ARG o qualsiasi altra speciale "a" di caratteri (ad esempio una virgola, se gli argomenti di analisi sono separati da una virgola; Verrà analizzata un esempio di utilizzo della funzione di risparmio energia in un secondo momento). Inoltre, il token non vengono raccolti più se il carattere corrente è valida o 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 == '^';
}
So che ho terminato la raccolta di token corrente non appena viene visualizzato un operatore matematico descritto nel metodo ValidAction o tra parentesi è definito dalla START_ARG o END_ARG costanti. È inoltre disponibile un caso speciale che coinvolgono un "-" token, che viene utilizzato per indicare un numero a partire da un segno negativo.
Alla fine di questo passaggio suddivisione, tramite le chiamate ricorsive per la valutazione dell'intera algoritmo vengono eliminate tutte le sottoespressioni tra parentesi e tutte le chiamate di funzione. Ma le azioni di queste chiamate ricorsive risultante saranno sempre l'azione END_ARG, che non sarà corretto nell'ambito globale espressione se non è alla fine dell'espressione da valutare l'espressione calcolata. Ecco perché l'azione deve essere aggiornato dopo ogni chiamata ricorsiva, come illustrato di seguito:
char action = ValidAction(ch) ? ch
: UpdateAction(data, ref from, ch);
Il codice per il metodo updateAction è in Figura 5.
Metodo di azione di aggiornamento nella figura 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;
}
L'analisi effettiva del token estratti sarà il seguente codice di Figura 4:
ParserFunction func = new ParserFunction(data, ref from, item.ToString(), ch);
double value = func.GetValue(data, ref from);
Se il token estratto non è una funzione, il codice tenta di convertirlo in un valore double. In caso contrario, una funzione appropriata, registrata in precedenza verrà chiamato, che può a sua volta in modo ricorsivo il metodo LoadAndCalculate.
Funzioni definite dall'utente e Standard
Ho deciso di implementare la factory di funzione utilizzando il linguaggio costruttore virtuale innanzitutto pubblicato da James Coplien (vedere l'articolo 4 in "Riferimenti"). In c#, questo viene spesso implementato utilizzando un metodo factory (vedere l'articolo 5 in "Riferimenti") che utilizza una classe factory aggiuntive per produrre l'oggetto richiesto. Ma precedente modello di progettazione del Coplien non è necessaria una classe factory aggiuntive dell'aspetto e invece costruisce un nuovo oggetto in tempo reale utilizzando il m_impl membro di implementazione che deriva dalla stessa classe:
private ParserFunction m_impl;
Il costruttore speciale interno Inizializza questo membro con la classe appropriata. L'effettiva classe m_impl l'oggetto implementazione creato dipende da parametri di input, come illustrato nella Figura 6.
Figura 6 costruttore virtuale
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 dizionario utilizzato per contenere tutte le funzioni del parser. Questo dizionario associa il nome della stringa della funzione (ad esempio "sin") per l'oggetto effettivo che implementa questa funzione:
private static Dictionary<string, ParserFunction> m_functions =
new Dictionary<string, ParserFunction>();
Gli utenti del parser possono aggiungere tanti funzioni come desiderano chiamando il metodo seguente nella classe base ParserFunction:
public static void AddFunction(string name, ParserFunction function)
{
m_functions[name] = function;
}
Viene chiamato il metodo GetValue su ParserFunction creato, ma il lavoro effettivo viene eseguito nella funzione di implementazione, che eseguirà l'override di metodo evaluate della classe di 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;
}
Le classi di implementazione (funzione), la derivazione dalla classe ParserFunction, non è possibile utilizzare il costruttore interno in Figura 6. Al contrario, utilizzano il costruttore della classe di base seguente:
public ParserFunction()
{
m_impl = this;
}
Vengono utilizzate due funzioni di "standard" speciale nel costruttore ParserFunction di Figura 6:
private static IdentityFunction s_idFunction = new IdentityFunction();
private static StrtodFunction s_strtodFunction = new StrtodFunction();
Il primo è la funzione di identità. verrà chiamato per l'analisi di qualsiasi espressione tra parentesi che non dispone di una funzione associata:
class IdentityFunction : ParserFunction
{
protected override double Evaluate(string data, ref int from)
{
return Parser.LoadAndCalculate(data, ref from, Parser.END_ARG);
}
}
La seconda funzione è "generico" che viene chiamato quando non viene trovata alcuna funzione corrispondente per l'ultimo token estratto. Ciò si verifica quando il token estratto è un numero reale né una funzione implementata. Nel secondo caso, verrà generata un'eccezione:
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; }
}
Tutte le altre funzioni possono essere implementate dall'utente. la più semplice è una funzione pi:
class PiFunction : ParserFunction
{
protected override double Evaluate(string data, ref int from)
{
return 3.141592653589793;
}
}
Un'implementazione più comune è una funzione 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);
}
}
Ho detto in precedenza che fornire un esempio di utilizzo di una funzione di risparmio energia, che richiede due argomenti separati da una virgola. Ciò viene illustrato come scrivere una funzione che richiede più argomenti separati da un separatore personalizzato:
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);
}
}
Qualsiasi numero di funzioni può aggiunto all'algoritmo dal codice utente, come illustrato di seguito:
ParserFunction.AddFunction("pi", new PiFunction());
ParserFunction.AddFunction("exp", new ExpFunction());
ParserFunction.AddFunction("pow", new PowFunction());
Avvolgendo
L'algoritmo di suddivisione e unione presentato in questo articolo sono complessità o (n) se n è il numero di caratteri nella stringa di espressione. Ciò accade in quanto ogni token verrà letto una sola volta durante il passaggio di suddivisione e, nel peggiore dei casi, verranno comunque la maggior parte dei 2 (m - 1) – 1 confronti nel passaggio di unione, dove m è il numero di celle creato nel primo passaggio.
Pertanto l'algoritmo ha la stessa complessità ora come algoritmo di Dijkstra (vedere "Riferimenti" elemento 3). Potrebbe includere un lieve svantaggio rispetto all'algoritmo di Dijkstra poiché viene utilizzata la ricorsione. D'altra parte, ritengo che l'algoritmo di suddivisione e unione è più facile da implementare, proprio perché la ricorsione e anche di estendere con la sintassi personalizzata, funzioni e operatori.
Riferimenti
- V. Kaplan, "Suddivisione e unione algoritmo per l'analisi di espressioni matematiche," CVu, 2, 27 maggio 2015, bit.ly/1Jb470l
- V. Kaplan, "Suddivisione e unione Revisited," CVu, 27-3, luglio 2015, bit.ly/1UYHmE9
- E. Dijkstra, algoritmo Shunting giardino, bit.ly/1fEvvLI
- J. Coplien, "avanzate gli stili di programmazione C++ e idiomi" (p. 140), Addison-Wesley, 1992
- E. Gamma, Helm r, R. Johnson e J. Vlissides, "modelli di progettazione: Elementi di Software riutilizzabile orientata agli oggetti"Addison-Wesley Professional Computing 1995 serie,
Vassili Kaplanè uno sviluppatore di Microsoft Lync precedente. È passione per la programmazione in c# e C++. Attualmente vive in Zurigo, Svizzera e lavora come freelance per diversi gruppi. È possibile contattarlo all'indirizzo iLanguage.ch.
Grazie all'esperto tecnico Microsoft seguente per la revisione di questo articolo: James McCaffrey