코틀린: infix expression을 prefix expression으로 변환(5/5) - 괄호 처리

앞의 예제에서는 수식에서 괄호(parentheses)를 처리하지 않았습니다. 괄호를 처리하기 전에 앞의 예제 코드에서 중복 코드가 여러 군데 사용되고 있습니다. 이 코드도 클래스의 멤버 함수로 구현해, 전체 코드를 간략화하겠습니다. 아래 메소드의 while 문에서 실행하는 문장이 중복 코드입니다.

private fun handleRemainingOperators() {
    while (opStack.isNotEmpty()) {
            val op = opStack.pop()
            val operand1 = exprStack.pop()
            val operand2 = exprStack.pop()
            exprStack.push(op + operand2 + operand1)
    }
}

 

메소드 handleRemainingOperator()에서 while 루프의 코드 블록을 새 멤버 함수 makeSubExpr()의 블록으로 정의합니다.  이제 메소드 handleRemainingOperator()는 아래처럼 간략화할 수 있습니다. 메소드 makeSubExpr()은 클래스 내부에서만 필요하므로 private로 선언합니다.

private fun makeSubExpr() {
        val op = opStack.pop()
        val operand1 = exprStack.pop()
        val operand2 = exprStack.pop()
        exprStack.push(op + operand2 + operand1)
}

private fun handleRemainingOperators() {
        while (opStack.isNotEmpty()) {
            makeSubExpr()
        }
}

 

연산자를 확인하기 위한 간단한 함수도 추가합니다. in 대신 함수 contains()를 사용해도 됩니다.

const val OP_LIST = "+-*/^"

private fun isOperator(op: Char): Boolean = op in OP_LIST // OP_LIST.contains(op)

 

사전 작업은 끝냈습니다. 우리가 수정해야 할 코드는 메소드 infixToPrefix()입니다. 프로그램을 모듈러하게 작성하면 전체 코드도 눈에 확 들어 와 코드 동작을 쉽게 파악할 수 있습니다. 이런 걸 코드 가독성(readability)이라고 합니다. 괄호를 처리하는 과정은 간단합니다. 열린 괄호( '(' )를 만나면, 열린 괄호와 쌍을 이루는 닫힌 괄호( ')' )를 만날 때까지 괄호안의 수식을 먼저 처리하면 됩니다. 괄호는 사용자가 임의로 연산 우선 순위를 부여하기 때문에 가장 우선 순위가 높습니다.

private fun processParenthesis() {
        while (opStack.isNotEmpty() && opStack.peek() != '(') {
            makeSubExpr()
        }
        opStack.pop()
}
    
fun infixToPrefix() {
        for (ch in infix) {
            if (ch == ' ') continue
            when {
                ch.isLetterOrDigit() -> exprStack.push(ch.toString())
                ch == '('       -> opStack.push(ch)
                ch == ')'       -> processParenthesis()
                isOperator(ch)  -> processOperators(ch)
            }
        }
        handleRemainingOperators()
        prefix = exprStack.peek()
 }

 

전체 코드를 볼까요. 코드 사이즈가 길어 앞에서 소개한 코드는 생략했습니다. 괄호를 포함한 중위 수식을 전위 수식으로 변환하고 수식 계산도 정확한 값을 출력하는 것을 알 수 있습니다.

import java.util.Stack
import kotlin.math.pow

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

class InfixExpression(val infix: String) {
    var prefix: String = ""
    private val opStack = Stack<Char>()
    private val exprStack = Stack<String>()

    private fun precedence(op: Char): Int { ... }
    private fun isOperator(op: Char): Boolean = op in OP_LIST

    private fun makeSubExpr() { ... }
    private fun processParenthesis() { ... }
    private fun processOperators(ch: Char) {
        while (opStack.isNotEmpty() &&
               precedence(ch) < precedence(opStack.peek())) {
            makeSubExpr()
        }
        opStack.push(ch)
    }

    private fun handleRemainingOperators() {
        while (opStack.isNotEmpty()) {
            makeSubExpr()
        }
    }

    private fun eval(op: Char, oprd1: Int, oprd2: Int) = ...
    
    fun infixToPrefix() { ... }
    fun evaluatePrefix(): Int { ... }
}

fun main() {
    val infix = "3+2*(4-6)"
    val evaluator = InfixExpression(infix)

    evaluator.infixToPrefix()
    println("prefix: ${evaluator.prefix}")
    val result = evaluator.evaluatePrefix()
    println("Result: $result")
}