[알고리즘/Stack] 유효한 괄호가 있는지 판별

이것도 스택을 이용한 대표적인 알고리즘 중 하나이다.

유효한 괄호는 [(()){}] 와 같이 여는 괄호와 닫는 괄호의 갯수가 같고, 각 여는 괄호와 닫는 괄호의 짝이 맞아야한다.

 

# 대략적인 과정

1. 여는 괄호가 나올 경우 Stack에 push

2. 닫는 괄호가 나올 경우 스택에 pop해서 비교한다. (닫는괄호와 여는 괄호가 서로 짝이 다르거나, 스택이 비어있다면 괄호의 개수가 맞지 않아 모두 유효하지 않은 괄호식인 것이다.)

아, 그리고 이 과정을 모두 반복했는데 스택에 남아있는 괄호가 있어도 짝이 맞지 않은 것이고, 스택이 비어있어야 유효한 괄호인 것이다.

 

# 소스코드

public boolean checkParentheses(String str) {
        Stack<Character> stack = new Stack<>();
        for(int i = 0; i < str.length(); i++) {
                char ch = str.charAt(i);
 
                if(ch == '(' || ch == '{' || ch == '[')
                        stack.push(ch);
                else if(ch == ')' || ch == '}' || ch == ']') {
                        if(stack.isEmpty())
                                return false;
                        char temp = stack.pop();
                        
                        if((temp == '(' && ch != ')') || (temp == '{' && ch != '}') || (temp == '[' && ch != ']'))
                                return false;
                }
        }
 
        return stack.isEmpty();
}