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

인간몽쉘김통통·2024년 1월 9일

백준 스택 알고리즘 자료구조

백준

목록 보기

45/92

문제

이해

후위 표기식은 일반적인 중위 표기식과 다르게 연산자가 피연산자들의 뒤에 붙는 표기식이다.

문제에서는 후위 표기식으로 변환하려면 우선순위에 따라 괄호로 묶어준 뒤 괄호의 순서대로 연산자를 괄호 바깥으로 꺼내 식을 작성한다고 설명한다.

중위 표기식으로 되어있는 식을 입력받아 후위 표기식으로 출력하라.

접근

후위 표기식은 연산자 우선순위에 따른 처리를 스택을 활용하여 하면 된다.

후위 표기식은 정의에 따라 피연산자들이 우선적으로 출력된다. 피연산자가 출력되면 연산자가 출력되는데 이는 우선순위에 따라 달라진다.

A + B * C

A * B + C

두 예제를 보자.

1번 예제의 출력 흐름을 보면
A -> AB -> ABC -> ABC -> ABC+ 이다.

A와 B라는 피연산자를 출력한 뒤 연산자가 바로 붙지 않은 이유는 +가 * 보다 우선순위가 낮기 때문이다.

그렇다면 반대의 경우를 보자.

2번 예제의 출력 흐름을 보면

A -> AB -> AB -> ABC -> AB*C+ 이다.

마찬가지로 * 가 +보다 우선순위가 높기 때문에 우선적으로 출력됐다.

이는 스택을 통해 구현할 수 있다. 연산자의 출력 여부를 검사할 때 만일 스택의 peek() 연산자가 우선순위가 더 높다면 pop()을 통해 꺼내고 출력한다. 반대로 peek() 연산자가 우선순위가 더 낮다면 출력되지 못해 그대로 존재하며 현재 연산자를 add() 한다.

그렇다면 괄호의 처리는 어떻게 하면 될까? 괄호는 * 보다 우선순위가 높다.

식에는 항상 '(', ')' 쌍의 괄호가 존재하는데 이 둘은 분리해서 생각해야 한다.

( 의 경우 괄호를 연다는 의미이므로 스택에 추가한다. 이 때, ( 는 누구보다도 우선순위가 높기 때문에 추가하면 된다.

) 의 경우에는 괄호를 닫는다는 의미이므로 괄호 안에 포함되었던 모든 연산자를 출력해야 할 필요가 있다.

괄호 안을 검사하는 동안 스택에는 괄호 안 연산자들이 우선순위에 따라 저장되어 있다. 따라서, 다시 ( 가 나올때까지 모두 꺼내서 출력하면 된다.

여기까지 후위 표기식의 알고리즘이다.

중요한 포인트는 스택의 활용, 우선순위를 통한 분기 설정이다.

코드

package java_baekjoon;

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

public class prob1918 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();

        System.out.println(PostFix(s));
    }

    static String PostFix(String s) {
        int length = s.length();
        Stack<Character> stck = new Stack<>();
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < length; i++) {
            char c = s.charAt(i);

            switch (c) {
                case '+':
                case '-':
                case '*':
                case '/':
                    while (!stck.isEmpty() && priority(stck.peek()) >= priority(c)) {
                        sb.append(stck.pop());
                    }
                    stck.add(c);
                    break;
                case '(':
                    stck.add(c);
                    break;
                case ')':
                    while (!stck.isEmpty() && stck.peek() != '(') {
                        sb.append(stck.pop());
                    }
                    stck.pop();
                    break;
                default:
                    sb.append(c);
            }
        }
        while(!stck.isEmpty()){
            sb.append(stck.pop());
        }

        return sb.toString();
    }

    static int priority(char operator) {
        if (operator == '(' || operator == ')') {
            return 0;
        } else if (operator == '+' || operator == '-') {
            return 1;
        } else if (operator == '*' || operator == '/') {
            return 2;
        }
        return -1;
    }
}