👨‍💻 문제

---

✍️ 풀이

🤔 생각

어떻게 풀지 먼저 생각해보았다.

1. 괄호부터 없앤다.

A + B * (C + D) 👉 A + B * CD+

현재 값이 닫는 괄호가 나온다면 여는 괄호가 나올 때까지 뺀다.
해당 문자열들을 후위 표기식으로 바꾼 후 하나의 문자열로 다시 스택에 집어넣는다.

기존 스택 : A + B *
괄호 덱ㅡ : C + D 

덱을 활용해 원래 순서로 넣는다.
덱에 후위 표기식 변환 메소드를 적용한다.
후위 표기식 변환 메소드는 아래 2번과 3번 동작을 수행한다.

2. 곱셈/나눗셈 처리

A + B * CD+ 👉 A + BCD+*

곱셈/나눗셈 나오면 다음값이랑 순서를 바꾼다.

3. 덧셈/뺄셈 처리

A + BCD+* 👉 ABCD+*+

덧셈/뺄셈 나오면 다음값이랑 순서를 바꾼다.

👨‍💻 구현

위에서 생각한 대로 구현했다.

---

📄 전체 소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;

public class Main {

    public static void main(String[] args) throws IOException {

        Deque<String> deque = new ArrayDeque<>();

        String[] values = input();
        for (String value : values) {
            if (value.equals(")")) {
                deque.addLast(toPostfix(getDequeInsideOfBracket(deque)));
            }
            else {
                deque.addLast(value);
            }
        }
        System.out.println(toPostfix(deque));
    }

    private static String[] input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        return br.readLine().split("");
    }

    private static Deque<String> getDequeInsideOfBracket(Deque<String> deque) {
        Deque<String> newDeque = new ArrayDeque<>();
        while (true) {
            String value = deque.pollLast();
            if (value.equals("(")) {
                break;
            }
            newDeque.addFirst(value);
        }
        return newDeque;
    }

    private static String toPostfix(Deque<String> deque) {

        Deque<String> prevDeque;
        Deque<String> currDeque;

        // 곱셈/나눗셈
        prevDeque = deque;
        currDeque = new ArrayDeque<>();
        while (!prevDeque.isEmpty()) {
            String value = prevDeque.pollFirst();
            if (value.equals("*") || value.equals("/")) {
                String prevValue = currDeque.pollLast();
                String nextValue = prevDeque.pollFirst();
                currDeque.addLast(prevValue + nextValue + value);
            }
            else {
                currDeque.addLast(value);
            }
        }

        // 덧셈/뺄셈
        prevDeque = currDeque;
        currDeque = new ArrayDeque<>();
        while (!prevDeque.isEmpty()) {
            String value = prevDeque.pollFirst();
            if (value.equals("+") || value.equals("-")) {
                String prevValue = currDeque.pollLast();
                String nextValue = prevDeque.pollFirst();
                currDeque.addLast(prevValue + nextValue + value);
            }
            else {
                currDeque.addLast(value);
            }
        }

        StringBuilder sb = new StringBuilder();
        while (!currDeque.isEmpty()) {
            sb.append(currDeque.pollFirst());
        }
        return sb.toString();
    }

}

🔍️ 참고

        // 덧셈/뺄셈
        prevDeque = currDeque;
        currDeque = new ArrayDeque<>();
        while (!prevDeque.isEmpty()) {
            String value = prevDeque.pollFirst();
            if (value.equals("+") || value.equals("-")) {
                String prevValue = currDeque.pollLast();
                String nextValue = prevDeque.pollFirst();
                currDeque.addLast(prevValue + nextValue + value);
            }
            else {
                currDeque.addLast(value);
            }
        }

        StringBuilder sb = new StringBuilder();
        while (!currDeque.isEmpty()) {
            sb.append(currDeque.pollFirst());
        }
        return sb.toString();

후위 표기식 변환 메소드에서, 덧셈/뺄셈 순서 변경 시에는
굳이 currDeque에 넣지 않고 바로 StringBuilder에 넣어버리는 것이 더 빠르다.