ITwork

www.acmicpc.net/problem/9012

아래 코드로 돌렸을 때 segmentation fault 발생 해서 gdb로 디버깅 한 결과입니다.

일단 은 어느 코드에서 문제가 발생한 정도로만 확인이 가능한데, 이정도만 추적을 해도 코드 수정하는데 많은 도움이 된다고 보입니다. 

  1 #include <iostream>                                                                                                                                                                                    
  2 #include <stack>
  3 #include <string.h>
  4 
  5 using namespace std;
  6 
  7 int main()
  8 {
  9     int n=0,i,j, check=0, count;
 10     char input[51];
 11 
 12     stack<char> s;
 13     cin >> count;
 14 
 15     for(j=0; j<count; j++)
 16     {
 17         check = 0;
 18         cin >> input;
 19         n = strlen(input);
 20 
 21         for(i=0; i<n; i++)
 22         {
 23             if ( input[i] == '(')
 24                 s.push(input[i]);
 25             else if(i == 0 && input[i] == ')')
 26             {
 27                 s.push(input[i]);
 28                 break;
 29             }
 30             else if( i !=0 && input[i]  == ')' )
 31             {
 32                 if( s.top() == '(' )
 33                     s.pop();
 34                 else
 35                     s.push(input[i]);
 36             }
 37         }   
 38         
 39         if( s.empty() )
 40             cout << "YES" << endl;
 41         else
 42             cout << "NO" << endl;
 43             
 44     }
 45     return 0;
 46 }   

#gdb ./a.out

gdb b main

gdb r

input값은 각각 count와 input 입력시 넣어 주시면 됩니다. 

1 <-- count

(())()) <-- input

step을 해보면서 segmentation fault발생한 지점이 32 line s.top()에서 문제가 발생한 것을 알았으며

s.top()이 stack에  아무것도 없을 경우 값이 이상한 값을 return하므로 조건문을 s.empty()인지를 추가해 주면 해결 될 것으로 판단해서 코드 수정을 해 주시면 될 것 같습니다.

