일반 괄호 시퀀스는 하나 이상의 유형의 여는 괄호와 닫는 괄호로 구성되며 각 여는 괄호에는 닫는 괄호가 있으며 유형이 여러 개인 경우 유형이 겹치지 않습니다.
올바른 SP:
( ( ) ) ( ) ( )
{ } [ ( ) ] ( )
{ [ ( { } ) ] }
잘못된 SP:
) ) ( ( ) ) ( (
{ [ ( ] ) }
( ( ] }
대괄호의 대괄호 순서가 같은 유형인지 확인하려면 균형을 확인하면 됩니다.
즉, 0(균형)과 같은 변수를 시작합니다. 그런 다음 문자열을 실행하여(이 작업을 수행하는 방법을 모르는 경우 - RUN, STUPID!) 여는 괄호를 만나면 균형을 높이고 닫는 괄호를 만나면 줄입니다. 어느 단계에서든 잔액이 마이너스가 되거나 마지막에 0이 아니면 순서가 잘못된 것입니다.
|
여러 유형의 괄호가 있는 경우 모든 것이 조금 더 복잡해집니다. 그 균형 변수 역할을 할 스택을 생성합니다. 괄호는 겹칠 수 없기 때문에 필요합니다. 줄을 따라가다가 여는 괄호를 만나면 스택에 밀어 넣습니다. 닫는 중괄호를 만나면 해당 유형의 여는 중괄호를 스택에서 꺼내려고 합니다. 다른 유형의 중괄호가 스택에 있는 경우 시퀀스가 유효하지 않습니다. 스택이 마지막에 비어 있지 않으면 시퀀스도 유효하지 않습니다.
|
올바른 대괄호 시퀀스의 생성은 검사가 수행되는 방식에서 직접 따릅니다. 정확성을 위반하지 않고 새 대괄호를 추가하기만 하면 됩니다. 이것은 재귀 반복에 의해 수행됩니다. 당신이 그를 모른다면 - BE ... 아, 아니, 더 읽어서 이해하려고 노력할 수 있습니다. 다음은 한 유형의 대괄호에 대한 코드 샘플입니다.
#include <벡터>
#include <iostream>
사용 네임스페이스 std;
정수 n; // 절반 길이
벡터<문자> 답변 // 우리의 대답
무효 rec(int 잔액) {
if (ans.size() == 2 * n) { // 만약 그렇다면, 우리는 완료 < /span>
for (int i = 0; i < 2 * n; i++)
cout << ans[i] << " ";
cout << "\n";
}
if (ans.size() + balance + 2 <= n * 2) { // 확인합니다. 새 여는 중괄호를 닫도록 하겠습니다
// 이제 손을 조심하세요: 각 시퀀스에 대해 별도의 벡터를 만들 필요가 없습니다
ans.push_back('(');
rec(잔액 + 1);
ans.pop_back(); // 이를 이해하려면 재귀에 대해 알아야 합니다. 먼저 벡터에 괄호를 추가한 다음 이 모든 코드를 다시 실행합니다.
// 즉, 가능하면 괄호를 다시 추가합니다.
// 이것은 재귀를 종료하기 시작할 때까지, 즉 원하는 길이에 도달할 때까지 발생합니다.
// 그러면 괄호가 제거되기 시작합니다. 당신이 이것을 이해한다면-축하합니다. 당신은 굉장합니다.
}
if (balance > 0) { // 괄호를 닫을 수 있으면 닫습니다.
ans.push_back(')');
rec(균형 - 1);
ans.pop_back();
}
}
int 메인()
{
cin>> N;
rec(0);
반품 0;
}
그리고 이제 어려움의 시간입니다. 여러 유형의 괄호에 대한 알고리즘을 직접 작성해야 합니다! 무아하하하하하하하하하!
|