Что такое инфиксная нотация и постфиксная можно узнать если внимательно почитать в Википедии. Так же есть статья на Хабре.
В это статье я покажу простой и понятный алгоритм преобразования инфиксной записи в постфиксную. Данный алгоритм я реализую на языке Kotlin, хотя алгоритм подойдет для любого языка программирования.
Ну что, вперед.
Для лучшего понимания и запоминания, будем использовать аббревиатуры:
Вот и все, все достаточно просто и понятно.
В это статье я покажу простой и понятный алгоритм преобразования инфиксной записи в постфиксную. Данный алгоритм я реализую на языке Kotlin, хотя алгоритм подойдет для любого языка программирования.
Ну что, вперед.
Для лучшего понимания и запоминания, будем использовать аббревиатуры:
- STACK — стек это тип данных, представляющий собой список элементов, организованных по принципу LIFO (последним пришёл — первым вышел). Более детальное изучение здесь
- QUEUE — очередь это тип данных, представляющий собой список элементов, организованных по принципу FIFO (первый пришёл — первым вышел). Более детальное изучение здесь
- PUSH — проталкивание, при проталкивании добавляется новый элемент, в вершину стека, то есть текущий элемент становиться вершиной стека (последним элементом). Детально изучить можно здесь
- POP — выгружает элемент который, является вершиной стека. Вершиной становится последний элемент в стеке. Более детально можно почитать здесь.
- TOP — вершина стека, то-есть последний его элемент
Алгоритм преобразования из инфиксного в постфиксное выражение
Перебираем выражение слева на право.
Рассмотрим пример: 5*6+(2-9)
Перебираем выражение слева на право.
Начальное состояние STACK = empty
Начальное состояние QUEUE = empty
В итоге мы получили постфиксное выражение 56*29-+.
- Если входящий элемент число, то добавляем его в очередь (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-+.
Алгоритм получение результата из постфиксного выражения
Перебираем постфиксное выражение слева на право.
Получим результат постфиксного выражения: 56*29-+.
Перебираем выражение слева на право.
Начальное состояние STACK = empty
Соответственно результат выражения:
Инфиксное выражение: 5*6+(2-9) = 23
Постфиксное выражение: 56*29-+ = 23
- Если входящий элемент является числом, поместите(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
Для примера реализуем на языке Kotlin
Попробуем рассчитать сложное выражение: 5*8*(2+9)+(7*5+8-9*(5*5)+5) = 263
Результат выполнения:
Инфиксное выражение: 5*8*(2+9)+(7-5+8-9*(5*5)+5)
Постфиксное выражение: 58*29+*75-8+955**-5++
Ответ: 230
- Перебираем выражение, заполняем expressionList: mutableListOf<String>()
private var stack = mutableListOf<String>() private var queue = mutableListOf<String>() private var expressionList = mutableListOf<String>() fun main() { parseExpression() } fun parseExpression() { "5*8*(2+9)+(7-5+8-9*(5*5)+5)".forEach { expressionList.add(it.toString()) } print("Инфиксное выражение: ") expressionList.forEach { print(it) } println() }
- Преобразуем инфиксную запись в постфиксную
private fun getPostFixEx() { // Перебираем expressionList expressionList.forEach { when { //Если входящий элемент левая скобка делаем PUSH it == "(" -> push(it) //Если входящий элемент правая скобка делаем POP it == ")" -> { if (expressionList.contains("(")) { pop() } } //Если входящий элемент число, то добавляем в очередь Regex("[\\d]").containsMatchIn(it) -> addQueue(it) //Если входящий элемент + или - Regex("[+-]").containsMatchIn(it) -> /* Проверяем, если стек пустой или на вершине стека левая скобка, * то делаем PUSH */ if (stack.isEmpty() || stack.last() == "(") push(it) /* Иначе, если на вершине стека оператор имеющий больший * приоритет, то делаем POP, потом PUSH */ else if (stack.last().contains(Regex("[/*]"))) { pop() push(it) } // Иначе просто делаем PUSH else { addQueue(stack.last()) stack[stack.lastIndex] = it } //Если входящий элемент * или / Regex("[*/]").containsMatchIn(it) -> { /* Проверяем, если на вершине стека элемент с таким же приоритетом, * то делаем POP */ if (stack.isNotEmpty() && (stack.last() == "*" || stack.last() == "/")) { pop() } // Потом делаем PUSH push(it) } } } // Когда перебрали все элементы выражения, то добавляем из стека элементы в очередь if (stack.isNotEmpty()) { for (i in stack.lastIndex downTo 0) { if (stack[i] != "(") { addQueue(stack[i]) } } } print("Постфиксное выражение: ") queue.forEach { print(it) } println() } private fun pop() { // Выгружаем стек в очередь пока не найдем левую скобку, потом удаляем скобку из стека Loop@ for (i in stack.lastIndex downTo 0) { if (stack[i] == "(") { stack[i] = " " break@Loop } addQueue(stack[i]) stack[i] = " " } stack.removeIf { it == " " } } private fun addQueue(item: String) { queue.add(item) } private fun push(item: String) { stack.add(item) }
- Произведем расчет постфиксной записи
private fun calcPostFix() { //Создаем стек для работы val stack = mutableListOf<Int>() // Перебераем все эелементы очереди for (item in queue) { when { // Если входящий элемент - число, то добавляем в стек Regex("[\\d]").containsMatchIn(item) -> { stack.add(item.toInt()) } /* Если входящий элемент + , берем два последних элемента и производим советующую операцию */ item == "+" -> { stack[stack.lastIndex - 1] = stack[stack.lastIndex - 1] + stack.last() stack.removeAt(stack.lastIndex) } /* Если входящий элемент * , берем два последних элемента и производим советующую операцию */ item == "*" -> { stack[stack.lastIndex - 1] = stack[stack.lastIndex - 1] * stack.last() stack.removeAt(stack.lastIndex) } /* Если входящий элемент / , берем два последних элемента и производим советующую операцию */ item == "/" -> { stack[stack.lastIndex - 1] = stack[stack.lastIndex - 1] / stack.last() stack.removeAt(stack.lastIndex) } /* Если входящий элемент -, берем два последних элемента и производим советующую операцию */ item == "-" -> { stack[stack.lastIndex - 1] = stack[stack.lastIndex - 1] - stack.last() stack.removeAt(stack.lastIndex) } } } // Результат - это элемент, который остался в стеке println("Ответ: ${stack.first()}") }
Результат выполнения:
Инфиксное выражение: 5*8*(2+9)+(7-5+8-9*(5*5)+5)
Постфиксное выражение: 58*29+*75-8+955**-5++
Ответ: 230
Вот и все, все достаточно просто и понятно.