[JAVA_알고리즘] BRACKETS2 (짝이 맞지 않는 괄호 문제)

**이 문제는 [알고리즘 문제 해결 전략]에서 인용하였습니다.

문제 : https://algospot.com/judge/problem/read/BRACKETS2

 이 문제는 스택을 이용하면 간단하게 풀 수 있다.
괄호끼리는 짝이 있으므로 "({[" 와 ")}]" 의 짝이 맞는지 검사하는 방법으로 풀어나간다면 쉽게 해결할 수 있다.

 우선 예를들어 "()()"라는 문자열을 입력받았다 가정한다.

1)첫번째 입력인 '(' 괄호는 여는 괄호이기 때문에 스택에 저장한다.

2)두번째 입력인 ')'는 닫는괄호이고, 스택의 top에 있는 '(' 괄호와 짝이 맞으므로 pop연산을 한다.

3)세번째 입력인 '('는 여는 괄호이기 때문에 스택에 저장한다.
4)네번째 입력인 ')'는 닫는 괄호이기 때문에 pop연산을 한다.
(3,4 번은 위의 과정과 동일하기 때문에 그림을 첨부하지 않았다.)


 다른 예를 들어보자
입력값이 "({[}])일 경우를 풀어보자

1)첫번째 입력은 '(' 으로 여는 괄호이기 때문에 스택에 저장한다.













2)두번째 입력은 '{'으로 여는 괄호이기 때문에 스택에 저장한다.













3)세번째 입력은 '['이므로 여는 괄호이기 때문에 스택에 저장한다.













4)네번째 입력은 '}'으로 닫는 괄호이다. 그러므로 pop연산을 해야하는데, 스택의 top에 있는 괄호와 짝이 맞지 않다. ( '['와 '}' 는 짝이 맞지 않는 괄호이다.)
그러므로 입력받은 문자열은 괄호의 짝이 맞지 않다.



*결론은 여는 괄호들은 스택에 차례대로 저장하고, 닫는 괄호는 스택의 top에 있는 괄호와 짝이 맞아야 한다.
 모든 연산을 끝낸후 스택에 문자가 남아있다면 그것은 짝이 맞지 않은 것이다.
또 pop연산을 해야 하는데 스택이 비어있을 경우 그것또한 짝이 맞지 않는 것이다.

**소스코드**
public boolean stackSymbol(){
//inputSymbol은 입력받은 문자열을 계산하기 쉽게 캐릭터 배열로 바꾼것
char[] inputSymbol=inputString.toCharArray();
//스택에 넣고 빼는 반복문
for(int i=0; i<inputSymbol.length; i++){
//입력받은 문자가 open문자일 경우 스택에 넣음
if(isOpen(inputSymbol[i]))
symbolStack.push(inputSymbol[i]);
else{
//스택이 비어있으면 짝이 맞지않음
if(symbolStack.empty())
return false;
//close문자와 open문자의 짝이 맞지 않으면 false
if(closeSymbol.indexOf(inputSymbol[i])
!=openSymbol.indexOf(symbolStack.peek()))
return false;
//짝이 맞을경우 pop연산
else symbolStack.pop();
}
}
//다 실행하고 스택이 비어있다면 true
if(symbolStack.empty())
return true;
else
return false;
 
}