코틀린: infix expression을 prefix expression으로 변환(3/5) - 람다 식

앞에서 작성한 코드는 함수를 사용하지 않았습니다. 아래 코드는 함수 processOperators와 handleRemainingOperator를 정의하여 전체 코드를 수정했습니다. 이렇게 함수를 사용해 프로그램하는 것을 모듈러(modular) 프로그래밍이라 부릅니다. 괄호가 포함된 중위 표기법을 다룰 때, 즉 간단한 프로그램에서 기능을 추가해가며 복잡한 프로그램을 만들 때 이러한 모듈러 프로그래밍 방식이 효과적입니다.

import java.util.*

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

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

fun processOperators(ch: Char, operators: Stack<Char>, expr: Stack<String>) {
    while (operators.isNotEmpty() &&
           precedence(ch) < precedence(operators.peek())) {
        makeSubExpr(operators, expr)
    }
    operators.push(ch)
}

fun handleRemainingOperators(operators: Stack<Char>, expr: Stack<String>) {
    while (operators.isNotEmpty()) {
        makeSubExpr(operators, expr)
    }
}

fun infixToPrefix(infix: String): String {
    val opStack = Stack<Char>()
    val expStack = Stack<String>()

    for (ch in infix) {
        if (ch.isWhitespace()) continue
        if (ch.isLetterOrDigit()) {
            expStack.push(ch.toString())
        }
        else if (isOperator(ch)) {
            processOperators(ch, opStack, expStack)
        }
    }
    handleRemainingOperators(opStack, expStack)
    return expStack.peek()
}

fun main() { ... }

 

함수를 사용한 코드를 람다 식(lambda expression)을 사용한 코드로 쉽게 바꿀 수 있습니다. 람다 식에 관한 자세한 내용은 쉽게 다가가는 최신 프로그래밍: 코틀린- 3.3. 람다식 기초을 참고하기 바랍니다. 함수와 람다 식의 차이점은 람다 식에서는 형식 인자가 람다 식 블록에 선언된다는 점입니다. 이를 제외하면 함수 블록이나 람다 식 블록에서 실행하는 내용은 같습니다.

import java.util.*

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

val isOperator:(Char) -> Boolean = { it in OP_LIST }
val makeSubExpr:(Stack<Char>, Stack<String>) -> Unit = { op, exp ->
    val op = op.pop()
    val operand1 = exp.pop()
    val operand2 = exp.pop()
    exp.push(op + operand2 + operand1)
}

val precedence: (Char) -> Int = { ch ->
    when (ch) {
        '+', '-' -> Precedence.LOW.priority
        '*', '/' -> Precedence.MEDIUM.priority
        '^' ->      Precedence.HIGH.priority
        else ->     Precedence.NONE.priority
    }
}

val processOperators: (Char, Stack<Char>, Stack<String>) -> Unit = { ch, operators, expr ->
    while (operators.isNotEmpty() &&
        precedence(ch) < precedence(operators.peek())) {
        makeSubExpr(operators, expr)
    }
    operators.push(ch)
}

val handleRemainingOperators: (Stack<Char>, Stack<String>) -> Unit = { operators, expr ->
    while (operators.isNotEmpty()) {
        makeSubExpr(operators, expr)
    }
}

fun infixToPrefix(infix: String): String { ... }
fun main() { ... }

 

중위 표기법을 전위 표기법으로 바꿨다고 모든 게 끝난 건 아니죠. 중위 표기법이든 전위 표기법이든 수식(expression)이기 때문에 수식을 계산해 값을 구해야 합니다. 2개의 함수(eval, evaluatePrefix)를 추가했습니다. 코드를 간단히 하기 위해 피연산자는 0~9 사이의 값만을 갖으며, Int 타입으로 선언했습니다. 함수 evaluatePrefix에서 가장 중요한 부분은 reversed() 함수를 사용해  전위 표기법의 역순으로 수식을 계산하는 것입니다. 

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

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

val isOperator:(Char) -> Boolean = { it in OP_LIST }
val precedence: (Char) -> Int = { ... }
val makeSubExpr:(Stack<Char>, Stack<String>) -> Unit = { ... }
val handleOperator: (Char, Stack<Char>, Stack<String>) -> Unit = { ... }
val processRemainingOperators: (Stack<Char>, Stack<String>) -> Unit = { ... }

fun infixToPrefix(infix: String): String { ... }

fun eval(op: Char, oprd1: Int, oprd2: Int) =
    when (op) {
        '+' -> oprd1 + oprd2
        '-' -> oprd1 - oprd2
        '*' -> oprd1 * oprd2
        '/' -> oprd1 / oprd2
        '^' -> oprd1.toDouble().pow(oprd2.toDouble()).toInt()
        else -> 0
    }

fun evaluatePrefix(prefix: String): Int {
    val evalStack = Stack<Int>()
    for (ch in prefix.reversed()) {
        if (ch.isDigit()) {
            evalStack.push(ch.toString().toInt())
        } else {
            val operand1 = evalStack.pop()
            val operand2 = evalStack.pop()
            val result = eval(ch, operand1, operand2)
            evalStack.push(result)
        }
    }
    return evalStack.pop()
}

fun main() {
    val infix = "3 + 2 * 5"
    val prefix = infixToPrefix(infix)
    val result = evaluatePrefix(prefix)
    println("prefix = $result")
}