[BOJ] 16637. 괄호 추가하기

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;

public class Main {
	static Scanner sc=new Scanner(System.in);
	static int N=sc.nextInt();
	static String form=sc.next();
	static List<Character> list=new ArrayList<>();
	static Stack<Character> operStack=new Stack<>();
	static Stack<Integer> numStack=new Stack<>();
	static Stack<Character> operStack2=new Stack<>();
	static Stack<Integer> numStack2=new Stack<Integer>();
	static int ans=Integer.MIN_VALUE;
	public static void main(String[] args) {
		init();
		go(0);
		System.out.println(ans);
	}
	
	public static void go(int index) {
		if(index+3>list.size()) {
//			for (int i = 0; i < list.size(); i++) {
//				System.out.print(list.get(i));
//			}
//			System.out.println();
			ans=Math.max(ans, result());
			return;
		}
		
		list.add(index,'(');
		list.add(index+4,')');
		go(index+6);
		list.remove(index);
		list.remove(index+3);
		go(index+2);
	}

	public static int result() {
		int size=list.size();
		for (int i = 0; i < size; i++) {
			char c=list.get(i);
			if(c=='('||c=='+'||c=='-'||c=='*'||c==')') {
				if(c==')') {
					int a=numStack.pop();
					int b=numStack.pop();
					char oper=operStack.pop(); // 괄호안 연산자 제거 
					numStack.push(cal(b,a,oper));
					operStack.pop();// 여는 괄호 제거 
				}else {
					operStack.push(c);
				}
			}else {
				numStack.push(c-'0');
			}
		}
		while(!numStack.isEmpty()) {
			numStack2.push(numStack.pop());			
		}
		while(!operStack.isEmpty()) {
			operStack2.push(operStack.pop());
		}
		
		while(!operStack2.isEmpty()) {
			int a=numStack2.pop();
			int b=numStack2.pop();
			char oper=operStack2.pop(); 
			numStack2.push(cal(a,b,oper));
		}
		return numStack2.pop();
	} 
	
	public static int cal(int a,int b,char oper) {
		if(oper=='+') return a+b;
		else if(oper=='-') return a-b;
		else if(oper=='*') return a*b;
		return 0;
	}
	
	public static void init() {
		int size=form.length();
		for (int i = 0; i < size; i++) {
			list.add(form.charAt(i));
		}
	}
}