Python에서 유효한 괄호를 확인하는 방법

이 자습서에서는 Python에서 유효한 괄호를 확인하는 방법을 배웁니다.

일련의 괄호가 주어지면 괄호 조합이 유효한지 확인하는 것은 인기 있는 코딩 면접 질문입니다. 그리고 앞으로 몇 분 동안 이 질문을 해결하고 주어진 문자열의 유효성을 검사하는 Python 함수를 코딩하는 기술을 배우게 됩니다.

유효한 괄호 문제는 무엇입니까?

유효한 괄호 문제는 무엇입니까?라는 질문에 답하여 토론을 시작하겠습니다.

단순 괄호, 중괄호 및 대괄호 문자를 포함하는 문자열이 제공됩니다. () [] {}, 주어진 괄호 조합이 유효한지 확인해야 합니다.

유효한 괄호 문자열은 다음 두 가지 조건을 충족합니다.

모든 여는 대괄호에는 동일한 유형의 일치하는 닫는 대괄호가 있어야 합니다.

브래킷은 올바른 순서로 닫아야 합니다.

다음은 유효하거나 유효하지 않은 괄호 문자열의 몇 가지 예입니다.

test_str = "{}]" --> INVALID, ] was never opened
test_str = "[{}]" --> VALID
test_str = "[]" --> VALID
test_str = "[]{}" --> VALID
test_str = "[{]}" --> INVALID, brackets closed incorrectly!

우리의 문제 해결 접근 방식에서 스택은 중추적인 역할을 할 데이터 구조입니다. 다음 섹션에서 스택의 기본 사항을 검토해 보겠습니다.

스택 데이터 구조 재검토

스택은 LIFO(Last In First Out) 데이터 구조로, 스택 맨 위에 요소를 추가하고 스택 맨 위에서 제거할 수도 있습니다.

스택 상단에 요소를 추가하면 푸시 작업을 수행하고 스택 상단에서 요소를 제거하면 팝 작업을 수행합니다.

다음 두 가지 규칙을 사용하여 괄호 문자열에 대해 수행할 수 있는 일련의 작업을 생각해 보겠습니다.

모든 여는 브래킷을 스택에 밀어 넣습니다.
닫는 대괄호를 발견하면 스택 상단을 팝니다.

유효한 괄호 검사 문제를 해결해 봅시다.

유효한 괄호를 확인하는 방법

위의 예에서 얻은 모든 관찰을 종합하면 다음과 같습니다.

괄호 문자열의 길이 확인: 홀수이면 문자열이 유효하지 않습니다.

모든 여는 대괄호에는 닫는 대괄호가 있어야 하므로 유효한 문자열에는 짝수의 문자가 포함되어야 합니다. 문자열의 길이가 홀수인 경우 잘못된 괄호 조합이 있다는 결론을 즉시 내릴 수 있습니다.

# len(test_str) = 3 (odd); ] does not have an opening [
test_str = "{}]"

# len(test_str) = 3 (odd); ( does not have a closing )
test_str = "[(]"

# len(test_str) = 5 (odd); there's a spurious )
test_str = "{())}"

다음으로, 문자열의 문자 수가 짝수일 때 대처하는 방법을 살펴보겠습니다.

Tik Tok 포스트에 음악을 추가하는 방법

괄호 문자열의 길이는 짝수입니다. 다음은 무엇입니까?

1단계: 문자열을 왼쪽에서 오른쪽으로 탐색합니다. 문자열 test_str과 문자열 char의 개별 문자를 호출해 보겠습니다.

