파이썬에서 주어진 문자열에서 가장 긴 유효한 괄호의 길이를 찾는 프로그램

문자열 s가 있다고 가정합니다. 여는 괄호와 닫는 괄호로만 구성됩니다. 가장 긴 유효(잘 구성된) 괄호 부분 문자열의 길이를 찾아야 합니다. 따라서 입력이 "))(())())"와 같으면 유효한 문자열이 "(())()"이므로 결과는 6이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 스택을 만들고 -1을 삽입하고 다음을 설정합니다. :=0

• 범위 0에서 스택 길이 – 1에 있는 i의 경우

  • s[i]가 괄호를 여는 경우 i를 스택에 삽입합니다.

  • 그렇지 않으면

    • 스택이 비어 있지 않고 스택의 맨 위가 -1이 아니고 s[stack top]이 여는 괄호인 경우

      • 스택의 최상위 요소

      • ans :=ans 및 i의 최대값 – 스택 상단

    • 그렇지 않으면 i를 스택에 삽입

• 반환

예시

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

class Solution(object):
   def solve(self, s):
      stack = [-1]
      ans = 0
      for i in range(len(s)):
         if s[i] == "(":
            stack.append(i)
         else:
            if stack and stack[-1]!=-1 and s[stack[-1]] == "(":
               stack.pop()
               ans = max(ans,i - stack[-1])
            else:
               stack.append(i)
      return ans
ob = Solution()
print(ob.solve("))(())())"))

입력

"))(())())"

출력

6