Перевод инфиксной нотации в постфиксную и получение результата в Kotlin

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

3. Если входящий элемент является левой скобкой, поместите (PUSH) его в стек (STACK).
4. Если входящий элемент является правой скобкой, выгружаем стек (POP) и добавляем его элементы в очередь (QUEUE), пока не увидите левую круглую скобку. Удалите найденную скобку из стека (STACK).
5. В конце выражения выгрузите стек (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-+.

1. Если входящий элемент является числом, поместите(PUSH) его в стек (STACK)
2. Если входящий элемент является оператором (*-/+), необходимо получить (POP) два последних числа из стека (STACK) и выполнить соответствующую операцию. Далее поместите (PUSH) полученный результат в стек (STACK).
3. Когда выражение закончится, число на вершине (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

1. Перебираем выражение, заполняем 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() } 

2. Преобразуем инфиксную запись в постфиксную

   private var stack = mutableListOf<String>() private var queue = mutableListOf<String>() private var expressionList = mutableListOf<String>()  fun main() {     parseExpression()     getPostFixEx() }  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) } 

3. Произведем расчет постфиксной записи

   private var stack = mutableListOf<String>() private var queue = mutableListOf<String>() private var expressionList = mutableListOf<String>()  fun main() {     parseExpression()     getPostFixEx()     calcPostFix() }  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