백준 1918번: 후위 표기식

문제: https://www.acmicpc.net/problem/1918

문제 풀이

스택

stack = 연산자를 저장할 스택으로 사용할 배열

top = 스택에 마지막으로 들어온 연산자가 저장된 인덱스, 스택이 비었으면 -1

피연산자가 들어오면 바로 출력, 연산자는 우선순위에 따라 스택에서 현재 연산자와 우선순위가 크거나 같은 모든 연산자를 출력하고 현재 연산자를 스택에 넣음

괄호의 경우 여는 괄호는 스택에 넣으면 되고 닫는 괄호는 스택에서 여는 괄호가 나올때까지 연산자를 출력하고 여는 괄호를 스택에서 제거하면 됨

이에 따라 후위 표현식으로 출력하면 정답

풀이 설명

수식은 일반적으로 3가지 표기법으로 표현할 수 있다. 연산자가 피연산자 가운데 위치하는 중위 표기법(일반적으로 우리가 쓰는 방법이다), 연산자가 피연산자 앞에 위치하는 전위 표기법(prefix notation), 연산자가 피연산자 뒤에 위치하는 후위 표기법(postfix notation)이 그것이다. 예를 들어 중위 표기법으로 표현된 a+b는 전위 표기법으로는 +ab이고, 후위 표기법으로는 ab+가 된다.

중위 표기식을 후위 표기식으로 바꾸는 방법을 간단히 설명하면 이렇다. 우선 주어진 중위 표기식을 연산자의 우선순위에 따라 괄호로 묶어준다. 그런 다음에 괄호 안의 연산자를 괄호의 오른쪽으로 옮겨주면 된다. 중위 표기식이 주어졌을 때 후위 표기식으로 고치는 프로그램을 작성하시오.

후위 표기식은 연산자를 연산해야 하는 두 피연산자 뒤에 두는 방식이므로 이에 따라 연산자를 우선순위에 맞게 쓰려면 뒤에 오는 연산자가 더 우선순위가 높을 수 있기 때문에 연산자를 저장해놓을 공간이 필요하다.

이에 따라 스택을 이용해서 마지막으로 저장된 연산자와 현재 입력된 연산자의 우선순위를 비교해 연산자를 출력하면 된다. 스택은 간단하게 배열과 현재 스택의 인덱스를 정의하면 된다.

연산자의 우선순위는 곱셈, 나눗셈이 덧셈, 뺄셈보다 먼저 계산되기 때문에 나중에 나와도 출력은 먼저 되어야 한다. 그러므로 곱셈, 나눗셈이 덧셈, 뺄셈보다 우선순위가 높게 되고 이에 따라 출력할때도 스택에 저장된 연산자의 우선순위가 더 높거나 같다면 저장된 연산자가 먼저 출력되어야 하므로 스택에서 우선순위가 높거나 같은 모든 연산자를 먼저 출력해야 한다.

여기서 괄호의 경우는 얘기가 좀 달라지는데 괄호 내의 식을 먼저 계산해야 하는 것이므로 괄호로 쌓인 식을 별도의 식으로 생각해 이 괄호 내의 식을 바로 후위 표기식으로 출력해야 한다. 그러므로 여는 괄호를 스택에 집어넣고 그 뒤에 연산자를 우선순위에 맞게 저장 및 출력을 하다가 닫힌 괄호가 나오면 여는 괄호가 나올때까지 저장된 연산자를 모두 출력해야 한다.

이 조건들에 맞게 중위 표현식을 하나하나 읽으면서 피연산자는 바로 출력하고 연산자는 스택에 저장 및 출력을 하면 후위 표현식에 맞게 식이 출력되므로 정답이 된다.

소스 코드

fun main(){
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()
    val infix = br.readLine()
    val stack = CharArray(infix.length)
    var top = -1
    for(c in infix){
        if(c in 'A'..'Z'){
            bw.append(c)
        } else {
            if(c == '+' || c == '-'){
                if(top >= 0){
                    while(top >= 0 && stack[top] != '('){
                        bw.append(stack[top--])
                    }
                }
                stack[++top] = c
            } else if(c == '*' || c == '/'){
                if(top >= 0){
                    while(top >= 0 && (stack[top] == '*' || stack[top] == '/')){
                        bw.append(stack[top--])
                    }
                }
                stack[++top] = c
            } else if(c == '('){
                stack[++top] = c
            } else {
                while(top >= 0 && stack[top] != '('){
                    bw.append(stack[top--])
                }
                top--
            }
        }
    }
    while(top >= 0){
        bw.append(stack[top--])
    }
    bw.flush()
    bw.close()
}