[Python] 괄호 매칭 검사 프로그램

괄호 매칭 검사 프로그램

들어가며

• 스택을 활용하여 간단하게 괄호의 매칭 검사를 수행할 수 있다.
• 여는 괄호를 만나면 push 하고, 닫는 괄호를 만나면 pop 한다 는 규칙을 적용한 후, push 또는 pop 하는 과정에서 다음의 조건을 확인하면 된다.

① 닫는 괄호를 만났을 때 스택은 비어 있지 않아야 한다.
② 닫는 괄호를 만났을 때 추출한 괄호는 여는 괄호여야 한다.
③ ②를 만족해도 두 괄호의 종류(소괄호, 중괄호, 대괄호)가 같아야 한다.
④ 모든 수식의 처리가 끝나면 스택은 비어 있어야 한다.

 

• 열린 괄호라면 무조건 push 한다.
• 닫는 괄호일 때는 스택에서 하나를 꺼내서 현재 괄호와 짝이 맞는지 확인한다.

if '(', '[', '{', '<' 중 하나면
    push()
elif ')', ']', '}', '>' 중 하나면
    열린 괄호 pop()
    if 두 괄호의 쌍이 맞으면
        통과
    else
        오류

 

• 그리고 모든 수식의 글자를 처리한 후, 다음과 같이 스택이 비었는지 확인한다.

if 스택이 비었으면
    정상
else
    오류

 

프로그램 구현

def isStackFull() :
    global SIZE, stack, top
    if (top >= SIZE-1) :
        return True
    else :
        return False
 
def isStackEmpty() :
    global SIZE, stack, top
    if (top == -1) :
        return True
    else :
        return False
 
def push(data) :
    global SIZE, stack, top
    if (isStackFull()) :
        print("스택이 꽉 찼습니다.")
        return
    top += 1
    stack[top] = data
 
def pop() :
    global SIZE, stack, top
    if (isStackEmpty()) :
        print("스택이 비었습니다.")
        return None
    data = stack[top]
    stack[top] = None
    top -= 1
    return data
 
def peek() :
    global SIZE, stack, top
    if (isStackEmpty()) :
        print("스택이 비었습니다.")
        return None
    return stack[top]
 
def checkBracket(expr) :
    for ch in expr:
        if ch in '([{<':
            push(ch)
        elif ch in ')]}>':
            out = pop()
            if ch == ')' and out == '(':
                pass
            elif ch == ']' and out == '[':
                pass
            elif ch == '}' and out == '{':
                pass
            elif ch == '>' and out == '<':
                pass
            else:
                return False
        else :
            pass
    if isStackEmpty() :
        return True
    else :
        return False
 
SIZE = 100
stack = [ None for _ in range(SIZE) ]
top = -1
 
if __name__ == "__main__" :
 
    exprAry = ['(A+B)', ')A+B(', '((A+B)-C', '(A+B]', '(<A+{B-C}/[C*D]>)']
 
    for expr in exprAry :
        top = -1
        print(expr, '==>', checkBracket(expr))

(A+B) ==> True
스택이 비었습니다.
)A+B( ==> False
((A+B)-C ==> False
(A+B] ==> False
(<A+{B-C}/[C*D]>) ==> True