[6개월 안에 백준 플래티넘 달성하기] 14. 후위 표기식 1918

후위 표기식

 

문제

 

풀이

처음 문제를 보았을 때는 굉장히 막막하였는데 예전 괄호 문제를 스택을 이용하여 푼 기억 덕분에 뭔가 비슷하게 스택에 연산자를 넣었다가 빼주면 될 거 같았습니다.

 

해당 문제도 비슷하게 스택을 이용하여 풀 수 있습니다. 아이디어는 다음과 같습니다.

1. 피연산자는 따로 담아두고 연산자만 스택에 담아준다.
2. 스택에 있는 연산자와 현재의 연산자를 비교하여 스택에 넣을지 말지를 결정한다.

 

이제 2번의 비교에 대한 경우를 신경 써주면 됩니다. 경우의 수는 총 3가지가 있습니다.

1. 스택에 있는 연산자보다 우선순위가 낮은 연산자가 들어오는 경우
2. 스택에 있는 연산자와 우선순위가 동일한 연산자가 들어오는 경우
3. 스택에 있는 연산자보다 우선순위가 높은 연산자가 들어오는 경우

 

각 상황별 예시와 처리 방법입니다.

1. A*B+C -> AB*C+  // 우선순위가 낮은 연산자가 들어오면 그보다 큰 우선순위를 가진 연산자를 스택에서 빼서 붙임
2. A/B/C -> AB/C/  // 우선순위가 같은 연산자가 들어오면 같은 우선순위를 가진 연산자를 스택에서 빼서 붙임
3. A+B*C -> ABC*+  // 우선순위가 높은 연산자가 들어오면 그냥 스택에 넣음

 

결국에는 스택에 있는 연산자보다 우선순위가 낮거나 같을 경우에는 스택에서 연산자를 빼주고 

스택에 있는 연산자보다 우선순위가 높을 경우에는 그냥 스택에 넣어주면 됩니다.

 

[주의점]
A+B+C 는 ABC++가 아닌 AB+B+ 입니다.
덧셈에서는 가능하지만 그 외 연산자의 경우 연산자의 순서에 따라 값이 달라집니다. 이러한 이유 때문에 동일 연산자인 경우에도 스택에서 빼줍니다.
A-B-C != A-(B-C)

 

 

저는 이러한 우선순위를 level 변수로 해결해 주었습니다.

+, - 인 경우 0 

*, / 인 경우 1

 

추가적으로 괄호인 경우에는

( 인 경우 +100

) 인 경우  -100

로 순서와 상관없이 무조건 우선순위를 가져야 되기 때문에 큰 수로 지정해 주었습니다. (문제에서의 식의 최대 길이=100)

 

 

코드로 보면 더 쉽게 이해가 되실 겁니다.

import java.util.Stack

fun main() = with(System.`in`.bufferedReader()){
    val str = readLine()
    
    data class Node(val num: Char, var level: Int) // 연산자, 우선순위
    val stack = Stack<Node>()
    val sb = StringBuilder()

    var level = 0

    for(c in str) {
        if (c == '+' || c == '-') {
            if (stack.isEmpty()) stack.add(Node(c, level))
            else {
                // 스택에 우선순위가 더 높거나 같은 연산자가 있을 경우
                while (stack.isNotEmpty() && stack.peek().level >= level) {
                    sb.append(stack.pop().num)
                }
                
                stack.add(Node(c, level))
            }
        } else if (c == '*' || c == '/') {
            if (stack.isEmpty()) stack.add(Node(c, level+1))
            else {
                // 스택에 우선순위가 더 높거나 같은 연산자가 있을 경우
                while (stack.isNotEmpty() && stack.peek().level >= level+1) {
                    sb.append(stack.pop().num)
                }
                
                stack.add(Node(c, level+1))
            }
        } else if (c == '(') {
            level+=100
        } else if (c == ')') {
            level-=100
        } else {
            sb.append(c)
        }

    }
    
    // 스택에 남아있는 연산자 붙여줌
    while (stack.isNotEmpty()) {
        sb.append(stack.pop().num)
    }
    print(sb.toString())
}