Est-ce que toutes les expressions RPN peuvent être représentées de sorte que tous les opérateurs apparaissent sur la gauche et tous les opérandes apparaissent sur la droite?

Question

Je me suis convaincu qu'ils ne peuvent pas.

Prenons par exemple:

4 4 + 4/

pile: 4 pile: 4 4 4 + 4 = 8 pile: 8 pile: 8 4 8/4 = 2 pile: 2

Il y a deux façons que vous pouvez écrire l'expression ci-dessus avec les mêmes opérateurs et opérandes tels que les opérandes tous viennent d'abord: « 4 4 4 +/» et « 4 4 4/+ », Dont aucune évaluation à 2.

"4 4 4 + /" pile: 4 pile: 4 4 pile: 4 4 4 4 + 4 = 8 pile: 4 8 4 /8 = 0,5 pile: 0,5

"4 4 4/+" pile: 4 pile: 4 4 pile: 4 4 4 4/4 = 1 pile: 4 1 4 + 1 = 5 pile: 5

Si vous avez la possibilité d'échanger des éléments sur la pile alors oui, c'est possible, sinon, non.

Pensées?

Answer 1

Tenir compte de l'expression algébrique:

(a + b) * (c + d) 

La traduction évidente RPN serait:

a b + c d + * 

Même avec une opération de swap disponible, je ne pense pas qu'il y ait un moyen de recueillir tous les opérateurs sur la droite:

a b c d + 
a b S 

où S est la somme de c et d. À ce stade, vous ne pouvez pas utiliser une seule opération d'échange pour obtenir à la fois a et b en place pour une opération +. Au lieu de cela, vous auriez besoin d'une opération de pile plus sophistiquée (comme roll) pour obtenir a et b au bon endroit. Je ne sais pas si une opération de roulis serait suffisante pour tous les cas, soit.

Answer 2

Il suffit de montrer celui qui ne peut pas afin de vous dire la réponse à cela.

Si vous ne pouvez pas réorganiser le contenu de la pile, l'expression (2 + 4) * (7 + 8) ne peut pas être réorganisée.

2 4 + 7 8 + *

Peu importe la façon dont vous réorganisez cela, vous vous retrouverez avec quelque chose qui doit être résumé avant de continuer.

Au moins, je le crois.

Answer 3

En fait, vous avez non seulement donné la réponse mais aussi une preuve concluante, en examinant un contre-exemple qui suffit à réfuter l'hypothèse implicite dans le titre.

Answer 4

Je sais que c'est un très vieux fil, mais je viens de le trouver aujourd'hui et je voulais dire que je crois que la réponse à la question initiale est OUI. Je suis confiant que toutes les expressions RPN peuvent être représentées de telle sorte que tous les opérateurs apparaissent sur la gauche et tous les opérandes apparaissent sur la droite, si en plus des opérations arithmétiques normales, nous sommes autorisés à inclure trois opérateurs 'navigationnels' supplémentaires dans la représentation. Toute expression arithmétique peut être représentée comme un arbre binaire, avec des variables et des constantes aux nœuds feuilles, des opérations arithmétiques binaires aux fourches dans l'arbre et des opérations unaires telles que négation, réciproque ou racine carrée le long des branches. Les trois opérations supplémentaires que je suggère représentent la construction d'une branche gauche, la construction d'une branche droite, ou l'atteinte d'un nœud feuille dans un arbre binaire. Maintenant, si nous plaçons tous les opérandes à gauche de la chaîne d'entrée selon la position de leurs feuilles respectives dans l'arbre, nous pouvons fournir au reste de la chaîne d'entrée des opérations indiquant comment reconstruire l'arbre binaire approprié en mémoire et insérer le opérandes et des opérations mathématiques en elle aux bons points. Enfin, un algorithme de traversée d'arbre en profondeur est appliqué pour calculer le résultat.

Je ne sais pas si cela a une application pratique. C'est probablement trop inefficace pour encoder et décoder des expressions. Mais en tant qu'exercice académique, je suis sûr que c'est réalisable.