쉽게 다가가는 최신 프로그래밍: 코틀린 - 2.2 연산자 오버로딩에서 연산자 오버로딩은 중위 표기법(infix notation)을 사용합니다. 3.6.6 중위 함수 역시 중위 표기법을 사용합니다. 수식 2 + 3 처럼 연산자(operator)가 피연산자(operand) 가운데에 놓이는 표기법을 중위 표기법이라고 합니다. 기계어 코드(machine code)에서는 + 2 3 처럼 연산자가 앞에 오는 전위 표기법(prefix notation)을 사용합니다. 전위 표기법을 폴란드 표기법(polish notation, PN)이라 부릅니다. 2 3 +처럼 연산자가 마지막에 오는 표기법을 후위 표기법(postfix notation)이라 부릅니다. 후위 표기법을 RPN(reverse polish notation)이라 부릅니다.
전위 표기법이 재미있는 점은 연산자 개수가 고정이면, 수식에 괄호를 사용할 필요가 없다는 점입니다. 또 한 가지, 프로그래밍 언어의 컴파일러를 구현할 때 구문 트리(syntax tree)를 탐색하며 중간 코드를 생성할 수 있는데, 트리 탐색 과정에서 수식은 전위(또는 후위) 표기법으로 자연스럽게 바뀝니다. 구문 트리에서 부모 노드가 연산자이며, 자식 노드가 피연산자이기 때문입니다. 구문 트리를 탐색하는 방식에 따라 전위 표기법 또는 후위 표기법으로 나타낼 수 있습니다. 자세한 내용은 4.8 응용: 탐색 알고리즘을 참고하기 바랍니다.
상위 레벨(high-level)에서 프로그래밍 언어는 중위 표기법을 사용하지만, 하위 레벨(low-level)에서는 전위 표기법을 사용합니다. 여기서는 전위 표기법을 사용한 수식 계산을 다루려고 합니다. 전위 표기법 또는 후위 표기법을 다룰 때는 자료 구조 스택(Stack)을 사용하는 것이 찰떡 궁합입니다.
스택 동작은 간단합니다. 관련 함수도 push, pop, peek 3가지 뿐입니다. push는 원소를 삽입할 때, pop은 원소를 꺼낼 때, 그리고 peek는 스택의 꼭대기(top)에 놓인 원소를 참조할 때 사용합니다. 1, 2, 3을 차례대로 스택에 삽입하려면 3번의 push가 필요합니다. push(1), push(2), push(3) 입니다. 스택에서 원소를 꺼낼 때는 가장 마지막에 삽입한 원소부터 가져옵니다. pop()하면 원소 3을 가져옵니다. push(1)는 실인자가 필요하지만, pop()은 인자가 없습니다. 스택을 가장 효과적으로 이해할 수 있는 예제인 중위 표기법을 전위 표기법으로 변환하는 예제를 살펴보겠습니다.
여기서 연산자는 피연산자가 2개인 이항 연산자(binary operator)로 제한합니다. 코드를 간단히 하기 위해 연산자 뿐 아니라 피연산자도 숫자가 아닌 문자(Char)로 통일합니다. 또 이진 트리(binary tree)를 사용하는 방법도 있지만, 초점이 Stack에서 트리로 옮겨가기 때문에 트리 대신 문자열 처리 방식을 사용합니다.
중위 수식 a + b * c 를 전위 수식으로 바꾸면 + a * b c 입니다. 왜 그럴까요? a + b * c 는 연산자 우선순위에 따라 a + (b * c) 처럼 곱셈을 먼저 계산하기 때문입니다. 중위 수식은 연산자 우선순위가 필요하며, 전위 수식으로 변환할 때 이를 반영해야 합니다. enum 클래스 Precedence를 아래처럼 선언하고, 연산자의 우선순위(Int 값)를 반환하는 함수 precedence()를 정의합니다.
enum class Precedence (val priority: Int) {
NONE(-1), LOW(1), MEDIUM(2), HIGH(3)
}
fun precedence(op: Char): Int {
return when (op) {
'+', '-' -> Precedence.LOW.priority
'*', '/' -> Precedence.MEDIUM.priority
'^' -> Precedence.HIGH.priority
else -> Precedence.NONE.priority
}
}
함수 infixToPrefix()는 중위 수식(infix)을 전위 수식(prefix)으로 변환하는 함수입니다. 변수 연산자(operators)와 수식(expr)을 Stack 타입으로 선언했습니다. for 루프에서 수식(infix)의 원소(ch)가 숫자나 알파벳이면 피연산자이므로 스택 expr에 삽입합니다. 원소(ch)가 연산자이면, 스택 operators의 꼭대기(top)에 저장된 연산자(operators.peek())와 ch의 우선순위를 비교합니다. ch가 우선순위가 낮으면, operators 스택에 저장된 연산자와 expr 스택에 저장된 2개의 피연산자를 꺼내 수식으로 만들어 expr 스택에 삽입합니다. 스택에서 꺼낸 피연산자 순서와 반대로(op + operand2 + operand1) 수식을 만듭니다. String 타입 변수끼리 + 연산은 연결(concatenation) 연산입니다. "Hello, " + "World!" 는 "Hello, World!"입니다.
for 루프 다음에 있는 while 루프에서는 operators 스택에 남은 연산자에 대한 피연산자를 expr 스택에서 꺼내 전위수식으로 변환합니다. expr 스택의 꼭대기(top)에 놓인 수식이 중위 표기법을 전위 표기법으로 변환한 수식입니다.
const val OP_LIST = "+-*/^"
fun isOperator(op: Char): Boolean = op in OP_LIST
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)
}
fun infixToPrefix(infix: String): String {
val operators = Stack<Char>()
val expr = Stack<String>()
for (ch in infix) {
if (ch.isWhitespace()) continue
if (ch.isLetterOrDigit()) {
expr.push(ch.toString())
}
else if (isOperator(ch)) {
while (operators.isNotEmpty() &&
precedence(ch) <= precedence(operators.peek())) {
makeSubExpr(operators, expr)
println("In the while loop inside the for loop: expr = ${expr.peek()}")
}
operators.push(ch)
println("in the for loop : operators = ${operators.peek()}")
}
}
while (operators.isNotEmpty()) {
makeSubExpr(operators, expr)
println("In the while loop: expr = ${expr.peek()}")
}
return expr.peek()
}
함수 중간에 삽입한 println()을 출력한 실행 결과입니다. 중위 수식 infix는 "a + b * c "입니다.
완성된 전체 코드입니다. Stack은 자바에서 제공하는 자료 구조입니다. 아주 간단한 예제를 갖고 전체 코드 흐름을 파악하는 게 중요합니다. 자신감이 붙었으면, infix = "a + b * c - d / e"로 바꿔서 실행해 보세요. 다음 단계 주제는 괄호가 포함된 중위 수식을 전위 수식으로 변환하는 예제입니다.
import java.util.Stack
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: Stack<Char>, exp: Stack<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")
}
'코틀린' 카테고리의 다른 글
코틀린: infix expression을 prefix expression으로 변환(3/5) - 람다 식 (0) | 2025.01.09 |
---|---|
코틀린: infix expression을 prefix expression으로 변환(2/5) - List 구현 (0) | 2025.01.09 |
코틀린: 5장 테스트에 도전해 보세요 (정답 해설) (0) | 2025.01.09 |
코틀린: 5장 테스트에 도전해 보세요 (0) | 2025.01.09 |
코틀린: 시퀀스(Sequence)와 컬렉션(Collection)은 뭐가 다를까요? (0) | 2025.01.09 |