괄호 일치 분석 귀속 실현

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

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

요구는 반드시 귀속적으로 써야 하며, 전체적으로 하나의 순환문이 나타나서는 안 된다.
분석하다.
이 문제는 많은 학우들이 보았는데 만약에 뒤의 조건이 없다면 입을 열면 창고로 실현한다. 시간 복잡도 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로 기록하지 않으면 이 문제의 귀환도 좋지 않다.
http://www.ituring.com.cn/article/56304