어떤 수식이 주어졌을 때, 괄호를 제거해서 나올 수 있는 서로 다른 식의 개수를 계산하는 프로그램을 작성하시오.
이 수식은 괄호가 올바르게 쳐져 있다. 예를 들면, 1+2, (3+4), (3+4*(5+6))와 같은 식은 괄호가 서로 쌍이 맞으므로 올바른 식이다.
하지만, 1+(23, ((2+3)4 와 같은 식은 쌍이 맞지 않는 괄호가 있으므로 올바른 식이 아니다.
괄호를 제거할 때는, 항상 쌍이 되는 괄호끼리 제거해야 한다.
예를들어 (2+(22)+2)에서 괄호를 제거하면, (2+22+2), 2+(22)+2, 2+22+2를 만들 수 있다. 하지만, (2+22)+2와 2+(22+2)는 만들 수 없다. 그 이유는 쌍이 되지 않는 괄호를 제거했기 때문이다.
어떤 식을 여러 쌍의 괄호가 감쌀 수 있다.
첫째 줄에 음이 아닌 정수로 이루어진 수식이 주어진다. 이 수식은 괄호가 올바르게 쳐져있다. 숫자, '+', '*', '-', '/', '(', ')'로만 이루어져 있다. 수식의 길이는 최대 200이고, 괄호 쌍은 적어도 1개, 많아야 10개이다.
올바른 괄호 쌍을 제거해서 나올 수 있는 서로 다른 식을 사전 순으로 출력한다.
(0/(0))
(0/0)
0/(0)
0/0
(2+(2*2)+2)
(2+2*2+2)
2+(2*2)+2
2+2*2+2
(1+(2*(3+4)))
(1+(2*3+4))
(1+2*(3+4))
(1+2*3+4)
1+(2*(3+4))
1+(2*3+4)
1+2*(3+4)
1+2*3+4
이 문제는 스택을 이용해서 여는 괄호와 닫히는 괄호 쌍을 구하고 괄호쌍을 토대로 깊이 우선 탐색을 통해 순서있는 조합을 통해 답을 구했다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Stack;
import java.util.TreeSet;
public class Main {
static ArrayList<Pair> list; //괄호쌍 저장 리스트
static StringBuilder sb;
static TreeSet<String> res; //괄호 삭제된 각 문자열 정렬 및 저장
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str = br.readLine();
list = new ArrayList<>();
res = new TreeSet<>();
Stack<Integer> stack = new Stack<>(); //괄호 쌍 구하기 위한 스택
for(int i=0; i<str.length(); i++) {
char c = str.charAt(i);
if(c=='(')
stack.push(i); //여는 괄호면 스택에 인덱스 넣음
else if(c==')') { //닫는 괄호 나오면 가까운 여는 괄호 인덱스와 함께 Pair쌍 생성
list.add(new Pair(stack.pop(), i));
}
}
dfs(str, 0);
for(String ans : res)
System.out.println(ans);
}
public static void dfs(String str, int idx) {
if(idx>=list.size()) return;
for(int i=idx; i<list.size(); i++) {
Pair temp = list.get(i);
sb = new StringBuilder(str);
sb.replace(temp.open, temp.open+1, " "); //괄호 삭제 쉽게 괄호를 공백으로 치환해서 문자열 길이 유지
sb.replace(temp.close, temp.close+1, " ");
res.add(sb.toString().replaceAll(" ", "")); //셋에 넣을 때는 공백삭제 후 추가
dfs(sb.toString(), i+1);
sb.replace(temp.open, temp.open+1, "(");
sb.replace(temp.close, temp.close+1, ")");
}
}
public static class Pair { //괄호쌍 저장 위한 클래스 구현
int open;
int close;
public Pair(int open, int close) {
this.open = open;
this.close = close;
}
}
}