Modellazione lo smistamento-iarda Algoritmo

Question

Priorità:

Sto cercando di realizzare una variante del Shunting-Yard Algorithm, ma invece di emettere l'espressione in notazione RPN, vorrei per aggiornare stessa come token vengono spinti in modo i risultati possono essere visualizzati in tempo reale (come se si stessero premendo i pulsanti su una calcolatrice e fosse necessario aggiornare il display dopo ogni pulsante).

Ecco la classe Manovra-Yard ...

public class ShuntingYard 
{ 
    private Stack<double> _operands; 
    private Stack<Operation> _operations; 

    public ShuntingYard() 
    { 
     this._operands = new Stack<double>(); 
     this._operations = new Stack<double>(); 
    } 
} 

E la classe Operation sarebbe qualcosa di simile ...

public abstract class Operation 
{ 
    public abstract void Evaluate(Stack<double> operands, Stack<Operation> operations); 
} 

La funzione Evaluate() aggiorna i faraglioni di conseguenza, e il " valore attuale "sarebbe _operands.Peek()

Ecco alcune delle" Operazioni "che ho finora:

public class NullaryOperation : Operation { }
E.g. Pi, e, ecc
Appena spinge costante sul _operands

public class UnaryOperation : Operation { }
Ad es SquareRoot, seno, coseno, ecc
Pops un numero largo di _operands, valuta, e spinge risulta _operands

public class BinaryOperation : Operation { }
Ad es +, -, *, /, ecc
Controlli la precedenza, valuta se necessario, spinge portare a _operands

---

Qui è il problema:
Ho bisogno la capacità di spingere aperti parentesi ( e tipo chiuso parentesi ) nello stack _operations come parte dell'algoritmo. Inoltre, quando aggiungo una parentesi chiusa, devo continuare a scoccare gli operandi/operazioni fino a quando non incontro una parentesi aperta.

voglio evitare i controlli di questo tipo (tipi di oggetto controllo):

while (operations.Peek().GetType() != typeof(OpenParen)) { ... }

voglio evitare l'aggiunta di un metodo come questo in Operation:

public abstract bool IsOpenParen();

potevo fare qualcosa di simile ...

public abstract class Operation 
{ 
    public enum OperationType { Nullary, Unary, Binary, OpenParen, CloseParen }; 
    public abstract OperationType GetOperationType() { }; 

    public abstract void Evaluate(Stack<double> operands, Stack<Operation> operations); 
} 

Ma richiedere a tutti i sottotipi di specificare il loro tipo come enumerazione sembra un cattivo progetto.

---

Come devo modellare questo in modo tale che io possa tenere traccia e gestire parentesi come sono spinti a?

Nota a margine: pensare a parentesi come "Operazioni" non sembra avere molto senso per me. Tuttavia, l'algoritmo su Wikipedia li tratta in questo modo, e non riesco a pensare a nessun altro modo per tenere traccia della loro posizione rispetto ad altre operazioni "reali".

Grazie.

Answer 1

public class Operand { 
    private ShuntingYard sy; 
    private double d; 
    public Operand(double v) { 
     d=v; 
     sy=null; 
    } 
    public Operand() { 
     d=NaN(); // I'm inept at C#, this should mean "d" is unused 
     sy=new ShuntingYard(); 
    } 
} 
public class ShuntingYard { 
    private Stack<Operand> _operands; 
    private Stack<Operation> _operations; 

    public ShuntingYard() 
    { 
     this._operands = new Stack<Operand>(); 
     this._operations = new Stack<Operation>(); 
    } 
} 

Starpilot dà una corretta consulenza, mettendo un'altra ShuntingYard nella pila, ma il modo corretto è quello di mettere un ShuntingYard come operando, non come un'operazione. Ora, una volta che appare nidificato ShuntingYard, gli vengono passati tutti gli operandi e le operazioni successive. Dovrebbe essere preparata una preparazione affinché un ShuntingYard riceva un'operazione di parentesi di chiusura, uno di primo livello dovrebbe generare un errore e gli interni dovrebbero valutare se stessi e sostituire contenente Operand con il risultato della sua valutazione.