[데이터 구조 --- 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;
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.