Могут ли все выражения RPN быть представлены так, чтобы все операторы располагались слева, а все операнды — справа?

Question

Я убедил себя, что они не могут.

Возьмем, к примеру:

4 4 + 4 /

куча:4 стека:4 4 4 4 = 8 стопок:8 стопок:8 4 8/4 = 2 стопки:2

Есть два способа написать приведенное выше выражение с теми же операторами и операндами, чтобы все операнды были первыми:«4 4 4 /» и «4 4 4 /», ни один из которых не равен 2.

Стек «4 4 4 /»:4 стека:4 4 стека:4 4 4 4 4 = 8 стопок:4 8 4 / 8 = 0,5 стека:0,5

Стек "4 4 4 /":4 стека:4 4 стека:4 4 4 4 / 4 = 1 стопка:4 1 4 1 = 5 стопок:5

Если у вас есть возможность менять местами предметы в стеке, то да, это возможно, иначе нет.

Мысли?

Answer 1

Рассмотрим алгебраическое выражение:

(a + b) * (c + d)

Очевидный перевод на RPN будет такой:

a b + c d + *

Даже при наличии операции обмена я не думаю, что есть способ собрать все операторы справа:

a b c d +
a b S

где S — сумма c и d.На этом этапе вы не могли использовать одну операцию замены, чтобы получить и a, и b для операции.Вместо этого вам понадобится более сложная операция со стеком (например, перекат), чтобы расположить a и b в нужном месте.Я также не знаю, будет ли операция прокрутки достаточной для всех случаев.

Answer 2

На самом деле вы дали не только ответ, но и убедительное доказательство, рассмотрев контрпример, которого достаточно, чтобы опровергнуть предположение, вынесенное в заголовок.

Answer 3

Я знаю, что это очень старая тема, но я нашел ее только сегодня и хотел сказать, что считаю, что ответ на первоначальный вопрос — ДА.Я уверен, что все выражения RPN можно представить так, чтобы все операторы располагались слева, а все операнды — справа, если в дополнение к обычным арифметическим операциям нам разрешено включать в представление три дополнительных «навигационных» оператора.

Любое арифметическое выражение можно представить в виде двоичного дерева с переменными и константами в конечных узлах, двоичными арифметическими операциями в развилках дерева и унарными операциями, такими как отрицание, обратное выражение или квадратный корень на любых ветвях.Три дополнительные операции, которые я предлагаю, представляют собой построение левой ветви, построение правой ветви или достижение конечного узла в двоичном дереве.Теперь, если мы разместим все операнды слева от входной строки в соответствии с положением их соответствующих листьев в дереве, мы сможем снабдить остальную часть входной строки операциями, сообщающими, как восстановить соответствующее двоичное дерево в памяти и вставить операнды и математические операции в него в правильных точках.Наконец, для вычисления результата применяется алгоритм обхода дерева в глубину.

Не знаю, имеет ли это какое-либо практическое применение.Вероятно, это слишком неэффективно для кодирования и декодирования выражений.Но я уверен, что в качестве академического упражнения это осуществимо.

Answer 4

Достаточно показать тому, кто не может, чтобы сказать вам ответ на этот вопрос.

Если вы не можете изменить порядок содержимого стека, то выражение (2 4)*(7 8) не может быть переставлено.

2 4 + 7 8 + *

Независимо от того, как вы это переупорядочите, в итоге вы получите что-то, что нужно будет суммировать, прежде чем продолжить.

По крайней мере, я так считаю.