SW Expert Academy - 1224번(계산기3)

문제 출처: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14tDX6AFgCFAYD&categoryId=AV14tDX6AFgCFAYD&categoryType=CODE&problemTitle=1224&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

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

public class Solution {

    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int problemNum = 1;

        for (int i = 0; i < 10; i++) {
            int size = Integer.parseInt(reader.readLine());
            StringBuilder tempString = new StringBuilder();
            Stack<String> temp = new Stack<>();
            // 중위 표기 -> 후위 표기
            for (String str : reader.readLine().split("")) {
                if (str.equals(")")) {
                    ArrayDeque<String> arrayDeque = new ArrayDeque<>();
                    StringBuilder tempString2 = new StringBuilder();
                    while (!temp.peek().equals("(")) {
                        arrayDeque.offer(temp.pop());
                    }
                    temp.pop();
                    arrayDeque = stackProcess(arrayDeque);
                    while (!arrayDeque.isEmpty()) {
                        tempString2.append(arrayDeque.poll());
                    }
                    temp.push(tempString2.toString());
                } else {
                    temp.push(str);
                }
            }

            tempString.setLength(0);

            while (!temp.isEmpty()) {
                tempString.append(temp.pop());
            }

            // 중위 표현 계산
            Stack<Integer> calcStack = new Stack<>();
            for (char c : tempString.toString().toCharArray()) {
                if (c == '+' || c == '*') {
                    int head = ' ';
                    int tail = ' ';

                    int result = 0;

                    if (!calcStack.isEmpty()) tail = calcStack.pop();
                    if (!calcStack.isEmpty()) head = calcStack.pop();

                    if (c == '+') result = head + tail;
                    else result = head * tail;

                    calcStack.push(result);
                } else {
                    calcStack.push(c - '0');
                }
            }

            sb.append("#").append(problemNum++).append(" ");
            sb.append(calcStack.pop()).append("\n");
        }

        System.out.println(sb);
    }

    private static ArrayDeque<String> stackProcess(ArrayDeque<String> arrayDeque) {
        ArrayDeque<String> deque = new ArrayDeque<>();
        Stack<String> stack = new Stack<>();

        String prev = "";

        while (!arrayDeque.isEmpty()) {
            String current = arrayDeque.pollLast();
            if (current.equals("*") || current.equals("+")) {
                if (!stack.isEmpty()) {
                    prev = stack.peek();
                    if (prev.equals(current)) {
                        deque.offer(stack.pop());
                    } else if (prev.equals("*")) { // * -> +
                        while (!stack.isEmpty()) {
                            deque.offer(stack.pop());
                        }
                    }
                }
                stack.push(current);
            } else {
                deque.offer(current);
            }
        }

        while (!stack.isEmpty()) {
            deque.offer(stack.pop());
        }

        return deque;
    }

}

• 큰 흐름은 계산기2의 문제와 같다.
• 그러나 여기서는 괄호 처리를 해야하는데, 이를 위해 우선 들어온 값들을 스택에 저장한다.
• 스택에 넣다가 닫는 괄호가 나오면 여는 괄호가 나올 때까지 pop()하여 덱에 넣는다. 그 다음 그 덱을 기존 계산기2 중위 표현 처리 로직을 돌려 중위 표현식을 만든다. 만들어진 값은 덱에 담겨 반환되는데, 중위 표현식으로 바뀐 부분은 다시 변환 로직에 들어가면 안되므로 하나의 문자열로 만들어 스택에 넣는다. 그 후 처리 로직은 계산기2와 같다.
• 블로그 글을 작성하다 생각한 부분인데, 굳이 덱으로 안해도 되고 스택으로 해도 될 것 같다.