1. 스택(Stacks)
스택은 자료를 보관하는 선형 구조 중 하나로, 한 쪽에서 밀어 넣고(Push) 같은 쪽에서 뽑아내는(Pop) 식으로 작동한다. 입구와 출구가 같다 보면 된다.
따라서 나중에 들어간 데이터가 먼저 빠져나올 수 있다는 뜻에서 후입선출(Last In First Out, LIFO)의 특징을 갖는다고 한다.
2. 스택의 동작 예
스택을 S라 하자. push, pop 연산은 아래와 같이 이루어진다.
단, 비어있는 스택에서 원소를 꺼내려 하거나(Stack underflow), 가득 찬 스택에 원소를 집어넣으려 할 때(Stack overflow)는 오류가 발생한다.
3. 스택의 구현
스택은 배열을 이용하거나 연결리스트를 이용해 구현할 수 있다.
전자의 경우 파이썬에서 제공하는 리스트와 그 메서드들을 사용하고, 후자의 경우 이중 연결리스트 클래스와 멤버함수를 정의해 사용한다.
스택에 사용되는 연산은 아래와 같이 정의한다.
- size(): 현재 스택에 들어있는 데이터 원소의 수
- isEmpty(): 현재 스택이 비어있는가?
- push(x): x를 스택에 추가
- pop(): 맨 위에 저장된 데이터 원소 제거 & 반환
- peek(): 맨 위에 저장된 데이터 원소 반환. 제거는 하지 않음
3-1. 배열로 구현한 스택
class ArrayStack:
def __init__(self):
self.data = []
def size(self):
return len(self.data)
def isEmpty(self):
return self.size() == 0
def push(self, item):
self.data.append(item)
def pop(self):
return self.data.pop()
def peek(self):
return self.data[-1]3-2. 이중 연결 리스트로 구현한 스택
노드 클래스 Node 와 이중 연결 리스트 DoublyLinkedList는 이전 포스팅을 참고한다.
class ArrayStack:
def __init__(self):
self.data = []
def size(self):
return len(self.data)
def isEmpty(self):
return self.size() == 0
def push(self, item):
self.data.append(item)
def pop(self):
return self.data.pop()
def peek(self):
return self.data[-1]
class LinkedListStack:
def __init__(self):
self.data = DoublyLinkedList()
def size(self):
return self.data.getLength()
def isEmpty(self):
return self.size() == 0
def push(self, item):
node = Node(item)
self.data.insertAt(self.size() + 1, node)
def pop(self):
return self.data.popAt(self.size())
def peek(self):
return self.data.getAt(self.size()).data4. 스택의 활용
4-1. 수식의 괄호 유효성 검사
괄호는 여는 괄호와 닫는 괄호가 짝이 맞아야 한다. (A+B)나 {(A+B) * C}는 맞지만 )A+B)라거나 {[A + B} * C)는 맞지 않다.
이렇게 괄호가 유효한지 검사하는데 스택이 쓰일 수 있다.
식을 앞에서부터 한 글자씩 읽어가며 왼 괄호를 만난다면 스택에 넣는다. 오른 괄호를 만났을 때 스택이 비어있으면 틀린 수식이며, 비지 않았다면 pop을 해 그 요소가 일치하는 왼 괄호가 아니면 틀린 수식이다.
문자열 끝까지 검사했을 때 스택이 비어있어야 올바른 수식이다.
스택을 배열로 구현하고 이를 활용한 코드는 아래와 같다. ArrayStack 클래스는 상단의 코드를 참고한다.
def solution(expr):
match = {
')': '(',
'}': '{',
']': '['
}
S = ArrayStack()
for c in expr:
if c in '({[':
S.push(c)
elif c in match:
if S.isEmpty():
return False
else:
t = S.pop()
if t != match[c]:
return False
return S.isEmpty()4-2. 수식의 후위 표기법
수식을 표현하는 데는 중위 표기법과 후위 표기법이 존재한다.
중위 표기법(infix notation)은 우리가 일상적으로 사용하는 표기법으로, 연산자가 피연산자들의 사이에 위치한다. (A+B)*(C+D) 식이다.
반면 후위 표기법(postfix notation)은 연산자가 피연산자들의 뒤에 위치하며, AB+CD+*의 식이다. 앞에 나오는 연산자들부터 연산을 수행하며, 괄호가 필요 없다.
중위 표현식을 후위 표현식으로 바꾸는 것을 스택으로 구현 가능하다.
(A+B)*(C+D) → AB+CD+*
A*(B-(C+D)) → ABCD+-*
(A+(B-C))*D → ABC-+D*
① 연산자의 우선순위 설정
+, - 연산은 *, / 연산보다 우선순위가 낮다. 또한 왼괄호의 우선순위를 +, -보다 낮게 설정하면 연산자를 만났을 때 왼괄호를 넘어가지 않도록 할 수 있다.
따러서 prec라는 딕셔너리를 선언해 연산자 우선순위가 높을 수록 value 값을 높게 설정해둔다.
② 중위 표현식을 왼쪽부터 한 글자씩 읽음
- 피연산자이면 그냥 출력한다.
(이면 스택에 push한다.)이면(이 나올 때까지 pop하고 출력한다.- 연산자이면 스택에서 높거나 같은 우선순위의 연산자들을 pop하고 출력하고, 이 연산자는 스택에 push한다.
③ 스택에 남아있는 연산자는 모두 pop하고 출력
아래는 코드 구현 결과이다. ArrayStack 클래스는 상단의 코드를 참고한다.
prec = {
'*': 3, '/': 3,
'+': 2, '-': 2,
'(': 1
}
def solution(S):
opStack = ArrayStack()
answer = ''
for s in S:
if s == '(':
opStack.push(s)
elif s == ')':
while opStack.peek() != '(':
answer += opStack.pop()
opStack.pop()
elif s in prec.keys():
while not opStack.isEmpty() and prec[opStack.peek()] >= prec[s]:
answer += opStack.pop()
opStack.push(s)
else:
answer += s
while not opStack.isEmpty():
answer += opStack.pop()
return answer4-3. 후위 표기 수식의 계산
중위 표기된 식을 후위 표기로 바꾸었다면, 후위 표기 식을 계산하는 것도 스택으로 가능하다.
앞에 나오는 두 피연산자가 뒤에 나오는 연산자의 피연산자이므로, 피연산자가 나오면 스택에 넣고, 연산자를 만나면 pop하여 연산을 진행한 뒤 push한다.
뺄셈과 나눗셈은 전후 순서가 중요하므로 나중에 pop한 피연산자가, 즉 먼저 들어간 피연산자가 연산의 앞에 오도록 하는데 주의한다.
① 후위 표현식을 왼쪽부터 한 글자씩 읽음
- 피연산자이면 push
- 연산자이면 pop 2개 하고,
(나중 피연산자) (연산자) (먼저 연산자)를 계산해 push. 예를 들자면 가장 아래 요소부터4,3이고 연산자가-일 때3 - 4를 계산한다.
② 수식 끝에 도달하면 pop하고 이것이 계산 결과임
# 수식을 숫자와 연산자를 구분해 한 글자씩 리스트에 넣어 반환하는 함수
def splitTokens(exprStr):
tokens = []
val = 0
valProcessing = False
for c in exprStr:
if c == ' ':
continue
if c in '0123456789':
val = val * 10 + int(c)
valProcessing = True
else:
if valProcessing:
tokens.append(val)
val = 0
valProcessing = False
tokens.append(c)
if valProcessing:
tokens.append(val)
return tokens
# 중위 표기법을 후위 표기법으로 변환하는 함수
def infixToPostfix(tokenList):
prec = {
'*': 3,
'/': 3,
'+': 2,
'-': 2,
'(': 1,
}
opStack = ArrayStack()
postfixList = []
for token in tokenList:
if token == '(':
opStack.push(token)
elif token == ')':
while opStack.peek() != '(':
postfixList.append(opStack.pop())
opStack.pop()
elif token in prec.keys():
while not opStack.isEmpty() and prec[opStack.peek()] >= prec[token]:
postfixList.append(opStack.pop())
opStack.push(token)
else:
postfixList.append(token)
while not opStack.isEmpty():
postfixList.append(opStack.pop())
return postfixList
# 후위 표기법의 수식을 계산하는 함수
def postfixEval(tokenList):
valStack = ArrayStack()
for token in tokenList:
if type(token) is int:
valStack.push(token)
else:
operand2 = valStack.pop()
operand1 = valStack.pop()
if token == '+':
valStack.push(operand1 + operand2)
elif token == '-':
valStack.push(operand1 - operand2)
elif token == '*':
valStack.push(operand1 * operand2)
elif token == '/':
valStack.push(operand1 / operand2)
return valStack.pop()
def calcExpr(expr):
tokens = splitTokens(expr)
postfix = infixToPostfix(tokens)
val = postfixEval(postfix)
return val5. 라이브러리 활용
파이썬에서는 stack 자체가 리스트와 연산이 동일하다. 앞서 본 것처럼 append 메서드가 push의 역할을 하고 pop은 그대로 pop 메서드가 지원한다. 맨 위 요소를 리턴하는 peek은 [-1] 인덱스를 불러와 사용할 수 있다.
C++의 경우 표준 라이브러리 <stack>을 통해 스택 자료구조를 제공한다. #include <stack>으로 불러와 stack<자료형> 스택명으로 선언한다.
push(요소), pop(), size(), empty() 함수가 있으며, peek()는 top()의 이름을 가지고 있다.
