[BOJ] 1918번 후위표기식 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        String s = br.readLine();
        Stack<Character> stack = new Stack<>();

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

            if (c == '(') {
                stack.push(c);
            } else if (c == ')') {
                while (!stack.isEmpty()) {
                    if (stack.peek() == '(') {
                        stack.pop();
                        break;
                    }
                    sb.append(stack.pop());
                }
            } else if (c == '*' || c == '/' || c == '+' || c == '-') {
                while (!stack.isEmpty()) {
                    if (getPriority(stack.peek()) > getPriority(c)) {
                        break;
                    }
                    sb.append(stack.pop());
                }
                stack.push(c);
            } else {
                sb.append(c);
            }
        }

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

        System.out.println(sb);
    }

    private static int getPriority(char op) {
        if (op == '(' || op == ')') {
            return 3;
        } else if (op == '*' || op == '/') {
            return 1;
        } else if (op == '+' || op == '-') {
            return 2;
        }
        return -1;
    }
}

📄 해설

접근

• Character 타입의 스택을 사용하여 해결하는 문제이다.
• 피연산자는 바로 출력하고, 여는 괄호는 스택에 넣고 닫는 괄호를 만나면 여는 괄호를 찾을 때까지 모든 원소를 출력한다.
• 연산자의 경우도 스택에 추가한다. 이때, 스택의 탑이 현재 연산자보다 높은 우선순위를 가진다면 스택이 빌때까지 전부 다 출력한다.
• 문자열 순회 끝나고 난 다음에 마지막에 추가된 연산자가 있을 수 있으니 한번 더 스택이 빌때까지 전부 다 출력한다.

과정

• Character 타입의 스택을 하나 선언하고, 입력 받은 문자열을 순회한다.
• 여는 괄호를 만난 경우, 스택에 추가한다.
• 닫는 괄호를 만난 경우, 스택이 빌때까지 스택의 모든 원소를 출력한다. 이때, 여는 괄호를 만나면 반복을 종료한다ㅏ.
• 연산자의 경우, 스택의 탑이 현재 연산자보다 높은 우선순위를 가진다면 스택이 빌 때까지 출력한다. 낮은 우선순위라면 반복을 종료한다. 현재 연산자를 스택에 넣는다.
• 피연산자의 경우는 그냥 바로 출력한다.
• 문자열 순회가 끝난 후에 남아있는 연산자가 존재할 수 있다. 그러므로 스택이 빌 때까지 스택 내의 원소들을 다 출력한다.