Algoritmo di smistamento

Question

Algoritmo di smistamento

#1 da (1 voti)
#2 da (1 voti)

1

Sono interessato a tutti i casi in cui algoritmo di smistamento può dire se un'espressione non è corretta scritto dal punto di vista della sintassi.

Quindi l'algoritmo Shunting-yard prende un'espressione scritta in notazione infissa e la trasforma in notazione prefisso o postfisso. Come un semplice esempio, quello preso da wikipedia: una notazione infissa di un'equazione sarebbe 3 + 4 × 2 ÷ (1 - 5) ^ 2 ^ 3 e dopo essere stata convertita in postfix con l'algoritmo diventerebbe 3 4 2 × 1 5 - 2 3 ^ ^ ÷ + .

L'algoritmo su Wikipedia verifica la presenza di parentesi non corrispondenti in due casi: Innanzitutto, se trova una parentesi quadra destra apre gli operatori fino a trovare una parentesi sinistra, se non viene trovata, ci sono parentesi non corrispondenti. In secondo luogo, dopo che tutti i token sono stati letti, apre lo stack dell'operatore nella coda di output. Se è rimasta una parentesi, ci sono parentesi non corrispondenti. Queste 2 cose possono essere fatte con l'algoritmo.

Ora per la mia espressione in notazione postfix 3 4 2 × 1 5 - 2 3 ^ ^ ÷ + come posso dire esattamente da questo che la mia notazione infisso è stata scritta correttamente? Ho pensato che dopo questa espressione viene valutato se c'è più di un elemento nello stack, allora c'è un errore. Quali altri casi dovrei prendere in considerazione?

algorithms shunting-yard

posta Shury 30.10.2018 - 10:38

fonte

2 risposte

Leggi altre domande sui tag algorithms shunting-yard

Cercando di capire il diagramma di sequenza Posso usare Entity Framework con un livello API SOAP su un database?

score 1 · Answer 1

La notazione Postfix è facile da controllare staticamente, a condizione che si possa facilmente consultare l'arity degli operatori. È possibile scorrere tutti gli elementi e tenere traccia del numero di elementi nello stack di valutazione. Questa dimensione deve essere sempre almeno una. Alla fine, la dimensione deve essere esattamente uno. Pseudocodice per la verifica:

operations = [...]
size = 0

for operand in operations:
  switch operand type:
    case literal:
      size = size + 1
    case operator:
      assert size >= arity(operand)
      size = size + 1 - arity(operand)

assert size == 1

Tuttavia, per un semplice linguaggio della calcolatrice non c'è alcun vantaggio di eseguire analisi statiche semplicemente eseguendo il codice e vedere se porta a uno stato incoerente.

score 1 · Answer 2

Un problema aggiuntivo quando si analizza infix è quando ci sono 2 numeri o 2 operatori uno accanto all'altro: 2 2 + + 3

Puoi verificarlo solo accettando un numero o parentesi sinistra dopo un operatore o parentesi sinistra e accetta solo un operatore o parentesi destra dopo un numero o parentesi tonde.

if(expectOperator){
    if(token.type == NUMBER || token.type == LEFT_PAREN){
        error("expect operator");
    } 
} else{
    if(token.type == OPERATOR || token.type == RIGHT_PAREN){
        error("expect number");
    } 
}
if(token.type != RIGHT_PAREN && token.type != LEFT_PAREN)
    expectOperator =! expectOperator;