[백준] 1918번 : 후위 표기식 (Kotlin)

1918번: 후위 표기식

나의 풀이

import java.lang.StringBuilder
import java.util.Stack

fun main() {
    val str = readLine()!!
    val sb = StringBuilder()
    val stack = Stack<Char>()

    str.forEach {
        // 알파벳의 경우 바로 문자열에 추가
        if (it in 'A'..'Z') {
            sb.append(it)
        } else {
            // 연산자의 경우
            when (it) {
                // +, -는 괄호 밖이라면 가장 우선순위가 낮음
                // 괄호를 제외한 스택에 쌓여있는 모든 연산자 제거 후 스택에 추가
                '+', '-' -> {
                    while (stack.isNotEmpty() && stack.peek() != '(') {
                        sb.append(stack.pop())
                    }
                    stack.push(it)
                }
                // *, /는 +, -보다 우선순위가 높기 때문에 스택의 *, /제거 후 +, -위에 추가
                '*', '/' -> {
                    while (stack.isNotEmpty() && stack.peek() != '(' && stack.peek() != '-' && stack.peek() != '+') {
                        sb.append(stack.pop())
                    }
                    stack.push(it)
                }
                // 스택에 괄호 추가 -> 괄호 내부
                '(' -> {
                    stack.push(it)
                }
                // 닫는 괄호라면 괄호 내부 연산 문자열에 추가
                ')' -> {
                    while (stack.isNotEmpty() && stack.peek() != '(') {
                        sb.append(stack.pop())
                    }
                    if (stack.isNotEmpty() && stack.peek() == '(') {
                        stack.pop()
                    }
                }
            }
        }
    }
    // 스택에 남아있는 연산자 제거
    while (stack.isNotEmpty()) {
        sb.append(stack.pop())
    }

    println(sb)
}

☞ 괄호가 포함된 중위 표기식을 후위 표기식으로 표현하는 문제입니다.

1. 피연산자인 알파벳은 최종적으로 출력할 StringBuilder(sb)에 바로 추가합니다.

2. 연산자와 괄호는 스택에 추가하되 연산자의 우선순위(*, /가 +, -보다 우선)를 생각하며 +, -가 입력될 경우 스택을 한번 비워주며 쌓여있던 연산자를 sb에 추가합니다. 

3. '(' 는 스택에 추가하지만 ')' 는 '(' 전까지 모든 연산을 제거해 sb에 추가합니다.

4. 중위 표기식의 모든 검사가 끝났다면 스택에 남아있는 연산자를 제거해 sb에 추가해 줍니다.

 

cf. 처음에는 괄호 내부/외부를 따로 처리해줘야 하나 싶어 고민이 많았던 문제입니다. 크게 괄호 내부/외부를 구분하지 않고 ')' 의 입력이 들어왔을 때에만 괄호 내부의 연산을 수행해 미리 StringBuilder에 추가하는 방식으로 해결했습니다.