[백준] 1918번: 후위 표기식 (JAVA, 문제, 문제풀이)

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

1918번: 후위 표기식

 

아래 차량기지 알고리즘을 참조했다.

https://ko.wikipedia.org/wiki/%EC%B0%A8%EB%9F%89%EA%B8%B0%EC%A7%80_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

차량기지 알고리즘 - 위키백과, 우리 모두의 백과사전

 

어려워서 나중에 또 풀기위해 남긴다.

 

Key Point

1. 스택에는 무조건 부호의 우선순위가 높은 순서로 쌓여야 한다.

2. 여는 괄호를 만나면 스택에 넣고, 닫는 괄호가 나왔을 때, 여는 괄호가 나올 때까지 계속 pop한다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
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();
        Stack<Character> stack = new Stack<>();

        String str = br.readLine();
        
        // 각 부호에 우선순위 부여
        HashMap<Character, Integer> dict = new HashMap<Character, Integer>() {{
         put('+', 1);
         put('-', 1);
         put('*', 2);
         put('/', 2);
         put('(', 0);
        }};

        for (int i = 0; i < str.length(); i++) {
            char temp = str.charAt(i);
            if ('A' <= temp && temp <= 'Z') { // 알파벳이면 무조건 출력
                sb.append(temp);
            } else {
                if (temp == '(') { // 여는 괄호가 나오면 무조건 스택에 push
                    stack.add(temp);
                } else if (temp == ')') { // 닫는 괄호가 나오면 여는 괄호가 나올 때까지 스택에서 pop
                    char calc = ' ';
                    while (calc != '(') {
                        calc = stack.pop();
                        if (calc != '(') sb.append(calc);
                    }
                } else { // 괄호 이외의 부호
                    while (!stack.isEmpty() && dict.get(temp) <= dict.get(stack.peek())) {
                        sb.append(stack.pop()); // 현재 포커스인 부호보다 스택에 쌓인 부호의 우선순위가 더 작으면 순선대로 pop 후 출력
                    }
                    stack.add(temp); // 현재 부호 스택에 push
                }
            }
        }
        while (!stack.isEmpty()) { // 스택에 남은 부호 출력
            sb.append(stack.pop());
        }
        System.out.println(sb);
    }
}