대기 규방: 괄호 일치 분석

원제
주어진 문자열, 출력 괄호가 일치하는지 여부, 예를 들어

1. "()" yes； 2. ")(" no； 3. "(abcd(e)" no； 4. "(a)(b)" yes。

반드시 귀속으로 써야 하며, 전체 실현에 순환 문장이 나타나서는 안 된다.

// 
bool ispairs(string str)
{
	int len = str.length();
	if(len <1)return true;
	stack<char> stk;
	for(int i = 0; i < len; i++)
	{
		if(str[i] == ')')
			if(stk.empty())
				return false;
			else
				stk.pop();
		else if(str[i] == '(')
			stk.push(')');
	}
	return stk.empty();
}
// 
bool ispairs(string str, int left, int right)
{
	if(left < right)return false;
	int len = str.length();
	if(len < 1) return left == right;
	if(str[0] == '(') left++;
	else if(str[0] == ')')right++;
	return ispairs(str.substr(1), left, right);
}

분석
이 문제는 많은 학우들이 보았는데 만약에 뒤의 조건이 없다면 입을 벌리고 창고로 실현하겠다고 말했다. 시간 복잡도 O(n), 공간 복잡도 O(n).이것은 아주 좋은 해답입니다. 문제없습니다.그러나 우리는 면접 문제를 풀고 면접을 준비하는 과정에서 모든 문제가 단지 어떤 방법에만 국한되어서는 안 된다.더 많은 사고방식을 시도해야 한다. 비록 어떤 사고방식의 시간, 공간의 복잡도는 그리 좋지 않지만 변화를 가져올 수 있다. 하나는 반셋이다. 이것이야말로 진정한 수확이다.
이 문제는 귀속 문장만 사용할 수 있고 순환 문장이 나타나지 않도록 요구한다.이럴 때 우리는 어떻게 처리해야 합니까?사실은 모두에게 귀착을 알려주고 비교적 생각했다. 어떻게 문제와 하위 문제를 정의할 것인가.
문자열의 괄호가 일치하면'('의 수량과')'의 수량은 같고, 반대로 같지 않습니다.이렇게 하면 귀속하는 과정에서'('의 수량과')'의 수량이 일치하는지 기록하는 변수를 저장할 수 있다.이렇게 귀속 문제 f(p,count)를 정의하면 현재 문자 p 이전의 문자열에서'('의 수량과')'의 수량의 일치 상황을 나타내고, p는 현재 문자의 바늘을 가리킨다.처음에 f(p,0)는 다음과 같이 귀속됩니다.

1.  p ， count 0， 0， ； 0， ； 2.  ， p， p='('， f(p++, count++); p=')'， f(p++, count--)。 p ， '(' ')'， f(p++, count)，count ， 。 count>=0.

사실 귀착의 문제는 때때로 그렇게 비슷하지 않아서 여러분의 끊임없는 연습이 필요합니다.괄호가 일치하는 경우를 count로 기록하지 않으면, 이 문제의 귀속도 생각하지 않습니다.