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

문제

풀이

1. 스택에는 연산자만 담고 피 연산자는 바로 출력 문자열에 담는다.
2. '(' 괄호는 스택에 담는다.
3. ')' 괄호는 '(' 를 만날 때까지 pop한 연산자를 출력 문자열에 더한다.
4. '*', '/', '+', '-' 연산자는 스택의 우선 순위가 더 높거나 같으면 스택의 연산자를 출력 문자열에 먼저 더해주고 현재 연산자는 스택에 다시 넣는다. (스택에 들어간 연산자가 우선순위가 같다면 더 우선적으로 빠짐)
5. 모든 연산을 다하면 스택에 남아 있는 연산자를 출력 문자열에 더해준다.

정답 코드

package com.baekjoon.data_structure.p1918;

import java.util.*;

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

        String infix = sc.next();

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

        for (int i = 0; i < infix.length(); i++) {
            char now = infix.charAt(i);

            switch (now) {
                case '(':
                    stack.push(now);
                    break;
                case ')':
                    // '(' 연산자를 만날 때까지 빼준다.
                    while (!stack.isEmpty() && stack.peek() != '(') {
                        sb.append(stack.pop());
                    }
                    stack.pop(); // 마지막에 못뺏던 '(' 연산자를 빼주기
                    break;
                case '*':
                case '/':
                case '+':
                case '-':
                    /*
                     * 스택에 있는 연산자 우선순위가 높다면 스택에서 먼저 뽑아 넣어준다.
                     * 우선순위가 같다면 스택 안에 먼저 들어있는 연산자 먼저 꺼내어 문자열에 더해준다.
                     */
                    while (!stack.isEmpty() && priority(stack.peek()) >= priority(now)) {
                        sb.append(stack.pop());
                    }
                    stack.push(now);
                    break;
                default:
                    sb.append(now);
            }
        }

        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }

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

    /*
     * 연산자 우선 순위를 계산하는 메서드
     * 이 부분을 생각하지 못해서 진행이 안되었다.
     */
    static int priority(char operator) {

        if (operator == '+' || operator == '-') {
            return 1;
        } else if (operator == '*' || operator == '/') {
            return 2;
        }

        return 0;
    }
}