Спустя долгое время я собираюсь работать над оценкой экспрессии, поэтому я пишу это сообщение в блоге, чтобы вернуться к нему и объяснить его самому себе.

Выражения, которые мы (люди) пишем, называются инфиксными выражениями, поскольку операторы помещаются между операндами, чтобы обозначить поток выполнения выражения.

Рассмотрим следующее выражение.

A + B, это инфиксное выражение, потому что оператор «+» стоит между операндами «A» и «B».

Для оценки выражений вручную полезно использовать инфиксную нотацию, поскольку она легко понимается человеческим мозгом.

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

Давайте посмотрим, что такое выражения Postfix:

В выражениях Postfix операторы идут после операндов. Ниже приведены инфиксные и соответствующие выражения Postfix.

A + B → A B +

Как упоминалось в приведенном выше примере, в выражении Postfix оператор стоит после операндов.

Чтобы начать преобразование выражения Infix в Postfix, во-первых, мы должны знать о приоритете операторов.

Приоритет оператора:

При оценке выражений решающее значение имеет приоритет операторов.

Верхний оператор в таблице имеет наивысший приоритет. В соответствии с приоритетом операторы будут помещены в стек.

Давайте посмотрим на пример преобразования инфикса в Postfix, мы начнем с простого,

Инфиксное выражение: A + B

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

Итак, у нас есть два элемента,

  1. Пустая строка выражения
  2. Пустой стек операторов

Сначала в выражении мы встречаем «A», поскольку это операнд, который мы добавим в строку выражения. Итак, теперь два элемента выглядят так, как показано ниже,

  1. Строка выражения: A
  2. Стек операторов:

Второй токен, с которым мы сталкиваемся, - это оператор «+», поэтому мы поместим его в стек операторов.

  1. Строка выражения: A
  2. Стек операторов: +

Третий токен - это операнд «B», поэтому мы добавим его в строку выражения.

  1. Строка выражения: A B
  2. Стек операторов: +

Таким образом, мы обработали все токены в данном выражении, теперь нам нужно извлечь оставшиеся токены из стека и добавить их в строку выражения.

Извлеките из стека оператор «+» и добавьте его в строку выражения, в которой уже есть «A B».

Итак, теперь вывод становится «A B +», который является нотацией Postfix для данного инфиксного выражения «A + B».

Второй пример:

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

( ( A + B ) — C * ( D / E ) ) + F

Данное выражение заключено в круглые скобки для обозначения приоритета. Итак, давайте начнем с преобразования с двумя пустыми элементами соответственно,

  1. Пустая строка выражения
  2. Пустой стек операторов

Первый обнаруженный токен - открытая скобка, добавьте ее в стек операторов.

  1. Строка выражения:
  2. Стек операторов: (
  3. Оставшееся выражение: (A + B) - C * (D / E)) + F

Второй встреченный токен - снова открытая скобка, добавьте ее в стек.

  1. Строка выражения:
  2. Стек операторов: ((
  3. Оставшееся выражение: A + B) - C * (D / E)) + F

Следующим токеном выражения является операнд «A», поэтому добавьте его в строку выражения.

  1. Строка выражения: A
  2. Стек операторов: ((
  3. Оставшееся выражение: + B) - C * (D / E)) + F

После этого у нас есть оператор «+», поэтому добавляем его в стек.

  1. Строка выражения: A
  2. Стек операторов: ((+
  3. Оставшееся выражение: B) - C * (D / E)) + F

Затем у нас есть операнд, поэтому добавьте его в строку выражения.

  1. Строка выражения: A B
  2. Стек операторов: ((+
  3. Оставшееся выражение: ) - C * (D / E)) + F

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

  1. Строка выражения: A B +
  2. Стек операторов: (
  3. Оставшееся выражение: - C * (D / E)) + F

Обратите внимание, что здесь мы не поместили закрывающую скобку в стек, вместо этого мы извлекли оператор «+» и добавили его в строку выражения, а также вытащили одну открывающую скобку из стека.

Далее мы сталкиваемся с оператором «-», поэтому помещаем его в стек.

  1. Строка выражения: A B +
  2. Стек операторов: (-
  3. Оставшееся выражение: C * (D / E)) + F

Далее идет операнд «C», поэтому добавьте его в строку выражения,

  1. Строка выражения: A B + C
  2. Стек операторов: (-
  3. Оставшееся выражение: * (D / E)) + F

Далее следует оператор «*», поэтому поместите его в стек.

  1. Строка выражения: A B + C
  2. Стек операторов: (- *
  3. Оставшееся выражение: (D / E)) + F

Далее следует открывающая скобка, поэтому добавьте ее в стек.

  1. Строка выражения: A B + C
  2. Стек операторов: (- * (
  3. Оставшееся выражение: D / E)) + F.

Далее идет операнд «D», поэтому добавьте его в строку выражения.

  1. Строка выражения: A B + C D.
  2. Стек операторов: (- * (
  3. Оставшееся выражение: / E)) + F

Затем мы сталкиваемся с оператором «/», поэтому помещаем его в стек.

  1. Строка выражения: A B + C D.
  2. Стек операторов: (- * (/
  3. Оставшееся выражение: E)) + F.

Затем нажмите «E», добавьте его в строку выражения.

  1. Строка выражения: A B + C D E
  2. Стек операторов: (- * (/
  3. Оставшееся выражение: )) + F

Затем закрывающая скобка, как мы видели ранее, мы не должны помещать ее в стек, вместо этого мы должны вытащить все операторы из стека и добавить их в строку выражения, пока мы не встретим открытую скобку. Затем вытолкните открывающую скобку из стека, но не добавляйте ее в строку выражения.

  1. Строка выражения: A B + C D E /
  2. Стек операторов: (- *
  3. Оставшееся выражение: ) + F

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

  1. Строка выражения: A B + C D E / * -
  2. Стек операторов:
  3. Оставшееся выражение: + F

Следующий токен - это оператор «+», поэтому поместите его в стек.

  1. Строка выражения: A B + C D E / * -
  2. Стек операторов: +
  3. Оставшееся выражение: F

Следующий токен - это операнд «F». Добавьте его в строку выражения.

  1. Строка выражения: A B + C D E / * - F
  2. Стек операторов: +
  3. Оставшееся выражение:

Поскольку мы обработали все инфиксное выражение, теперь нужно очистить стек операторов, вытащив все оставшиеся операторы и добавив их в строку выражения.

Здесь у нас есть оператор «+» в стеке, поэтому мы извлечем оператор «+» из стека и добавим его в строку выражения. Таким образом, результирующее выражение Postfix будет выглядеть так, как показано ниже,

Окончательное выражение Postfix: A B + C D E / * - F +

Надеюсь, вы поймете, если нет, дайте мне знать в комментариях.

✉️ Подпишитесь на рассылку еженедельно Email Blast 🐦 Подпишитесь на CodeBurst на Twitter , просмотрите 🗺️ Дорожная карта веб-разработчиков на 2018 год и 🕸️ Изучите веб-разработку с полным стеком .