코틀린: infix expression을 prefix expression으로 변환(2/5) - List 구현

앞에서 중위 수식을 전위 수식으로 바꾸기 위해 자료 구조로 Stack 타입을 사용했습니다. Stack 대신 List 컬렉션을 사용해서 구현하려면 앞에서 작성한 코드를 어떻게 수정하면 될까요? Stack과 List는 정반대 방식으로 원소를 저장하고 관리합니다. 프로그램을 개발할 때 성능 개선이나 설계 요구 조건을 충족하기 위해 핵심 자료 구조를 변경해야 할 때가 종종 있습니다. 자료구조의 차이점만 정확히 알고 있으면 어렵지 않게 바꿀 수 있습니다.

앞에서 구현한 코드에서는 Stack 타입 객체에서 제공하는 3개의 메소드 push, pop, peek를 사용했습니다. 

fun makeSubExpr(op: Stack<Char>, exp: Stack<String>) {
    val op = op.pop()
    val operand1 = exp.pop()
    val operand2 = exp.pop()
    exp.push(op + operand2 + operand1)
}

 

원소가 수시로 바뀌기 때문에 List는 불변 리스트가 아니라 가변 리스트 MutableList를 사용해야 합니다. 리스트 컬렉션은 마지막에 추가한 원소가 리스트의 끝에 추가됩니다. 스택의 pop() 함수는 리스트 객체에서는 마지막 원소를 꺼내야 합니다. pop() 함수도 스택에서 원소를 제거하기 때문에 리스트 객체도 removeAt() 함수를 사용합니다. 단, removeAt() 함수의 인자는 마지막 원소의 인덱스를 지정해야 합니다. 스택의 push() 함수는 리스트 객체의 add() 함수를 사용하면 됩니다.

fun makeSubExpr(op: MutableList<Char>, exp: MutableList<String>) {
    val op = op.removeAt(op.size - 1)
    val operand1 = exp.removeAt(exp.size - 1)
    val operand2 = exp.removeAt(exp.size - 1)
    exp.add(op + operand2 + operand1)
}

 

이제 함수 infixToPrefix()를 수정해야 합니다. Stack 타입 객체로 선언한 operators와 expr을 mutableListOf<T>()를 사용해 가변 리스트 객체를 생성합니다. Stack 객체의 peek() 함수는 리스트 객체에서는 last()로 바꾸면 됩니다.

fun infixToPrefix(infix: String): String {
    val operators = mutableListOf<Char>()
    val expr = mutableListOf<String>()

    for (ch in infix) {
        if (ch.isWhitespace()) continue
        if (ch.isLetterOrDigit()) {
            expr.add(ch.toString())
        }
        else if (isOperator(ch)){
            while (operators.isNotEmpty() &&
                precedence(ch) <= precedence(operators.last())) {
                makeSubExpr(operators, expr)
                println("In the while loop inside the for loop: expr = ${expr.last()}")
            }
            operators.add(ch)
            println("in the for loop : operators = ${operators.last()}")
        }
    }
    while (operators.isNotEmpty()) {
        makeSubExpr(operators, expr)
        println("In the while loop: expr = ${expr.last()}")
    }
    return expr.last()
}

 

전체 코드를 다시 볼까요. 자료 구조를 Stack에서 List로 바꿨을 때 코드 수정이 필요한 함수와 수정이 필요 없는 함수로 구분할 수 있습니다. 수정이 필요한 함수는 makeSubExpr()과 infixToPrefix() 뿐입니다. 나머지 함수는 수정 없이 그대로 사용할 수 있습니다.

enum class Precedence (val priority: Int) { ... }
const val OP_LIST = "+-*/^"

fun isOperator(op: Char): Boolean = op in OP_LIST
fun precedence(op: Char): Int { ... }
fun makeSubExpr(op: MutableList<Char>, exp: MutableList<String>) { ... }
fun infixToPrefix(infix: String): String { ... }

fun main() {
    val infix = "a + b * c"
    val prefix = infixToPrefix(infix)
    println("Infix notation: $infix")
    println("Prefix notation: $prefix")
}