[자료구조] 스택(Stack)이란? 스택을 활용해 괄호쌍 확인하기

목표

저번 포스팅에서 간단히 알아봤던 스택(Stack)에 대해서 복습하고 실습을 통해 자세히 이해하도록 하겠습니다.

 

목차                                                                                  클릭하면 해당 목차로 이동합니다.

스택(Stack) 이란?

 

연습 문제: 괄호 맞추기

 

정리

 

개요

저번 포스팅에서 순차적 자료구조(Sequential Data Structure)에 대해서 알아보았습니다.

참고 - [자료구조] 순차적 자료구조, 배열과 리스트의 이해

그 중에서도 배열과 리스트에 대해서 자세히 알아보았는데요. 이 과정에서 스택, 큐, 디큐에 대해서 잠깐 언급했었습니다. 이번 포스팅에서는 스택에 대해서 자세히 알아보도록 하겠습니다.

 

스택(Stack)이란?

어떤 자료구조든 삽입·삭제·탐색 기능을 제공합니다. 스택에서는 Push(삽입), Pop(삭제)를 비롯한 Top(맨 위에 있는 값 반환), Len(스택의 데이터 개수)까지 4가지 기능을 활용할 수 있습니다.

물론, 앞서 배운 파이썬의 리스트에서 append, pop(매개변수X)를 활용해서 스택을 구현할 수 있습니다. 하지만, 리스트의 경우 많은 기능을 제공하기도 하고 개발자가 실수로 다른 함수를 사용할 여지가 있기 때문에 지양하는 것입니다.

 

스택은 LIFO(Last In First Out) 구조를 가집니다. 제일 마지막에 Push된 데이터가 가장 먼저 Pop된다는 뜻입니다.

조금만 찾아봐도 다양한 예시를 찾을 수 있는데, 자루나 접시 쌓는 것에 많이 비유하는 것 같습니다. 접시를 차곡차곡 쌓으면 위에서 부터 쌓이고 가져갈 때는 위에 있는 접시를 가져가는 것과 유사합니다. 꼭 두번째 접시를 가져가는 사람들이 있지만요.

그림으로 나타내면 대략 다음과 같습니다.

▲ 스택 구조(LIFO)

1, 7, -2, 4 순서대로 스택에 들어왔겠지만(Push), 나갈때는(Pop) 반대로 4부터 나가는 것입니다. 

 

코드 구현: 파이썬(Python)

파이썬의 클래스를 이용해서 스택을 구현해보겠습니다. 스택은 Push, Pop, Top, Len 4가지 기능을 한다고 말씀 드렸습니다. 생성자 __init__을 포함해 총 5개의 멤버함수가 필요하겠네요. 코드로 구현하면 다음과 같습니다.

▲ 파이썬으로 구현한 스택(Stack) 클래스

__Init__

객체를 생성하면 먼저 생성자가 자동으로 실행됩니다. 이 과정에서 item이라는 멤버리스트를 갖게됩니다.

이 리스트에 append, pop을 활용해서 스택 구조를 나타냈습니다.

push

매개변수로 넘어온 X를 스택에 추가하는 것입니다. 위에서 본 그림처럼 위에서부터 차곡차곡 쌓이게 됩니다.

pop

이 멤버함수가 실행되면 맨 위에 있는 데이터를 제거하게됩니다. 원래 리스트의 pop()함수는 마지막 값을 제거하고 반환하지만 함수에 return은 사용하지 않았기 때문에 반환되지는 않습니다.

보시면 try - except 문으로 예외처리가 되어있는 것을 확인할 수 있습니다. 값을 제거하려고 봤는데 스택에 아무 데이터도 없으면 런타임 에러가 발생할 수 있습니다. 따라서 예외 처리를 해서 에러를 우아하게 관리할 수 있습니다.

top

스택의 맨 위에 있는 데이터를 반환하게 됩니다. 가장 최근에 Push된 데이터가 되겠죠? 마찬가지로 스택에 아무 데이터도 없으면 반환할 데이터가 없기 때문에 런타임 에러가 발생할 여지가 있습니다. 따라서, 예외처리를 해줬습니다.

len_stack

스택은 len을 통해서 스택에 있는 데이터 개수를 알려줄 수 있다고 말씀드렸습니다. 파이썬 내장 함수에 len이 존재하기 때문에 겹치지 않게 len_stack으로 변수명을 지었습니다.

 

연습 문제: 괄호 맞추기

