(카카오)수식 최대화(문제20)

import java.util.*;

class Solution {
    private static ArrayList<ArrayList<Character>> operatorPriorities = new ArrayList<>();
    
    public long solution(String expression) {
        operatorPriorities.add(new ArrayList<>(Arrays.asList('+', '-', '*')));
        operatorPriorities.add(new ArrayList<>(Arrays.asList('+', '*', '-')));
        operatorPriorities.add(new ArrayList<>(Arrays.asList('-', '+', '*')));
        operatorPriorities.add(new ArrayList<>(Arrays.asList('-', '*', '+')));
        operatorPriorities.add(new ArrayList<>(Arrays.asList('*', '-', '+')));
        operatorPriorities.add(new ArrayList<>(Arrays.asList('*', '+', '-')));
        
        //연사자 얻기 이것도 필요가 없네
        //List<Character> operators = getOperators(expression);
        
        //우선순위들로 계산
        
        
        return calculate(expression);
    }
    
    private static long calculate(String s){
        long max = -1L;
        for(ArrayList<Character> priority : operatorPriorities){
            //토큰 추출
            List<String> tokens = new ArrayList<>();
            StringBuilder sb = new StringBuilder();
            for(char c : s.toCharArray()){
                if(Character.isDigit(c)){
                    sb.append(c);
                }else{
                    tokens.add(sb.toString());
                    tokens.add(String.valueOf(c));
                    sb = new StringBuilder();
                }
            }
            if(sb.length() > 0) tokens.add(sb.toString());

            
            //후위 연산으로 변경
            Stack<Character> stack = new Stack<>();
            List<String> list = new ArrayList<>();
            
            for (String token : tokens) {
                if (token.equals("*") || token.equals("+") || token.equals("-")) {
                    int currentPriority = priority.indexOf(token.charAt(0));
                    while (!stack.isEmpty() && priority.indexOf(stack.peek()) >= currentPriority) {
                        list.add(String.valueOf(stack.pop()));
                    }
                    stack.push(token.charAt(0));
                } else {
                    list.add(token);
                }
            }

            // 🔥 스택에 남아 있는 연산자 모두 pop
            while (!stack.isEmpty()) {
                list.add(String.valueOf(stack.pop()));
            }
            
            // System.out.println(list);
            //stack 비었으니 그대로쓰면된다.
            Stack<String> stack2 = new Stack<>();
            for(String token : list){
                if (token.equals("*") || token.equals("+") || token.equals("-")) {
                    long b = Long.parseLong(stack2.pop());
                    long a = Long.parseLong(stack2.pop());
                    if(token.equals("*")) stack2.push(String.valueOf(a*b));
                    if(token.equals("+")) stack2.push(String.valueOf(a+b));
                    if(token.equals("-")) stack2.push(String.valueOf(a-b));
                }else{
                    stack2.push(token);
                }
                
            }
            max = Math.max(max, Math.abs(Long.parseLong(stack2.pop())));
        }
        return max;
    }
    
    private static List<Character> getOperators(String s){
        Set<Character> operators = new HashSet<>();
        for(char c : s.toCharArray()){
            if(c == '+' || c == '-' || c == '*') operators.add(c);
        }
        return new ArrayList<>(operators);
    }
}