[java] 자바 스택을 활용한 괄호 검사 알고리즘 구현하기

05 Dec 2023

java

괄호 검사는 프로그래밍에서 자주 사용되는 중요한 알고리즘입니다. 괄호의 짝이 올바르게 맞아야 코드가 정상적으로 작동하기 때문에, 이를 검사하는 알고리즘을 구현하는 것은 필수적입니다. 이번에는 자바의 스택을 활용하여 괄호 검사 알고리즘을 구현해보겠습니다.

알고리즘 동작

문자열을 순회하며 문자를 하나씩 확인합니다.
여는 괄호((, {, [)를 만나면 스택에 push 합니다.
닫는 괄호(), }, ])를 만나면 스택의 top을 확인하여 짝이 맞는지 검사합니다.
- 짝이 맞지 않으면 유효하지 않은 문자열로 처리합니다.
문자열을 모두 확인한 후에도 스택에 여는 괄호가 남아있으면 유효하지 않은 문자열로 처리합니다.
위 조건에 모두 해당하지 않으면 유효한 괄호 문자열로 처리합니다.

알고리즘 구현

import java.util.Stack;

public class BracketValidator {
    public static boolean validate(String input) {
        Stack<Character> stack = new Stack<>();
        for (char c : input.toCharArray()) {
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            } else if (c == ')' || c == '}' || c == ']') {
                if (stack.isEmpty()) {
                    return false;
                } else {
                    char top = stack.peek();
                    if ((c == ')' && top != '(')
                            || (c == '}' && top != '{')
                            || (c == ']' && top != '[')) {
                        return false;
                    }
                    stack.pop();
                }
            }
        }
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        String input = "{(())}";
        if (validate(input)) {
            System.out.println("유효한 괄호 문자열입니다.");
        } else {
            System.out.println("유효하지 않은 괄호 문자열입니다.");
        }
    }
}

위의 코드는 주어진 문자열이 유효한 괄호 문자열인지를 판별하는 validate() 메소드를 구현한 예시입니다.

테스트 결과

위의 예시 코드에서는 “{(())}”라는 문자열을 테스트하였는데, 이는 유효한 괄호 문자열입니다. 따라서 다음과 같은 결과가 출력됩니다.

유효한 괄호 문자열입니다.

마무리

자바의 스택을 활용하여 괄호 검사 알고리즘을 구현하는 방법을 살펴보았습니다. 괄호 검사는 프로그래밍에서 중요한 역할을 하는 알고리즘 중 하나이므로, 손쉽게 구현할 수 있도록 스택을 활용하는 방법에 익숙해지시기 바랍니다.