Зачем нам нужен префикс, постфиксная запись
Я знаю, как каждый из них может быть преобразован друг в друга, но никогда не понимал, что их приложения. Обычная инфиксная операция вполне читабельна, но где она терпит неудачу, что привело к появлению префиксной и постфиксной нотации
4 ответа
Нотация с инфиксом легко читается людьми, тогда как нотация с префиксом / постфиксом легче разбирается для машины. Большим преимуществом префикса / постфикса является то, что никогда не возникает таких вопросов, как приоритет оператора.
Например, рассмотрим выражение инфикса 1 # 2 $ 3, Теперь мы не знаем, что означают эти операторы, поэтому существует два возможных соответствующих выражения postfix: 1 2 # 3 $ а также 1 2 3 $ #, Не зная правил, регулирующих использование этих операторов, инфиксное выражение по сути бесполезно.
Или, если выразить это в более общих терминах: можно восстановить исходное дерево (синтаксический анализ) из выражения пре-/ постфикса без каких-либо дополнительных знаний, но это не относится к выражениям инфикса.
Обозначение Postfix, также известное как RPN, очень легко обрабатывать слева направо. Операнд помещается в стек; оператор извлекает свои операнды из стека и выводит результат. Небольшой или никакой разбор необходим. Он используется Forth и некоторыми калькуляторами (HP калькуляторы известны для использования RPN).
Обозначение префикса почти так же легко обрабатывается; это используется в Лиспе.
По крайней мере, в случае префиксной нотации: преимущество использования префиксного оператора состоит в том, что синтаксически он читается так, как будто оператор является вызовом функции.
Другой аспект префикса / постфикса по сравнению с инфиксом заключается в том, что арность оператора (к скольким аргументам он применяется) больше не должна быть ограничена ровно 2. Она может быть больше, а иногда и меньше (0 или 1, когда значения по умолчанию подразумевается, естественно, как ноль для сложения / вычитания, один для умножения / деления).
В случае инфиксного выражения время, необходимое для оценки, составляет O(n^2) Причина - приоритет операторов. Пример: a+b*c В этом случае мы не будем напрямую оценивать a + b. Сначала мы просматриваем все выражение и находим оператор, имеющий наивысший приоритет. В нашем случае это *, поэтому сначала мы вычисляем b * c и, таким образом, снова выполняем ту же процедуру снова, пока не завершим вычисление выражения
Но это не так в случае постфиксного или инфиксного выражения. время, необходимое для вычисления постфиксного выражения, составляет O(n)
Преобразование инфиксов в постфикс ==== O(n) Оценка постфикса ==== O(n)
Общее время = O(n) + O(n)= O(n)
В случае вычисления постфикса нам не нужно думать о приоритете операторов. Просто нам нужно оценить слева, чтобы написать
Точно так же в случае префиксного выражения нам нужно оценивать справа налево