[스택 마인드, DP] NYOJ-15 괄호 일치(둘)

괄호 일치(둘)

묘사
"(", ")", "[", "] 네 가지 기호만 포함하는 문자열을 드리겠습니다. 적어도 몇 개의 괄호를 추가해야만 이 괄호들을 일치시킬 수 있습니다.
예:
[] 일치
([])[]가 일치합니다.
(] 이(가) 일치하지 않습니다.
([)] 일치하지 않습니다.
입력
첫 번째 행은 테스트 데이터 그룹 수(N<=10)를 나타내는 양의 정수 N을 입력합니다.
각 그룹의 테스트 데이터는 한 줄만 있고 하나의 문자열 S입니다. S에는 위에서 말한 네 가지 문자만 포함되어 있으며 S의 길이는 100을 넘지 않습니다.
출력
각 그룹의 테스트 데이터는 최소한 추가해야 할 괄호의 수량을 나타내는 정수를 출력합니다.각 그룹의 테스트 출력은 한 줄을 차지한다
샘플 입력

4

[]

([])[]

((]

([)]

샘플 출력

0

0

3

2

【분석】
유사한 창고의 사상을 운용할 수 있다.
　　　　1.'('|||'['인 경우 스택이 없습니다.
　　　　2.')' | | '이고 창고 꼭대기 요소가 일치하면 창고 꼭대기 pop입니다.
　　　　3.만약 조건 2의 반례가 있다면 순환에 들어가 현재 읽은 요소와 창고의 모든 요소를 비교합니다.
3.1 일치하면 순환을 벗어나서sum에 일치하는 개수를 추가합니다.
3.2 창고 밑에 읽어도 일치하지 않으면sum+1.
　　　　4.출력 결과는sum+"창고"의 요소 개수여야 합니다
그래서 사실 창고로 할 수 없다. 창고의 모든 요소와 하나씩 비교해야 하기 때문에 창고에 이런 조작이 없기 때문에 두 개의 수조로 창고의 조작을 모의해야 한다.
예를 들어 다음과 같은 스택은 배열로 이해해야 합니다.
(]) 먼저 (("창고"를 누르고 (3단계 실행) ","] "를 순서대로"창고 "의 ((비교해 보면 창고 밑에 있는 요소도 일치하지 않기 때문에 (3.2) sum++, 계속 읽기)) 와 비교하고 2단계를 실행합니다.
출력에 대한 답은 1입니다.
([)) 먼저 ([스택]을 누르고(3단계 수행), [)]를 스택에서 순차적으로([비교, 첫 번째(시, 현재 요소와 일치, 점프 순환(3.1)
출력 응답은 1입니다.
좋아, 이렇게 잔소리가 많으니 나도 잘 표현할 수 없으니 코드를 쳐라!
【코드】
　　

 1 #include<cstdio>

 2 #include<cstring>

 3 int main(){

 4     int n;

 5     scanf("%d",&n);

 6     while(n--){

 7         char arry[105] = {'0'},stack[105] = {'0'};

 8         scanf("%s",arry);

 9         int len = strlen(arry),i,flag,temp,sum = 0;

10         int top = 0,k;

11         for(i = 0;i < len;i++){

12             temp = flag = 0;

13             k = top;

14             if(arry[i] == '(' || arry[i] == '[')

15                 stack[top++] = arry[i];

16             else if(arry[i] == ')' && stack[top - 1] == '(' || arry[i] == ']' && stack[top - 1] == '['){

17                 top--;

18             }else{

19                 while(k!=0){

20                     if(arry[i] == ')' && stack[k - 1] == '(' || arry[i] == ']' && stack[k - 1] == '['){

21                         temp = 1;

22                         top = k - 1;

23                         break;

24                     }else{

25                         flag += 1;

26                     }

27                     k--;

28                 }

29                 if(!temp)

30                     sum += 1;

31                 else 

32                     sum += flag;

33             }

34         }

35         sum += top;

36         printf("%d
",sum);

37     }

38     return 0;

39 }

물론 DP의 사상으로 먼저 구덩이를 파서 연구를 해야 합니다...