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()).data

4. 스택의 활용

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 answer

4-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 val

5. 라이브러리 활용

파이썬에서는 stack 자체가 리스트와 연산이 동일하다. 앞서 본 것처럼 append 메서드가 push의 역할을 하고 pop은 그대로 pop 메서드가 지원한다. 맨 위 요소를 리턴하는 peek은 [-1] 인덱스를 불러와 사용할 수 있다.

C++의 경우 표준 라이브러리 <stack>을 통해 스택 자료구조를 제공한다. #include <stack>으로 불러와 stack<자료형> 스택명으로 선언한다.
push(요소), pop(), size(), empty() 함수가 있으며, peek()는 top()의 이름을 가지고 있다.