[데이터 구조 --- 18] 스 택 기반 괄호 일치 검출

7283 단어 데이터 구조
제목 설명:
'(', ')', '{', '}', '[', ']' 만 포함 하 는 문자열 을 지정 하여 문자열 이 올 바른 지 판단 합 니 다.
유효한 문자열 만족:
왼쪽 괄호 는 같은 유형의 오른쪽 괄호 로 닫 아야 합 니 다. 왼쪽 괄호 는 정확 한 순서 로 닫 아야 합 니 다.
예시 1:
입력: "()" 출력: true
예시 2:
입력: "() [] {}" 출력: true
예시 3:
입력: "(]" 출력: false
예시 4:
입력: "([)]" 출력: false
예시 5:
입력: "{[]}" 출력: true
먼저 필요 한 스 택 구축: c 언어 구현 동적 스 택
사고 분석:
1. 문자열 의 길 이 를 찾 아 옮 겨 다 니 며 왼쪽 괄호 로 옮 겨 다 닐 때 스 택 에 해당 하 는 오른쪽 괄호 를 누 릅 니 다. 2. 오른쪽 괄호 로 옮 겨 다 닐 때 스 택 꼭대기 요 소 를 비교 하고 일치 하지 않 으 면 false 3 으로 돌아 갑 니 다. 빈 문자 로 옮 겨 다 니 면 continue 4. 최종 적 으로 옮 겨 다 니 며 일치 하 는 근 거 는 스 택 이 빈 스 택 : Push top , top 이 라 고 판단 합 니 다.
코드 구현:
bool isValid(char * s)
{
    Stack S;
    StackInit(&S);
    int n=strlen(s);
    for(int i=0;i<n;++i)
    {
        if(s[i]=='(')
        {
            StackPush(&S,')');
        }
        if(s[i]=='[')
        {
            StackPush(&S,']');
        }
        if(s[i]=='{')
        {
            StackPush(&S,'}');
        }
        if(s[i]==' ')
        {
           continue;
        }
        if(s[i]==')'||s[i]==']'||s[i]=='}')
        {
            if(StackTop(&S)==s[i])
            { 
                StackPop(&S);
            }
            else
            {
                return false;
            }
        }
    }
    if(S.top==0)
    {
        return true;
    }
    else
    {
        return false;
    }
}

좋은 웹페이지 즐겨찾기