Breakpoint 1, main () at 9012.cpp:8
8	{
(gdb) n
9		int n=0,i,j, check=0, count;
(gdb) n
12	    stack<char> s;
(gdb) n
13	    cin >> count;
(gdb) n
1
15	    for(j=0; j<count; j++)
(gdb) n
17	        check = 0;
(gdb) n
18	        cin >> input;
(gdb) n
(())())
19	        n = strlen(input);
(gdb) n
21	        for(i=0; i<n; i++)
(gdb) disp n
1: n = 7
(gdb) n
23	            if ( input[i] == '(')
1: n = 7
(gdb) n
24	                s.push(input[i]);
1: n = 7
(gdb) n
21	        for(i=0; i<n; i++)
1: n = 7
(gdb) n
23	            if ( input[i] == '(')
1: n = 7
(gdb) disp *input@i
2: *input@i = "("
(gdb) n
24	                s.push(input[i]);
1: n = 7
2: *input@i = "("
(gdb) disp i
3: i = 1
(gdb) n
21	        for(i=0; i<n; i++)
1: n = 7
2: *input@i = "("
3: i = 1
(gdb) n
23	            if ( input[i] == '(')
1: n = 7
2: *input@i = "(("
3: i = 2
(gdb) n
25	            else if(i == 0 && input[i] == ')')
1: n = 7
2: *input@i = "(("
3: i = 2
(gdb) n
30	            else if( i !=0 && input[i]  == ')' )
1: n = 7
2: *input@i = "(("
3: i = 2
(gdb) n
32	                if( s.top() == '(' )
1: n = 7
2: *input@i = "(("
3: i = 2
(gdb) n
33	                    s.pop();
1: n = 7
2: *input@i = "(("
3: i = 2
(gdb) n
21	        for(i=0; i<n; i++)
1: n = 7
2: *input@i = "(("
3: i = 2
(gdb) n
23	            if ( input[i] == '(')
1: n = 7
2: *input@i = "(()"
3: i = 3
(gdb) n
25	            else if(i == 0 && input[i] == ')')
1: n = 7
2: *input@i = "(()"
3: i = 3
(gdb) n
30	            else if( i !=0 && input[i]  == ')' )
1: n = 7
2: *input@i = "(()"
3: i = 3
(gdb) n
32	                if( s.top() == '(' )
1: n = 7
2: *input@i = "(()"
3: i = 3
(gdb) n
33	                    s.pop();
1: n = 7
2: *input@i = "(()"
3: i = 3
(gdb) n
21	        for(i=0; i<n; i++)
1: n = 7
2: *input@i = "(()"
3: i = 3
(gdb) n
23	            if ( input[i] == '(')
1: n = 7
2: *input@i = "(())"
3: i = 4
(gdb) n
24	                s.push(input[i]);
1: n = 7
2: *input@i = "(())"
3: i = 4
(gdb) n
21	        for(i=0; i<n; i++)
1: n = 7
2: *input@i = "(())"
3: i = 4
(gdb) n
23	            if ( input[i] == '(')
1: n = 7
2: *input@i = "(())("
3: i = 5
(gdb) n
25	            else if(i == 0 && input[i] == ')')
1: n = 7
2: *input@i = "(())("
3: i = 5
(gdb) n
30	            else if( i !=0 && input[i]  == ')' )
1: n = 7
2: *input@i = "(())("
3: i = 5
(gdb) n
32	                if( s.top() == '(' )
1: n = 7
2: *input@i = "(())("
3: i = 5
(gdb) n
33	                    s.pop();
1: n = 7
2: *input@i = "(())("
3: i = 5
(gdb) n
21	        for(i=0; i<n; i++)
1: n = 7
2: *input@i = "(())("
3: i = 5
(gdb) n
23	            if ( input[i] == '(')
1: n = 7
2: *input@i = "(())()"
3: i = 6
(gdb) n
25	            else if(i == 0 && input[i] == ')')
1: n = 7
2: *input@i = "(())()"
3: i = 6
(gdb) n
30	            else if( i !=0 && input[i]  == ')' )
1: n = 7
2: *input@i = "(())()"
3: i = 6
(gdb) n
32	                if( s.top() == '(' )
1: n = 7
2: *input@i = "(())()"
3: i = 6
(gdb) n

Program received signal SIGSEGV, Segmentation fault.
main () at 9012.cpp:32
32	                if( s.top() == '(' )
1: n = 7
2: *input@i = "(())()"
3: i = 6
(gdb) 

문제점 수정한 코드는 아래와 같으면 결과가 잘 출력되는 걸 확인 했습니다.

  1 #include <iostream>
  2 #include <stack>
  3 #include <string.h>
  4 
  5 using namespace std;
  6 
  7 int main()
  8 {
  9     int n=0,i,j, check=0, count;
 10     char input[51];
 11 
 12     stack<char> s;
 13     cin >> count;
 14 
 15     for(j=0; j<count; j++){
 16         check = 0;
 17         cin >> input;
 18         n = strlen(input);
 19 
 20         for(i=0; i<n; i++){
 21             if ( input[i] == '(')
 22                 s.push(input[i]);
 23             else if(i == 0 && input[i] == ')'){
 24                 s.push(input[i]);
 25                 break;
 26             }
 27             else if( i !=0 && input[i]  == ')' ){
 28                 if( s.empty() ){
 29                     s.push(input[i]);
 30                 }
 31                 else{
 32                     if( s.top() == '(' )
 33                         s.pop();
 34                     else
 35                         s.push(input[i]);
 36                 }
 37             }
 38         }                          
 39 
 40         if( s.empty() )
 41             cout << "YES" << endl;
 42         else
 43             cout << "NO" << endl;
 44 
 45         while( !s.empty() )
 46             s.pop();
 47     }
 48     return 0;
 49 }