[파이썬] 괄호 짝 판별

4종류의 괄호 문자들 '()', '[]', '{}', '<>'로 이루어진 문자열이 주어진다.

이 문자열에 사용된 괄호들의 짝이 모두 맞는지 판별하는 프로그램을 작성한다.

 

조건:

1. 괄호의 종류 : 대괄호 '[]', 중괄호 '{}', 소괄호 '()', 화살괄호 '<>'

2. 왼쪽 괄호의 개수와 오른쪽 괄호의 개수가 같아야 한다.

3. 같은 괄호에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나와야 한다.

4. 괄호 사이에 포함 관계만 존재한다.

 

스택을 이용한 구현 방법 :

1. 배열에 있는 괄호를 차례대로 조사

2. 왼쪽 괄호를 만나면 스택에 삽입

3. 오른쪽 괄호를 만나면 스택에서 top 괄호를 삭제한 후, 오른쪽 괄호와 짝이 맞는지 검사

4. 스택이 비어 있으면 조건2 또는 조건3에 위배되고 괄호의 짝이 맞지 않으면 조건4에 위배

5. 마지막 괄호까지를 조사한 후에도 스텍에 괄호가 남아 있으면 조건2에 위배

 

by SW expert academy

C언어로 구현한 풀이다.

i가 괄호가 들어있는 배열 input의 길이인 것 같은데 왜 뒤에서 부터 검사하는지 모르겠다.

조건문은 열린 괄호면 stack에 push하도록 해놓고..?

 

 

❤ 나의 풀이

tc=int(input())   # 테스트 케이스

for t in range(tc):
  in_lst=input()		# 괄호 입력
  size=len(in_lst)
  stack=[0]*size
  top=0
  pair={}    # 딕셔너리 생성
  pair[')']='('
  pair[']']='['
  pair['}']='{'
  i=0

  while i != size :
    if in_lst[i] == '(' or in_lst[i] == '[' or in_lst[i] == '{' :       # 열린 괄호라면
      stack[top]=in_lst[i]    # push
      top+=1
    else:
      if top == 0 :   # 짝 지을 괄호가 없으므로 무효
        break
      elif stack[top-1] == pair[in_lst[i]] :    # 짝 검사
        top-=1              # pop
      else:
        break
    i+=1
    
  if size == i and top == 0 :
    print("1\n")    # 올바른 괄호
  else:
    print("0\n")    # 올바르지 않은 괄호

 

index error 생길 줄 알고 while i != size-1로 했더니 올바른 괄호일 때 top이 1이 나왔다. top이 0이 되어야 하는데.

생각해보니 i의 증가가 반복문 끝부분에 이루어져서 size-1 해 줄 필요가 없다.

 

 

 

 

참고 SW expert academy