Как преобразовать инфиксное выражение в постфиксное. Реализация на языке Kotlin.

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

• STACK — стек это тип данных, представляющий собой список элементов, организованных по принципу LIFO (последним пришёл — первым вышел). Более детальное изучение здесь
• QUEUE — очередь это тип данных, представляющий собой список элементов, организованных по принципу FIFO (первый пришёл — первым вышел). Более детальное изучение здесь
• PUSH — проталкивание, при проталкивании добавляется новый элемент, в вершину стека, то есть текущий элемент становиться вершиной стека (последним элементом). Детально изучить можно здесь
• POP — выгружает элемент который, является вершиной стека. Вершиной становится последний элемент в стеке. Более детально можно почитать здесь.
• TOP — вершина стека, то-есть последний его элемент

Алгоритм преобразования из инфиксного в постфиксное выражение

Перебираем выражение слева на право.

• Если входящий элемент число, то добавляем его в очередь (QUEUE).
• Если входящий элемент оператор (+, -, *, /) то проверяем:
• Если стек (STACK) пуст или содержит левую скобку в вершине (TOP), то добавляем (PUSH) входящий оператор в стек (STACK).
• Если входящий оператор имеет более высокий приоритет чем вершина (TOP), поместите (PUSH) его в стек (STACK).
• Если входящий оператор имеет более низкий или равный приоритет, чем вершине (TOP), выгружаем POP в очередь (QUEUE), пока не увидите оператор с меньшим приоритетом или левую скобку на вершине (TOP), затем добавьте (PUSH) входящий оператор в стек (STACK).
• Если входящий элемент является левой скобкой, поместите (PUSH) его в стек (STACK).
• Если входящий элемент является правой скобкой, выгружаем стек (POP) и добавляем его элементы в очередь (QUEUE), пока не увидите левую круглую скобку. Удалите найденную скобку из стека (STACK).
• В конце выражения выгрузите стек (POP) в очередь (QUEUE)

Рассмотрим пример: 5*6+(2-9)
Перебираем выражение слева на право.
Начальное состояние STACK = empty
Начальное состояние QUEUE = empty

• Входящий элемент 5. Добавляем в очередь.
  STACK = empty
  QUEUE = 5
• Входящий элемент *. Добавляем в стек.
  STACK = *
  QUEUE = 5
• Входящий элемент 6. Добавляем в очередь.
  STACK = *
  QUEUE = 5, 6
• Входящий элемент +. Здесь мы видим, что входящий оператор имеет более низкий приоритет чем вершина стека. Согласно алгоритму, выгружаем стек в очередь пока не увидим на вершине стека оператор с меньшим приоритетом или левую скобку. После выгрузки входящий оператор добавляем в стек.
  STACK = +
  QUEUE = 5, 6, *
• Входящий элемент (. Добавляем в стек.
  STACK = +, (
  QUEUE = 5, 6, *
  
• Входящий элемент 2. Добавляем в очередь.
  STACK = +, (
  QUEUE = 5, 6, *, 2
  
• Входящий элемент — . Здесь мы видим, что входящий оператор " — ", а на вершине стека "(". Согласно алгоритму добавляем в стек.
  STACK = +, (, —
  QUEUE = 5, 6, *, 2
  
• Входящий элемент 9 . Согласно алгоритму добавляем в очередь.
  STACK = +, (, —
  QUEUE = 5, 6, *, 2, 9
  
• Входящий элемент ) . Согласно алгоритму выгружаем стек в очередь, пока не найдем левую скобку. Потом удаляем из стека левую скобку.
  STACK = +
  QUEUE = 5, 6, *, 2, 9, —
  
• После того, как выражение закончилось мы выгружаем все в очередь.
  STACK = empty
  QUEUE = 5, 6, *, 2, 9, -, +
  

В итоге мы получили постфиксное выражение 56*29-+.

Отлично, мы получили постфиксное выражение, которое намного легче посчитать

Алгоритм получение результата из постфиксного выражения

Перебираем постфиксное выражение слева на право.

• Если входящий элемент является числом, поместите(PUSH) его в стек (STACK)
• Если входящий элемент является оператором (*-/+), необходимо получить (POP) два последних числа из стека (STACK) и выполнить соответствующую операцию. Далее поместите (PUSH) полученный результат в стек (STACK).
• Когда выражение закончится, число на вершине (TOP) стека (STACK) является результатом.

Получим результат постфиксного выражения: 56*29-+.
Перебираем выражение слева на право.
Начальное состояние STACK = empty

• Входящий элемент 5. Добавляем в стек.
  STACK = 5
• Входящий элемент 6. Добавляем в стек.
  STACK = 5, 6
• Входящий элемент * . Получаем два последних числа из стека (5 * 6), умножаем их, и результат возвращаем в стек.
  STACK = 30
• Входящий элемент 2 . Добавляем в стек.
  STACK = 30, 2
• Входящий элемент 9 . Добавляем в стек.
  STACK = 30, 2, 9
• Входящий элемент — . Получаем два последних числа из стека (2 — 9), получаем их разность, и результат возвращаем в стек.
  STACK = 30, -7
• Входящий элемент + . Получаем два последних числа из стека (-7 + 30), суммируем их, и результат возвращаем в стек.
  STACK = 23

Соответственно результат выражения:
Инфиксное выражение: 5*6+(2-9) = 23
Постфиксное выражение: 56*29-+ = 23

Вот и все. Таким способом, можно посчитать любое сложное математическое выражение.

Далее я реализую этот алгоритм на языке Koltin, выложен на GithubGist.

https://gist.github.com/mrDevGo/c1aec4090e2afb1c64683fc570e7b2dd