[자료구조] 스택 - 괄호 검사 알고리즘

728x90

 

 

 

🙆‍♂️ 괄호 검사 알고리즘

---

"""
괄호 검사 알고리즘
"""
def checkB(string):
    stack = []
    for i in string:
        if i in ['(','{','[']:
            stack.append(i)
        elif i in [')','}',']']:
            if len(stack) == 0:
                return "Wrong String!"
            else:
                if ((
                    stack[-1] == '(' and i==')'
                    or stack[-1] == '{' and i=='}'
                    or stack[-1] == '[' and i==']'
                )):
                    stack.pop(-1)
                else:
                    return "Wrong String!"
    if len(stack) != 0:
        return "Wrong String!"
    else:
        return "Good String!"
    
string = input("input string : ")
ans = checkB(string)
print(ans)

스택을 이용해서 괄호 검사 알고리즘을 만들 수 있습니다.

 

소,중,대 여는 괄호가 입력되면 if문으로 감지하여 stack에 넣고

소,중,대 닫는 괄호가 입력되면 스택이 비어있나 검사를 한 후

해당 괄호와 일치한다면 스택의 최상단

즉, 리스트로 치면 최후단 값을 지워서 괄호 하나가 정상적으로 닫혔음을 알려줍니다.

 

위 과정 중 맞지 않는 결과가 나온다면 잘못된 괄호식임을 인지하고 Wrong String!을 출력합니다!