Conversion de la notation polonaise inversée

Question

Existe-t-il un moyen d'interpréter la notation polonaise inversée en "normal"? notation mathématique lors de l'utilisation de C ++ ou C #? Je travaille pour une firme d’ingénierie, ils utilisent donc parfois les RPN et nous avons besoin d’un moyen de les convertir. Des suggestions?

Answer 1

Oui. Pensez au fonctionnement d'une calculatrice RPN. Désormais, au lieu de calculer la valeur, vous ajoutez l'opération à l'arborescence. Ainsi, par exemple, 2 3 4 + * , quand vous arrivez au +, alors plutôt que de mettre 7 sur la pile, vous mettez (+ 3 4) sur le empiler. De même, lorsque vous accédez à * (votre pile ressemblera à 2 (+ 3 4) * à ce stade), elle devient (* 2 (+ 3 4)) .

C’est la notation de préfixe, que vous devez ensuite convertir en infixe. Traversez l'arbre de gauche à droite, la profondeur en premier. Pour chaque "niveau interne", si la priorité de l'opérateur est inférieure, vous devez placer l'opération entre parenthèses. Ici, alors, vous direz 2 * (3 + 4) , car le + a une priorité inférieure à *.

J'espère que ça aide!

Éditer: Il y a une subtilité (à part ne pas prendre en compte les opérations unaires dans ce qui précède): j'ai supposé des opérateurs associatifs de gauche. Pour une association de droite (par exemple, ** ), vous obtenez des résultats différents pour 2 3 4 ** ** & # 8658; (** 2 (** 3 4)) versus 2 3 ** 4 ** & # 8658; (** (** 2 3) 4) .

Lors de la reconstruction d'infix à partir de l'arborescence, les deux cas montrent que la précédence ne nécessite pas de bracketing, mais en réalité, ce dernier cas doit être encadré ( (2 ** 3) ** 4 ) . Ainsi, pour les opérateurs associatifs de droite, la branche de gauche doit avoir une priorité supérieure (au lieu d'être supérieure ou égale) pour éviter les parenthèses.

Nous pensons également que vous avez également besoin de crochets pour la branche droite des opérateurs - et / .

Answer 2

L’algorithme Shunting Yard est utilisé pour convertir Infix (c’est-à-dire algébrique) en RPN. C'est l'opposé de ce que vous voulez.

Pouvez-vous me donner un exemple de votre entrée RPN? Je suis un utilisateur / programmeur expérimenté de la calculatrice HP. Je suppose que vous avez une pile contenant toutes les entrées & amp; les opérateurs. Je suppose que vous devez reconstruire l’arbre des expressions, puis parcourir l’arbre pour générer le formulaire infix.

Answer 3

C # n’a pas de prise en charge intégrée pour l’analyse de la notation polonaise inversée (RPN) .Vous devrez écrire votre propre analyseur ou en trouver un en ligne.

Il existe des dizaines de tutoriels pour convertir une forme postfixe (RPN) en infixe (équation algébrique). Jetez un coup d’œil à this , peut-être le trouverez-vous utile et pourrez-vous essayer 'reverse engineering' pour convertir les expressions postfixes en infixes, en gardant à l'esprit qu'il peut y avoir plusieurs notations infixes pour une postfixe donnée. Il existe très peu d'exemples utiles traitant de la conversion de postfix en infix. Voici une entrée en deux parties que j’ai trouvée très utile. Il a aussi un pseudo-code:

• PostFix à Infix: conversion de RPN en expressions algébriques
• Postfix pour infixer, partie 2: ajout des parenthèses

Answer 4

Si vous pouvez lire ruby, vous trouverez de bonnes solutions à ce problème ici

Answer 5

Une approche consiste à prendre l'exemple du deuxième chapitre du livre de dragon qui explique comment écrire un analyseur syntaxique pour convertir et inverser la notation infixe en notation postfixée.

Answer 6

Si vous souhaitez convertir du texte RPN (notation postfixe) en "notation normale", vous souhaitez convertir du texte source (chaîne / s). (infixe), cela est certainement possible (et probablement pas trop difficile).

RPN a été conçu pour les machines empilées, car la manière dont l’opération était représentée ("2 + 3" - - gt; "2 3 +") correspondait à la manière dont elle était réellement exécutée sur le matériel (bouton "Push"). 2 "sur la pile, enfoncez" 3 "dans la pile, supprimez les deux arguments supérieurs de la pile et ajoutez-les, repoussez-les dans la pile).

En gros, vous voulez créer une arborescence de syntaxe à partir de votre RPN en créant les 2 expressions que vous souhaitez utiliser sur les "nœuds terminaux". et l'opération elle-même, qui vient ensuite, le "nœud parent". Cela se fera probablement en regardant de manière récursive votre chaîne d'entrée (vous voudrez probablement vous assurer que les sous-expressions sont correctement mises entre parenthèses pour plus de clarté, si elles ne le sont pas déjà).

Une fois que vous avez cet arbre de syntaxe, vous pouvez générer une notation de préfixe, infixe ou postfixe simplement en effectuant une traversée de précommande, de post-commande ou dans l'ordre de cet arbre (encore une fois, mettez entre parenthèses votre sortie pour plus de clarté). ).

Vous pouvez trouver des informations supplémentaires ici .

Answer 7

Je viens d'écrire une version en Java, il s'agit d'une here et un dans Objective-C, sur ici .

Algorithme possible : si vous avez une pile avec l'entrée dans rpn telle que l'utilisateur la saisirait, par exemple. 8, 9, *. Vous parcourez le tableau du premier au dernier et vous supprimez toujours l'élément actuel. Cet élément que vous évaluez. S'il s'agit d'un opérande, vous l'ajoutez à une pile de résultats. Lorsqu'il s'agit d'un opérateur, vous devez extraire la pile de résultats deux fois (pour les opérations binaires) pour les opérandes et écrire la chaîne de résultats sur la pile de résultats.

Avec l'exemple de saisie de " 8, 9, +, 2, * " vous obtenez ces valeurs sur la pile de résultats (les crochets indiquant les éléments individuels) :

étape 1: [8]

étape 2: [8], [9]

étape 3: [(8 + 9)]

étape 4: [(8 + 9)], [2]

étape 5: [(8 + 9) * 2]

Lorsque la pile d'entrée est vide, vous avez terminé et le seul élément de resultStack est votre résultat. (Notez cependant que l'entrée peut contenir plusieurs entrées ou que cela n'a pas de sens, comme une opération pilote: "+ 2 3 /".)

Les implémentations dans les liens n'utilisent délibérément aucun type fait maison, par exemple. opérateurs ou opérandes et ne s'applique pas par exemple modèle composite. C'est simplement propre et simple afin qu'il puisse être facilement compris et transféré dans une autre langue.

Le portage en C # est simple.