Можно ли представить все выражения 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

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

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

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

Answer 3

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

Answer 4

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

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

2 4 + 7 8 + *

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

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