Step by Step solution about How to resolve the algorithm Parsing/Shunting-yard algorithm step by step in the Kotlin programming language

This code snippet implements a function that converts an infix expression into its postfix equivalent. Infix expressions are expressions in which the operators are placed between the operands, while in postfix expressions the operands are placed before the operators. The code uses a stack to store the operators in the expression. It iterates through the tokens in the infix expression, and for each token it checks if it is an operator. If it is an operator, it pops operators from the stack until it finds an operator with a lower precedence than the current operator, and then it pushes the current operator onto the stack. If the token is a left parenthesis, it is pushed onto the stack. If the token is a right parenthesis, it pops operators from the stack until it finds a left parenthesis, and then it pops the left parenthesis from the stack. If the token is an operand, it is appended to the output string. After iterating through all the tokens in the infix expression, the code pops any remaining operators from the stack and appends them to the output string. Finally, the postfix expression is returned. Here is a breakdown of the code:

const val OPS = "-+/*^"

This is a constant string containing the operators that are supported by the function.

fun infixToPostfix(infix: String): String {

This is the main function that converts an infix expression into its postfix equivalent. It takes an infix expression as an argument and returns a postfix expression.

   val sb = StringBuilder()
   val s = Stack<Int>()
   val rx = Regex("""\s""")

These are the variables used by the function. sb is a StringBuilder that will store the postfix expression. s is a stack that will store the operators in the expression. rx is a regular expression that matches whitespace characters.

   for (token in infix.split(rx)) {

This loop iterates through the tokens in the infix expression.

       if (token.isEmpty()) continue

This checks if the token is empty and skips it if it is.

       val c = token[0]

This gets the first character of the token.

       val idx = OPS.indexOf(c)

This gets the index of the operator in the OPS string.

       // check for operator
       if (idx != - 1) {

This checks if the token is an operator.

           if (s.isEmpty()) {
               s.push(idx)
           }

If the stack is empty, the operator is pushed onto the stack.

           else {
               while (!s.isEmpty()) {
                   val prec2 = s.peek() / 2
                   val prec1 = idx / 2
                   if (prec2 > prec1 || (prec2 == prec1 && c != '^')) {
                       sb.append(OPS[s.pop()]).append(' ')
                   }
                   else break
               }
               s.push(idx)
           }

If the stack is not empty, the operator is compared with the operators on the stack. If the operator on the stack has a higher precedence than the current operator, the operator on the stack is popped and appended to the output string. This is repeated until an operator with a lower precedence than the current operator is found, or until the stack is empty. Then the current operator is pushed onto the stack.

       }
       else if (c == '(') {
           s.push(-2)  // -2 stands for '('
       }

If the token is a left parenthesis, it is pushed onto the stack.

       else if (c == ')') {

If the token is a right parenthesis, the operators on the stack are popped and appended to the output string until a left parenthesis is found. Then the left parenthesis is popped from the stack.

       else {
           sb.append(token).append(' ')
       }

If the token is an operand, it is appended to the output string.

   }

This completes the loop through the tokens in the infix expression.

   while (!s.isEmpty()) sb.append(OPS[s.pop()]).append(' ')

This pops any remaining operators from the stack and appends them to the output string.

   return sb.toString()
}

This returns the postfix expression.

fun main(args: Array<String>) {

This is the main function that calls the infixToPostfix function and prints the results.

   val es = listOf(
       "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3",
       "( ( 1 + 2 ) ^ ( 3 + 4 ) ) ^ ( 5 + 6 )"
   )

These are the infix expressions that are converted to postfix expressions.

   for (e in es) {
       println("Infix : $e")
       println("Postfix : ${infixToPostfix(e)}\n")
   }
}

This iterates through the infix expressions and prints the corresponding postfix expressions.

// version 1.2.0

import java.util.Stack

/* To find out the precedence, we take the index of the
   token in the OPS string and divide by 2 (rounding down).
   This will give us: 0, 0, 1, 1, 2 */
const val OPS = "-+/*^"

fun infixToPostfix(infix: String): String {
    val sb = StringBuilder()
    val s = Stack<Int>()
    val rx = Regex("""\s""")
    for (token in infix.split(rx)) {
        if (token.isEmpty()) continue
        val c = token[0]
        val idx = OPS.indexOf(c)

        // check for operator
        if (idx != - 1) {
            if (s.isEmpty()) {
                s.push(idx)
            }
            else {
                while (!s.isEmpty()) {
                    val prec2 = s.peek() / 2
                    val prec1 = idx / 2
                    if (prec2 > prec1 || (prec2 == prec1 && c != '^')) {
                        sb.append(OPS[s.pop()]).append(' ')
                    }
                    else break
                }
                s.push(idx)
            }
        }
        else if (c == '(') {
            s.push(-2)  // -2 stands for '('
        }
        else if (c == ')') {
            // until '(' on stack, pop operators.
            while (s.peek() != -2) sb.append(OPS[s.pop()]).append(' ')
            s.pop()
        }
        else {
            sb.append(token).append(' ')
        }
    }
    while (!s.isEmpty()) sb.append(OPS[s.pop()]).append(' ')
    return sb.toString()
}

fun main(args: Array<String>) {
    val es = listOf(
        "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3",
        "( ( 1 + 2 ) ^ ( 3 + 4 ) ) ^ ( 5 + 6 )"
    )
    for (e in es) {
        println("Infix : $e")
        println("Postfix : ${infixToPostfix(e)}\n")
    }
}