[BOJ] 1918. 후위 표기식

스택을 이용하는 문제이다. 

이 문제는 스택을 활용하여 연산자들을 스택에 저장하면서 수식을 후위표기식으로 출력하는 문제였다. 스택을 보다 자유롭게 활용할 수 있는 deque를 사용하였다. 이 문제에서는 연산자들마다 우선순위가 있기에 그것을 고려하여 스택을 탐색하는 과정이 필요했다. 입력을 하나씩 확인하면서 다음과 같은 규칙을 적용하였다.

1. A~Z의 경우 바로 출력
2. (의 경우 바로 스택에 넣기
3. )의 경우 스택에서 (를 만나기 전까지 출력
4. +,-의 경우 우선순위가 *,/보다 낮기때문에 스택이 비거나 (를 만나기전까지 스택에서 빼서 출력
5. *,/의 경우 우선순위가 +,-보다 높기때문에 스택이 비거나 +,-,(를 만나기전까지 스택에서 빼서 출력

package algosutdy1;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
 
public class Main_bj_1918_후위표기식 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();
 
        Deque<Character> deque = new LinkedList<>();
 
        String result = "";
 
        for (int i = 0; i < input.length(); i++) {
            char cur = input.charAt(i);
 
            if ('A' <= cur && cur <= 'Z') {
                //A~Z는 그대로 출력
                result += cur;
            } else if (cur == '+' || cur == '-') {
                //+,-는 우선순위가 *,/보다 낮기에 스택이 비거나 (가 나오기 전까지 스택을 출력 후 스택에 넣기
                while (true) {
                    if (deque.isEmpty()) {
                        break;
                    }
 
                    char top = deque.peekLast();
 
                    if (top == '(') {
                        break;
                    }
                    result += deque.removeLast();
                }
 
                deque.addLast(cur);
            } else if (cur == '*' || cur == '/') {
                //*,/는 +,-보다 우선순위가 높아서 +,-,(가 나오기 전까지 스택을 출력 후 스택에 넣기
                while (true) {
                    if (deque.isEmpty()) {
                        break;
                    }
 
                    char top = deque.peekLast();
 
                    if (top == '+' || top == '-' || top == '(') {
                        break;
                    }
 
                    result += deque.removeLast();
                }
 
                deque.addLast(cur);
            } else if (cur == ')') {
                //)는 (가 스택에 나오기 전까지 스택을 출력
                while (true) {
                    char top = deque.peekLast();
 
                    if (top == '(') {
                        deque.removeLast();
                        break;
                    } else {
                        result += deque.removeLast();
                    }
                }
            } else if (cur == '(') {
                //(는 그대로 스택에 넣기
                deque.addLast(cur);
            }
 
        }
 
        //스택나머지는 쭉 출력
        while (!deque.isEmpty()) {
            result += deque.removeLast();
        }
 
        System.out.println(result);
    }
}