[BaekJoon] 16638 괄호 추가하기 2 (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
    static int length, answer;
    static boolean[] brackets;
    static Element[] expression;

    static void input() {
        Reader scanner = new Reader();

        length = scanner.nextInt(); // 수식 길이
        answer = Integer.MIN_VALUE;
		// 괄호 여부
		// 해당 연산자 앞, 뒤의 피연산자들의 연산에 대해 괄호를 쳤는지 여부
        brackets = new boolean[length];
        expression = new Element[length]; // 각 숫자 및 연산기호를 Element 객체로 변환하여 저장
        String info = scanner.nextLine();

        for(int idx = 0; idx < length; idx++) {
            char element = info.charAt(idx);
			// 곱하기 연산자의 경우, 더하기, 빼기보다 우선순위가 앞서있기 때문에 우선순위를 2로 설정
			// 숫자의 우선순위가 제일 높기 때문에 숫자의 우선순위가 0이 되고,
			// 괄호 연산의 우선순위가 곱하기보다 높기 때문에 괄호 연산의 우선순위가 1이 된다
            if(element == '*') expression[idx] = new Element(element, 2);
						// 더하기, 빼기 연산자의 경우, 가장 우선순위가 낮기 때문에 우선순위를 3으로 설정
            else if(element == '+' || element == '-') expression[idx] = new Element(element, 3);
						// 숫자의 우선순위는 제일 높은 0으로 설정한다
            else expression[idx] = new Element(element, 0);
        }
    }

    static void solution() {
        findMaxByBracket(1);
        System.out.println(answer);
    }

    static void findMaxByBracket(int index) {
		// 모든 연산자에 대한 괄호 작업이 마무리되었다면
        if(index >= length) {
			// 중위 표현식을 후위 표현식으로 변경한 후 후위 표현식으로 계산을 진행한다
            int expressionResult = postfix(inorderToPostOrder());
			// 계산된 값과 이전까지의 최댓값을 비교하여 더 큰 수로 갱신한다
            answer = Math.max(answer, expressionResult);
            return;
        }

		// 첫 연산자라면 괄호를 쳐보고 이후 계산을 진행한다
        if(index == 1) {
            brackets[index] = true;
            findMaxByBracket(index + 2);
            brackets[index] = false;
        } else { // 첫 연산자가 아니라면
			// 이전 연산자에 대해 괄호가 쳐졌는지 확인하고
			// 만약 쳐져있다면 현재 연산자까지 괄호를 치면 같은 괄호 안에 2개의 연산자가 들어가기 때문에 현재 위치에는 괄호를 칠 수 없다
			// 그러므로 이전 연산자에 괄호가 쳐져있지 않은 상태일 때에만 현재 연산자에도 괄호를 치고 다음 계산을 진행한다
            if(!brackets[index - 2]) {
                brackets[index] = true;
                findMaxByBracket(index + 2);
                brackets[index] = false;
            }
        }
		// 현재 연산자에 괄호를 치지 않고 다음 계산을 이어간다
        findMaxByBracket(index + 2);
    }

	// 중위 표현식을 후위 표현식으로 변환하는 메서드
    static List<Element> inorderToPostOrder() {
        List<Element> postOrder = new ArrayList<>(); // 후위 표현식
        Stack<Element> stack = new Stack<>(); // 연산자들을 임시로 저장하는 공간(우선순위로 인해)

		// 식의 각 요소들을 순회하면서 계산을 진행한다
        for(int idx = 0; idx < length; idx++) {
			// 현재 요소가 숫자라면 postOrder 리스트에 해당 숫자를 넣는다
            if(expression[idx].priority == 0) postOrder.add(expression[idx]);
            else { // 현재 요소가 연산자라면
				// 현재 연산자의 우선순위를 가져오고 만약 현재 연산자에 괄호가 쳐져 있다면 우선순위를 1로 변경한다
                int priority = expression[idx].priority;
                if(brackets[idx]) priority = 1;
				// stack이 비워지기 전까지 현재 연산자의 우선순위보다 높거나 같은(우선순위를 나타내는 숫자로 따지면 낮거나 같은) 우선순위를 갖고 있는 연산자들을 stack에 빼고
				// 그 연산자들을 postOrder에 넣는다
                while(!stack.isEmpty() && stack.peek().priority <= priority)
                    postOrder.add(stack.pop());

				// stack에 현재 연산자를 넣는다
                stack.push(new Element(expression[idx].element, priority));
            }
        }

		// 아직 stack에 연산자들이 남아있다면 남아있는 모든 연산자들을 postOrder 리스트에 넣어 후위 표현식을 완성시킨다
        while(!stack.isEmpty()) postOrder.add(stack.pop());

        return postOrder;
    }

	// 후위 표현식을 계산하는 메서드
    static int postfix(List<Element> postOrder) {
        Stack<Integer> stack = new Stack<>();
        int result = 0;

        for(int idx = 0; idx < length; idx++) {
			// 만약 현재 위치의 요소가 숫자라면 stack에 숫자를 넣는다
            if(postOrder.get(idx).priority == 0) stack.push(postOrder.get(idx).element - '0');
            else { // 현재 위치의 요소가 연산자라면
				// 두 숫자를 빼서 연산자에 맞게 계산을 진행한 후, 그 숫자를 stack에 넣는다
                int n1 = stack.pop();
                int n2 = stack.pop();

                result = calculate(n2, n1, postOrder.get(idx).element);
                stack.push(result);
            }
        }

        return stack.pop();
    }

    static int calculate(int n1, int n2, char operator) {
        int result = 0;
        switch(operator) {
            case '+':
                result = n1 + n2;
                break;
            case '-':
                result = n1 - n2;
                break;
            case '*':
                result = n1 * n2;
                break;
        }

        return result;
    }

    static class Element {
        char element;
        int priority;

        public Element(char element, int priority) {
            this.element = element;
            this.priority = priority;
        }
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }

            return str;
        }
    }
}