2단계: 첫 번째 문자 char가 여는 대괄호(, { 또는 [, push it to the top of the stack and proceed to the next character in the string.

Step 3: Now, check if the next character (char) is an opening or a closing bracket.

Step 3.1: If it’s an opening bracket, push it again onto the stack.

Step 3.2: If you encounter a closing bracket instead, pop off the stack top, and proceed to step 4.

Step 4: Here again, there are 3 possibilities based on the value popped off the stack:

Step 4.1: If is an opening bracket of the same type, loop back to step 3.

Step 4.2: If it is an opening bracket of a different type, you can again conclude that it is not a valid parentheses string.

Step 4.3: The final possibility is that the stack is empty. Again, this is the case of an invalid string, as you’ve run into a closing bracket that doesn’t have a matching opening bracket.

Valid Parentheses String Examples Walkthrough

Now let’s take three examples and walk through the above steps.

📑 If you’ve already gotten the hang of how this works, feel free to skip to the next section.

#1. As a first example, let test_str = “{()”.

{ is the first character, and it’s an opening bracket, so you push it to the stack.
The next character ( is also an opening bracket, so go ahead and push it onto the stack as well.
The third character in the string ) is a closing bracket, so you have to pop off the stack top, which returns (.
At this point, you’ve reached the end of the string. But the stack still contains the opening { , which was never closed. So the given parentheses string test_str is invalid.

작성하기 어려운 이메일을 위해 자동 생성된 템플릿을 사용하여 영감 얻기

#2. In this second example, let test_str = “()]”

첫 번째 문자( 여는 대괄호이며 스택에 밀어 넣습니다.
두 번째 문자 )는 닫는 대괄호입니다. ) – 같은 유형의 여는 브래킷입니다. 다음 캐릭터로 넘어갑니다.
세 번째 문자 ]는 닫는 대괄호이며 스택 맨 위에서 다시 튀어 나와야 합니다. 그러나 보시다시피 스택은 비어 있습니다. 이는 일치하는 여는 괄호가 없음을 의미합니다. [. Hence, this string is invalid.

#3. In this final example, test_str = “{()}”.

The first two characters {( are opening brackets, so push them onto the stack.
The third character is a closing ), so pop off the stack top – (.
The next character } is a closing curly brace, and when you pop the stack top, you get { – an opening curly brace.
After you have traversed the entire string, the stack is empty and test_str is valid! ✅

📌 I’ve put together the following flowchart outlining the steps in the valid parentheses checking problem. You may save it for quick reference!

In the next section, let’s see how to translate our concept to Python code.

Python Program to Check for Valid Parentheses

In Python, you can use the list to emulate a stack.

You can use the .append() method to add elements to the end of the list. This is similar to pushing to the top of the stack.

The .pop() method returns the last element from the list, and this is similar to the popping off the top of the stack – to remove the last-added element.

So you now know how to implement the push and pop operations on a Python list, emulating the stack.

As a next step, let’s answer the question: how to differentiate between opening and closing brackets?

Well, you can use a Python dictionary – with the opening brackets ‘{‘, ‘[‘, ‘(‘ as the keys of the dictionary and the corresponding closing brackets ‘}’, ‘]’, ‘)’를 값으로 사용합니다. .keys() 메서드를 사용하여 사전의 개별 키에 액세스할 수 있습니다.

Microsoft Word 문서에 표절이 있는지 확인하는 방법

is_valid() 함수의 정의를 작성하기 위해 배운 모든 것을 사용합시다.

함수 정의 이해하기

함수 정의가 포함된 다음 코드 셀을 읽으십시오. 위의 설명과 함께 순서도의 단계를 사용했음을 알 수 있습니다.

또한 독스트링 포함:

기능에 대한 간단한 설명
함수 호출의 인수
함수의 반환 값

▶ help(is_valid) 또는 is_valid.__doc__를 사용하여 독스트링을 검색할 수 있습니다.

def isValid(test_str):
  '''Check if a given parentheses string is valid.

  Args:
    test_str (str): The parentheses string to be validated
  
  Returns:
    True if test_str is valid; else False 
  '''
  # len(test_str) is odd -> invalid!
  if len(test_str)%2 != 0:
    return False
  # initialize parentheses dict
  par_dict = {'(':')','{':'}','[':']'}
  stack = []
  for char in test_str:
    # push opening bracket to stack
    if char in par_dict.keys():
      stack.append(char)
    else:
      # closing bracket without matching opening bracket
      if stack == []:
          return False
      # if closing bracket -> pop stack top
      open_brac = stack.pop()
      # not matching bracket -> invalid!
      if char != par_dict[open_brac]:
        return False
  return stack == []

Python 함수 is_valid는 괄호 문자열이 유효한지 확인하고 다음과 같이 작동합니다.

is_valid 함수는 검증할 괄호 문자열인 test_str 하나의 매개변수를 받습니다. test_str 문자열이 유효한지 여부에 따라 True 또는 False를 반환합니다.
여기서 stack은 스택을 에뮬레이트하는 Python 목록입니다.
그리고 par_dict는 여는 대괄호를 키로 사용하고 닫는 대괄호를 해당 값으로 사용하는 Python 사전입니다.
문자열을 탐색하는 동안 괄호 문자열을 유효하지 않게 만드는 조건이 발생하면 함수는 False를 반환하고 종료됩니다.
문자열의 모든 문자를 순회한 후 스택 == [] 스택이 비어 있는지 확인합니다. 그렇다면 test_str이 유효하고 함수는 True를 반환합니다. 그렇지 않으면 함수는 False를 반환합니다.

이제 함수가 올바르게 작동하는지 확인하기 위해 몇 가지 함수 호출을 수행해 보겠습니다.

str1 = '{}[]'
isValid(str1)
# Output: True

str2 = '{((}'
isValid(str2)
# Output: False

str3 = '[{()}]'
isValid(str3)
# Output: True

str4 = '[{)}]'
isValid(str4)
# Output: False

str5 = '[[]}'
isValid(str5)
# Output: False

위의 코드 조각에서 함수가 예상대로 작동한다는 결론을 내릴 수 있습니다!

결론 🧑‍💻

학습한 내용을 간단히 요약하면 다음과 같습니다.

먼저 유효한 괄호 검사 문제에 대해 알아보았습니다.
다음으로 스택을 선택한 데이터 구조로 사용하여 문제를 해결하는 방법을 배웠습니다.
그런 다음 여는 대괄호, 키 및 해당 닫는 대괄호를 값으로 사용하여 Python 사전을 사용하여 괄호 조합을 검증하는 방법을 배웠습니다.
마지막으로 주어진 괄호 문자열이 유효한지 확인하는 Python 함수를 정의했습니다.

다음 단계로 koreantech.org의 온라인 Python 편집기에서 문제를 코딩해 보십시오. 도움이 필요하면 이 안내서를 다시 방문하십시오!

더 많은 Python 자습서를 확인하십시오. 즐거운 코딩!🎉