Modifier l'algorithme de shunt de triage pour inclure un opérateur de mur |

Question

Comment la norme Shunting Yard Algorithm serait-elle modifiée pour inclure un symbole 'wall', |, représentant la fin des paramètres de la fonction? Autrement dit, pour prendre en charge une modification de la notation postfixe (Reverse Polish Notation) qui permet des fonctions avec un nombre arbitraire de paramètres.

Quelques exemples de la notation postfixe modifié:

f (1,2) 9 ⟶ | 1 2 f 9 +
f (1,2,3) +9 ⟶ | 1 2 3 f 9 +

S'il vous plaît, je cherche les modifications réelles, pas seulement des idées sur la façon de le faire.

algorithme de triage

1. Bien qu'il y ait des jetons à lire:
2. Lire un jeton.
3. Si le jeton est un nombre, poussez-le dans la file d'attente de sortie.
4. Si le jeton est un jeton de fonction, poussez-le sur la pile.
5. Si le jeton est un séparateur d'arguments de fonction (par exemple, une virgule):
   • Jusqu'à ce que le jeton au sommet de la pile est une parenthèse gauche, les opérateurs de bruit de la pile sur la file d'attente de sortie. Si aucune parenthèse gauche n'est rencontrée, soit le séparateur a été égaré, soit les parenthèses ne correspondent pas.

6. Si le jeton est un opérateur, o1, puis:

   • alors qu'il ya un o2 jeton opérateur, au sommet de la pile de l'opérateur et soit

     • o1 est gauche-associative et sa précédence est inférieure ou égale à celle de o2, ou

     • o1 est associative droite, et a préséance inférieure à celle de o2,

       -pop o2 de la pile de l'opérateur, dans la file d'attente de sortie;

     • à la fin de l'itération, appuyez sur o1 sur la pile de l'opérateur.
7. Si le jeton est une parenthèse gauche (ie "("), puis appuyez sur la pile
8. Si le jeton est une parenthèse droite (ie ")".):
   • Jusqu'à ce que le jeton en haut de la pile soit une parenthèse gauche, placez les opérateurs hors de la pile dans la file d'attente de sortie.
   • Insérez la parenthèse gauche de la pile, mais pas dans la file d'attente de sortie.
   • Si le jeton en haut de la pile est un jeton de fonction, placez-le dans la file d'attente de sortie.
   • Si la pile s'épuise sans trouver de parenthèse gauche, il y a des parenthèses incompatibles.
9. Quand il n'y en a plus à lire:
   • Bien qu'il existe encore des jetons opérateur dans la pile:
     • Si le jeton opérateur sur le dessus de la pile est une parenthèse, puis il y a des parenthèses incompatibles.
     • Pop l'opérateur sur la file d'attente de sortie.
10. Exit.

Answer 1

La solution:

A l'étape 4, en plus de la fonction de poussée de la pile, écrire le | symbole à l'expression de postfix de sortie.

Bien sûr, l'algorithme qui évalue cette expression postfixe modifiée doit lui-même être modifié pour prendre en compte le symbole de mur.