Pouvez tous RPN expressions être représentée telle que tous les opérateurs apparaissent sur la gauche et tous les opérandes apparaissent sur la droite?

Question

J'ai 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 ya deux façons que l'on peut écrire l'expression ci-dessus avec le même les opérateurs et d'opérandes tel que les opérandes viennent tous d'abord:"4 4 4 + /" et "4 4 4 / +", ni de ce qui s'évaluer à 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é de permuter les éléments sur la pile, alors oui, c'est possible, sinon, non.

Pensées?

Answer 1

Considérons l'expression algébrique:

(a + b) * (c + d)

L'évidence de la traduction à la RPN serait:

a b + c d + *

Même avec une opération de swap disponible, je ne pense pas qu'il y est 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 de swap à obtenir à la fois a et b en place pour une opération+.Au lieu de cela, vous auriez besoin d'un plus sophistiqué pile de fonctionnement (comme les roll) pour obtenir a et b dans le bon endroit.Je ne sais pas si un rouleau opération serait suffisant pour tous les cas, que ce soit.

Answer 2

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

Answer 3

Je sais que c'est un fil très vieux, mais je viens de trouver ça aujourd'hui et je voulais dire que je pense que la réponse à la question est OUI.Je suis convaincu que toutes les RPN expressions 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 de la normale des opérations arithmétiques, nous sommes autorisés à inclure trois autres 'navigation' opérateurs dans la représentation.

Toute expression arithmétique peut être représenté comme un arbre binaire, avec des variables et des constantes à nœuds feuilles, arithmétique binaire opérations à la fourche de l'arbre, et les opérations unaires comme la négation, de la réciprocité ou de la racine carrée, le long de toutes les branches.Les trois autres opérations, je suggère de représenter la construction d'une branche gauche, la construction d'une branche de droite, ou de parvenir à un nœud feuille dans un arbre binaire.Maintenant, si nous mettons toutes les opérandes de la gauche de la chaîne d'entrée en fonction de la position respective de leurs feuilles dans l'arbre, nous pouvons fournir le reste de la chaîne d'entrée avec les opérations de dire comment reconstruire l'appropriées arbre binaire dans la mémoire et insérez les opérandes et les opérations mathématiques à l'corriger les points.Enfin, une profondeur d'abord de l'arbre-traversée de l'algorithme est appliqué pour calculer le résultat.

Je ne sais pas si cela a de toute application pratique.Il est probablement trop inefficace comme moyen d'encoder et de décoder les expressions.Mais comme un exercice académique, je suis sûr que c'est réalisable.

Answer 4

Il suffit de montrer un qui ne peut pas pour vous dire la réponse à cette question.

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

2 4 + 7 8 + *

Peu importe comment vous réorganiser cela, vous vous retrouverez avec quelque chose qui doit être résumé avant de vous rendre sur.

Au moins je le crois.