스택을 활용한 문제 1번은 괄호 맞추기 입니다. 수식을 입력할 때 우선 순위 및 가독성을 위해서 괄호를 사용하는데요. 스택을 활용해서 괄호의 쌍이 맞는지 확인할 수 있습니다.

 

입력 : 소괄호, 중괄호, 대괄호 쌍

출력 : 괄호 쌍이 맞을 경우 True, 틀릴 경우 False예시 : [{(())()}] → True , (()(()( → False 

 

실제 수식을 입력하는 경우에도 괄호 쌍이 맞는지 확인할 수 있지만, 다음 포스팅에서 계산기를 다루기 때문에 이번 예시에서는 괄호쌍만 입력받도록 하겠습니다.

 

답안

우선 코드를 작성하기 전에 생각을 해야합니다. 어떻게 문제를 해결할 수 있을까요?

괄호쌍이 입력 될 때 여는 괄호가 입력되면 그 다음 입력되는 닫는 괄호와 한 쌍을 이룹니다. 다시 말해서 가장 나중에 입력된 여는 괄호와 제일 최근에 입력되는 닫는 괄호가 한 쌍을 이룬다는 말입니다. 이 말은 즉슨, 스택에 Top에 저장되어 있는 가장 마지막에 들어온 여는 괄호와 지금 입력되는 닫는 괄호가 한 쌍을 이룬다는 뜻입니다.

말로 하니까 살짝 복잡해보이는데요. 직접 괄호를 그려보면서 하면 이해하기 수월합니다.

 

그래서 제가 생각했던 해결 방안은 여는 괄호가 나오면 Push하고, 닫는 괄호가 나오면 pop 하는 것입니다. 괄호쌍이 맞는다면 마지막에 스택의 크기는 0이 되어야합니다. Push된 여는 괄호가 닫는 괄호를 만나 Pop되었기 때문입니다. 다만, 지금 입력되는 것은 소, 중, 대괄호 3종류이기 때문에 각자 종류가 맞아야합니다. 그래도 다행인 점은 대괄호가 열리고 뜬금 없이 닫는 소괄호만 나온다면 당연히 쌍이 안맞기 때문에 여는 괄호가 나오면 그냥 Push하면 해결할 수 있습니다.

 

위에서 작성한 Stack 클래스는 존재한다고 가정하겠습니다.

먼저, Stack 객체를 생성해야합니다. 그 이후 괄호쌍을 입력받아야합니다.

S = Stack() #Stack 객체 생성
paren = input("괄호 입력:") #괄호쌍 입력

paren은 괄호(parentheses)의 약자입니다.

 

▲괄호 쌍 맞추기

입력된 문자열은 for ~ in 을 통해서 한 문자씩 확인할 수 있습니다.

한 문자씩 확인해서 여는 괄호가 나오면 바로 Push합니다. 닫는 괄호가 나온다면 각자 종류가 맞는 여는 괄호가 스택의 Top에 있는지 확인합니다. 만약, 쌍이 맞지 않는다면 바로 False를 출력하고 프로그램을 종료합니다.

 

이렇게 반복문을 통해서 쌍을 확인하고 나오면 반복문을 통해서 최종으로 확인합니다.

왜냐하면 "()(((" 처럼 여는 괄호만 남아있을 경우 반복문 안에서 걸러지지 않기 때문입니다. 따라서 스택의 길이가 0일 경우 True를 출력하고 아니면 False를 출력하고 프로그램을 종료합니다.

 

결과를 확인해보도록 하겠습니다.

▲괄호 맞추기 결과(True)

▲ 괄호 맞추기 결과(False)

제가 조금 애매하게 써놓은 것 같은데, } False라는 것은 중괄호의 괄호쌍이 안맞는 게 아니라, }가 입력되는 순간에 쌍이 안맞아서 False를 반환한다는 의미입니다.

 

 

정리

이번 포스팅에서는 스택이 무엇인지에 대해 알아보고 괄호 맞추기를 통해 예제를 풀어보았습니다. LIFO 구조를 갖고 위에서 데이터가 들어오고 위로 나가는 듯한 모양을 갖고 있습니다. 자료구조를 흉내만 내보고 제대로 틀을 갖춰서 코드를 작성한 것은 처음이라 좋은 경험이 되었던 것 같습니다.

 

다음 포스팅에서는 스택을 활용한 계산기를 만들어보도록 하겠습니다.

이 과정에서 전위 표기, 중위 표기, 후위 표기법에 대해서 알아보도록 하겠습니다.

 

*한국외대 신찬수 교수님의 Data Structures with Python 강의를 참고하여 포스팅하였습니다.