백준 1918 - 후위 표기식

문제

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

리뷰

스택을 활용하여 풀이할 수 있는 대표적인 문제였다.
우선 스택에는 연산자만을 조건에 따라 push/pop 하며 피연산자는
그대로 출력한다.
문자에 따른 로직의 구성은 다음과 같다.

• ( : 그대로 push 한다.
• ) : 스택에서 (를 마주할 때까지 모든 연산자를 pop하여 출력한다.
• + , - , * , /
  괄호를 제외하고 우선순위에 따라 스택에 연산자를 배치해야 하기
  때문에 현재 stack 의 peek 보다 우선순위가 낮은 연산자가
  스택에 들어오려할 경우, 스택 내에서 해당 연산자보다 우선순위가 높거나
  같은 모든 연산자를 pop 하여 출력한다.

문제를 풀이하며 유의할 부분은 ( 의 우선순위를 설정하는 부분이었다.
당연하게도 ( 는 ) 를 처리하기 위해 스택에 존재하므로 우선순위를
가장 낮게 설정해주어야 한다.

주어지는 중위식 문자열의 길이가 최대 100이고 stack 과 관련된
삽입/삭제 연산은 모두 $O(1)$이므로 로직의 시간복잡도는 제한 조건인
2초를 여유 있게 통과할 수 있었다.

코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String infix = in.nextLine();

        StringBuilder sb = new StringBuilder();
        Stack<Character> operators = new Stack<>();

        for (int i = 0; i < infix.length(); i++) { //O(n)
            Character c = infix.charAt(i);

            //스택 삽입/삭제 연산 O(1)
            switch (c) {
                case '(':
                    operators.push(c);
                    break;

                case ')':
                    while (!operators.peek().equals('('))
                        sb.append(operators.pop());
                    operators.pop();
                    break;

                case '+':
                case '-':
                case '*':
                case '/':
                    int priority1 = getPriority(c);

                    while (!operators.isEmpty() &&
                            getPriority(operators.peek()) >= priority1) {
                        sb.append(operators.pop());
                    }

                    operators.push(c);
                    break;

                default:
                    sb.append(c);
            }
        }

        while (!operators.isEmpty())
            sb.append(operators.pop());

        System.out.println(sb);
        in.close();
    }

    private static int getPriority(Character operator) {
        switch (operator) {
            case '+':
            case '-':
                return 1;
            case '*':
            case '/':
                return 2;
        }

        return -1;
    }
}

결과