어떻게 괄호 의 합 법성 을 판정 합 니까?

본문 을 다 읽 고 나 면 너 는 힘 을 다 해 다음 과 같은 문 제 를 풀 수 있다.
20. 유효한 괄호
-----------
괄호 에 대한 합 법성 판단 은 흔히 볼 수 있 고 실 용적 인 문제 이다. 예 를 들 어 우리 가 쓴 코드, 편집기 와 컴 파일 러 는 괄호 가 정확하게 닫 혔 는 지 확인한다.그리고 우리 의 코드 는 세 가지 괄호 [](){} 를 포함 할 수 있어 서 판단 하기 가 좀 어렵다.
본 고 는 괄호 의 합 법성 판단 에 관 한 알고리즘 문 제 를 이야기 하고 스 택 이라는 데이터 구조 에 대한 이 해 를 강화 할 수 있 을 것 이 라 고 믿 습 니 다.
제목 은 간단 합 니 다. 문자열 을 입력 하 십시오. [](){} 여섯 가지 괄호 가 포함 되 어 있 습 니 다. 이 문자열 로 구 성 된 괄호 가 합 법 적 인지 판단 하 십시오.

Input: "()[]{}"
Output: true

Input: "([)]"
Output: false

Input: "{[]}"
Output: true

이 문 제 를 해결 하기 전에 우 리 는 먼저 난이 도 를 낮 추고 하나의 괄호 () 만 있다 면 문자열 로 구 성 된 괄호 가 합 법 적 인지 아 닌 지 를 어떻게 판단 해 야 할 지 생각해 보 자.
PS: 저 는 100 여 편의 오리지널 작품 을 열심히 썼 습 니 다. 손 에 200 개의 파워 버튼 문 제 를 긁 었 고 모두 labuladong 의 알고리즘 소 초 를 발표 하여 계속 업데이트 되 었 습 니 다.소장 을 권장 합 니 다. 제 글 순서에 따라 문 제 를 풀 고 각종 알고리즘 을 파악 한 후에 문제 에 넣 으 면 물 만난 고기 와 같 습 니 다.
괄호
문자열 에는 괄호 만 있 습 니 다. 괄호 문자열 을 합 법 적 으로 하려 면 다음 을 해 야 합 니 다.
모든 오른쪽 괄호 ) 의 왼쪽 에는 반드시 왼쪽 괄호 ( 가 그것 과 일치 해 야 한다.
예 를 들 어 문자열 ()))(( 에서 중간 에 있 는 두 개의 오른쪽 괄호 왼쪽 에 왼쪽 괄호 가 일치 하지 않 기 때문에 이 괄호 조합 은 합 법 적 이지 않다.
그러면 이 사고방식 에 따라 우 리 는 알고리즘 을 쓸 수 있다.

bool isValid(string str) {
    //          
    int left = 0;
    for (char c : str) {
        if (c == '(')
            left++;
        else //      
            left--;

        if (left < 0)
            return false;
    }
    return left == 0;
}

괄호 만 있 으 면 합 법성 을 정확하게 판단 할 수 있다.세 가지 괄호 의 상황 에 대해 저 는 처음에 이 생각 을 모방 하여 세 가지 변수 left1 를 정의 하고 싶 었 습 니 다. left2, left3 각각 괄호 를 처리 하고 싶 었 습 니 다. if else 가 지 를 많이 써 야 하지만 문 제 를 해결 할 수 있 을 것 같 습 니 다.
그러나 실제 적 으로 이런 사고방식 을 그대로 옮 겨 서 는 안 된다. 예 를 들 어 하나의 괄호 만 있 는 상황 (()) 은 합 법 적 이지 만 여러 가지 괄호 가 있 는 상황 [(]) 은 분명히 비합법적 이다.
모든 왼쪽 괄호 가 나타 난 횟수 만 기록 하면 정확 한 판단 을 할 수 없다. 우 리 는 저 장 된 정 보 량 을 늘 리 고 스 택 을 이용 하여 비슷 한 사 고 를 모방 할 수 있다.
2. 여러 가지 괄호 처리
스 택 은 선진 적 인 데이터 구조 로 괄호 문 제 를 처리 할 때 특히 유용 하 다.
우리 의 이 문 제 는 이전 사고방식 의 left 변 수 를 left 라 는 창고 로 대체 하고 왼쪽 괄호 를 만나면 창고 에 들어간다. 오른쪽 괄호 를 만나면 창고 에서 가장 가 까 운 왼쪽 괄호 를 찾 아서 일치 하 는 지 확인 하 자.

bool isValid(string str) {
    stack left;
    for (char c : str) {
        if (c == '(' || c == '{' || c == '[')
            left.push(c);
        else //    c     
            if (!left.empty() && leftOf(c) == left.top())
                left.pop();
            else
                //           
                return false;
    }
    //              
    return left.empty();
}

char leftOf(char c) {
    if (c == '}') return '{';
    if (c == ')') return '(';
    return '[';
}

＿＿＿＿＿＿＿＿＿＿＿＿＿
나의 온라인 전자 책 에는 100 편의 오리지널 문장 이 있 는데, 손잡이 끈 으로 200 개의 힘 으로 문 제 를 풀 고, 소장 하 는 것 을 건의 합 니 다!대응 하 는 GitHub 알고리즘 창 고 는 이미 70k star 를 획득 하 였 습 니 다. 별 을 환영 합 니 다!