[伯俊]#2800括弧を削除

質問する

式が与えられた場合、カッコを削除して得られる異なる式の個数を計算するプログラムを作成します.
この公式のかっこは正になっている.例えば、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です.

しゅつりょく

正しいかっこペアを削除し、アルファベット順に異なるフォーマットを出力します.

入力例1

(0/(0))

サンプル出力1

(0/0)
0/(0)
0/0

入力例2

(2+(2*2)+2)

サンプル出力2

(2+2*2+2)
2+(2*2)+2
2+2*2+2

入力例3

(1+(2*(3+4)))

サンプル出力3

(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;
        }
    }
}