BOJ 1918 후위표기식 - 스택

문제

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

이 문제에서 우리가 다룰 표기법은 후위 표기법이다. 후위 표기법은 위에서 말한 법과 같이 연산자가 피연산자 뒤에 위치하는 방법이다. 이 방법의 장점은 다음과 같다. 우리가 흔히 쓰는 중위 표기식 같은 경우에는 덧셈과 곱셈의 우선순위에 차이가 있어 왼쪽부터 차례로 계산할 수 없지만 후위 표기식을 사용하면 순서를 적절히 조절하여 순서를 정해줄 수 있다. 또한 같은 방법으로 괄호 등도 필요 없게 된다. 예를 들어 a+b*c를 후위 표기식으로 바꾸면 abc*+가 된다.

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

예를 들어 a+b*c는 (a+(b*c))의 식과 같게 된다. 그 다음에 안에 있는 괄호의 연산자 *를 괄호 밖으로 꺼내게 되면 (a+bc*)가 된다. 마지막으로 또 +를 괄호의 오른쪽으로 고치면 abc*+가 되게 된다.

다른 예를 들어 그림으로 표현하면 A+B*C-D/E를 완전하게 괄호로 묶고 연산자를 이동시킬 장소를 표시하면 다음과 같이 된다.

이러한 사실을 알고 중위 표기식이 주어졌을 때 후위 표기식으로 고치는 프로그램을 작성하시오

입력

첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식은 주어지지 않는다. 표기식은 알파벳 대문자와 +, -, *, /, (, )로만 이루어져 있으며, 길이는 100을 넘지 않는다. 

출력

첫째 줄에 후위 표기식으로 바뀐 식을 출력하시오

예제 입력 1 복사

A*(B+C)

예제 출력 1 복사

ABC+*

---

해설

이 문제를 처음 접할 때가 아마도 자료구조를 처음 배웠을 때이었을 것이다. 그 때는 문제를 풀 지 못했는데, 이번엔 어떻게든 꾸역꾸역 문제를 풀어냈다.

 

사고의 흐름

문제에도 나와있는 데, 우선순위에 따라 괄호를 씌워주고, 이에 맞춰 연산자를 꺼내면 된다했다.
즉 이 문제는 연산자에 우선순위를 부여하고 이에 맞춰 해결하면 되는 문제이다.
연산자가 언제 후위로 나오는 지를 살펴보면, 연산자 우선 순위가 낮거나 같은 연산자가 다음에 나오게 되면, 연산자를 밖으로 빼주게 된다.
이에 맞춰 소스코드를 작성해 보자.

 

import java.io.*;
import java.util.Stack;


public class Main {
    public static int priority(char c){
        if(c == '(') return 0;
        else if(c == '+' || c == '-') return 1;
        else return 2;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter wr = new BufferedWriter(new OutputStreamWriter(System.out));
        char[] input = br.readLine().toCharArray();
        Stack<Character> stack = new Stack<>();
        for(int i = 0; i < input.length; i++){
            char c = input[i];
            if('A' <= c && c <= 'Z'){
                wr.write(c);
            } else if(stack.isEmpty()) stack.push(c);
            else {
                if(c == ')'){
                    while(!stack.isEmpty()){
                        char s = stack.pop();
                        if(s == '(')
                            break;
                        else wr.write(s);
                    }
                } else if(c == '*' || c == '/'){
                    if(priority(stack.peek()) < priority(c)){
                        stack.push(c);
                    } else {
                        while(!stack.isEmpty() && priority(stack.peek()) >= priority(c))
                            wr.write(stack.pop());
                        stack.push(c);
                    }
                } else{
                    if(c != '(' && priority(stack.peek()) >= priority(c))
                        while(!stack.isEmpty() && priority(stack.peek()) >= priority(c))
                            wr.write(stack.pop());
                    stack.push(c);
                }
            }
        }
        while(!stack.isEmpty())
            wr.write(stack.pop());

        wr.flush();
    }
}

 

이렇게 문제를 풀고나니, 식을 다시 한 번 정리하고 싶어졌다. 뭔가 어떻게든 답에 코드를 맞춰 짠 기분이라, 내가 이해할 수 있게 다시 코드륵 작성하고 싶었다.

 

import java.io.*;
import java.util.Stack;


public class Main {
    public static int priority(char c){
        if(c == '(') return 0;
        else if(c == '+' || c == '-') return 1;
        else return 2;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter wr = new BufferedWriter(new OutputStreamWriter(System.out));
        char[] input = br.readLine().toCharArray();
        Stack<Character> stack = new Stack<>();
        for(int i = 0; i < input.length; i++){
            char c = input[i];
            if('A' <= c && c <= 'Z'){
                wr.write(c);
            } else if(c == '(') {
                stack.push(c);
            } else if(c == ')'){
                while(!stack.isEmpty()){
                    char s = stack.pop();
                    if(s == '(')
                        break;
                    wr.write(s);
                }
            } else {
                while(!stack.isEmpty() && priority(stack.peek()) >= priority(c))
                    wr.write(stack.pop());
                stack.push(c);
            }
        }
        while(!stack.isEmpty())
            wr.write(stack.pop());

        wr.flush();
    }
}

 

아래 두 if문의 내용이 똑같다는 것을 알 수 있다. 이를 하나로 줄여서 작성하니 확실히 깔끔하게 해결됐다.

 

느낀 점

• 스택 문제 유형 중 조금 어려운 문제를 만나, 하루종일 고민을 했다. 그래도 자료구조의 특성을 잘 생각하여 흐름을 잘 따라가면 문제를 풀어낼 수 있을 것 같다. 자신감을 갖자!!