Почему постфиксная (rpn) нотация используется чаще, чем префикс?
Под использованием я подразумеваю его использование во многих калькуляторах, таких как HP35-
Мои догадки (и заблуждения) -
- postfix на самом деле более эффективно использует память -(поэтому оставляйте комментарии здесь). (путаница - алгоритм оценки обоих одинаков со стеком)
- Тип ввода с клавиатуры в калькуляторах тогда (путаница - это не должно было иметь большого значения, поскольку это зависит только от порядка операторов, указанных первым или последним)
Еще один способ задать этот вопрос - какие преимущества у постфиксной записи перед префиксом?
Кто-нибудь может просветить меня?
5 ответов
Для одного легче осуществить оценку.
При использовании префикса, если вы нажимаете оператор, а затем его операнды, вам необходимо заранее знать, когда у оператора есть все его операнды. По сути, вам нужно отслеживать, когда у выдвинутых операторов есть все свои операнды, чтобы вы могли развернуть стек и оценить.
Поскольку сложное выражение, скорее всего, приведет к тому, что в стеке будет много операторов, вам потребуется структура данных, которая может это обработать.
Например, это выражение: - + 10 20 + 30 40 будет один - и один + в стеке одновременно, и для каждого вам нужно знать, есть ли у вас доступные операнды.
С суффиксом, когда вы нажимаете на оператор, операнды уже (должны) уже в стеке, просто извлекаете операнды и выполняете оценку. Вам нужен только стек, который может обрабатывать операнды, и никакой другой структуры данных не требуется.
Префиксная нотация, вероятно, чаще используется... в математике, в выражениях типа F(x,y). Это очень старое соглашение, но, как и многие старые системы (футы и дюймы, бумага для писем), оно имеет недостатки по сравнению с тем, что мы могли бы сделать, если бы использовали более продуманную систему.
Почти каждый первый учебник по математике в университете должен тратить страницу, по крайней мере, объясняя, что f(g(x)) значит мы применяем g будет первый f, Делать это в порядке чтения имеет гораздо больше смысла: x.f.g значит мы применяем f первый. Тогда, если мы хотим применить h "после" мы просто говорим x.f.g.h,
В качестве примера рассмотрим проблему в 3d ротациях, с которой мне недавно пришлось столкнуться. Мы хотим повернуть вектор в соответствии с соглашением XYZ. В postfix операция vec.rotx(phi).roty(theta).rotz(psi), С префиксом приходится перегружать * или же () и затем обратный порядок операций, например, rotz*roty*rotx*vec, Это склонно к ошибкам и раздражает необходимость думать об этом все время, когда вы хотите думать о более серьезных проблемах.
Например, я видел что-то вроде rotx*roty*rotz*vec в чужом коде, и я не знал, было ли это ошибкой или необычным соглашением о ротации ZYX. Я до сих пор не знаю. Программа работала, поэтому она была внутренне самосогласованной, но в этом случае префиксная нотация затрудняла поддержку.
Другая проблема с префиксной нотацией заключается в том, что когда мы (или компьютер) анализируем выражение f(g(h(x))) мы должны держать f в нашей памяти (или в стеке), то g, затем hтогда хорошо, мы можем подать заявку h в xтогда мы можем подать заявку g к результату, то f к результату. Слишком много вещей в памяти по сравнению с x.f.g.h, В какой-то момент (для людей гораздо раньше, чем для компьютеров) у нас закончится память. Неудача таким образом не распространена, но зачем открывать дверь, когда x.f.g.h не требует кратковременной памяти. Это как разница между рекурсией и зацикливанием.
И еще одна вещь: f(g(h(x))) имеет так много скобок, что начинает выглядеть как Лисп. Постфиксная нотация однозначна, когда дело касается приоритета оператора.
Некоторые математики (в частности, Натан Джекобсон) пытались изменить соглашение, потому что с постфиксом намного проще работать в некоммутативной алгебре, где порядок действительно важен, но мало что дает. Но так как у нас есть шанс сделать что-то лучше, в области компьютерных технологий, мы должны воспользоваться этой возможностью.
По сути, потому что если вы пишете выражение в postfix, вы можете оценить это выражение, используя только стек:
Прочитайте следующий элемент выражения,
Если это операнд, вставьте в стек,
В противном случае считайте из операндов стека, требуемых операцией, и поместите результат в стек.
Если не конец выражения, перейдите к 1.
пример
expression = 1 2 + 3 4 + *
stack = [ ]
Read 1, 1 is Operand, Push 1
[ 1 ]
Read 2, 2 is Operand, Push 2
[ 1 2 ]
Read +, + is Operation, Pop two Operands 1 2
Evaluate 1 + 2 = 3, Push 3
[ 3 ]
Read 3, 3 is Operand, Push 3
[ 3 3 ]
Read 4, 4 is Operand, Push 4
[ 3 3 4 ]
Read +, + is Operation, Pop two Operands 3 4
Evaluate 3 + 4 = 7, Push 7
[ 3 7 ]
Read *, * is Operation, Pop two Operands 3 7
Evaluate 3 * 7 = 21, Push 21
[ 21 ]
Оффлайн оценка обоих обозначений одинакова в теоретической машине
(Стремительная стратегия оценки) Оценка только с одним стеком (без помещения оператора в стек)
Это может быть сделано путем оценки префикс-нотации right-to-left,
- 7 + 2 3
# evaluate + 2 3
- 7 5
# evaluate - 7 5
2
Это то же самое, что и оценка Postfix-нотации left-to-right,
7 2 3 + -
# put 7 on stack
7 2 3 + -
# evaluate 2 3 +
7 5 -
# evaluate 7 5 -
2
(Оптимизированная стратегия короткого замыкания) Оценка с двумя стеками (один для оператора и один для операнда)
Это может быть сделано путем оценки префикс-нотации left-to-right,
|| 1 < 2 3
# put || in instruction stack, 1 in operand stack or keep the pair in stack
instruction-stack: or
operand-stack: 1
< 2 3
# push < 2 3 in stack
instruction-stack: or, less_than
operand-stack: 1, 2, 3
# evaluate < 2 3 as 1
instruction-stack: or
operand-stack: 1, 1
# evaluate || 1 1 as 1
operand-stack:1
Обратите внимание, что мы можем сделать оптимизацию короткого замыкания для boolean Выражение здесь легко (по сравнению с предыдущей оценочной последовательностью).
|| 1 < 2 3
# put || in instruction stack, 1 in operand stack or keep the pair in stack
instruction-stack: or
operand-stack: 1
< 2 3
# Is it possible to evaluate `|| 1` without evaluating the rest ? Yes !!
# skip < 2 3 and put place-holder 0
instruction-stack: or
operand-stack: 1 0
# evaluate || 1 0 as 1
operand-stack: 1
Это то же самое, что и оценка Postfix-нотации right-to-left,
(Оптимизированная стратегия короткого замыкания) Оценка с одним стеком, который принимает кортеж (такой же, как указано выше)
Это может быть сделано путем оценки префикс-нотации left-to-right,
|| 1 < 2 3
# put || 1 in tuple-stack
stack tuple[or,1,unknown]
< 2 3
# We do not need to compute < 2 3
stack tuple[or,1,unknown]
# evaluate || 1 unknown as 1
1
Это то же самое, что и оценка Postfix-нотации right-to-left,
Онлайн оценка в калькуляторе, когда человек вводит данные слева направо
При вводе чисел в калькулятор, Postfix-нотация 2 3 + может быть оценен мгновенно, без какого-либо знания о символе, который собирается поставить человек. Это противоположно префиксной нотации, потому что когда мы имеем - 7 + нам нечего делать, пока мы не получим что-то вроде - 7 + 2 3,
Онлайн оценка в калькуляторе, когда человек вводит данные справа налево
Теперь префикс-нотацию можно оценивать + 2 3 мгновенно, в то время как Postfix-нотация ожидает дальнейшего ввода, когда она имеет 3 + -,
Пожалуйста, обратите внимание на @AshleyF, заметьте, что арабский язык пишет справа налево, в отличие от английского языка, который пишет слева направо!
Я предполагаю, что little-endian и big-endian связаны с этим обозначением префикса / постфикса.
Последний комментарий: обратная польская запись сильно поддерживается Дейкстрой (он является сильным противником оптимизации короткого замыкания и считается изобретателем обратной польской записи). Это ваш выбор, чтобы поддержать его мнение или нет (я не).
Если вам нравится, что ваш порядок чтения человеком совпадает с порядком оценки, основанным на стеке машины, тогда postfix - хороший выбор.
То есть, если вы читаете слева направо, что не все делают (например, иврит, арабский,...). И при условии, что ваша машина оценивает с помощью стека, что не все делают (например, переписывание терминов - см. Радость).
С другой стороны, нет ничего плохого в том, что человек предпочитает префикс, в то время как машина оценивает "обратно вперед / снизу вверх". Сериализация также может быть обращена вспять, если задача состоит в оценке по мере поступления токенов. Вспомогательное средство может работать лучше в префиксной нотации (знание функций / слов в первую очередь может помочь в определении допустимых аргументов), но вы всегда можете ввести справа налево.
Я считаю, что это просто соглашение...