2. 스택 (Stack)

본 포스팅은 아래의 출처를 참고하여 정리한 것입니다.
https://www.youtube.com/watch?v=PIidtIBCjEg&list=PLsMufJgu5933ZkBCHS7bQTx0bncjwi4PK&index=1

Stack

• 선입후출, LIFO (Last In First Out)
• 삽입: push
• 삭제: pop

• list의 append = stack의 push
• list의 pop = stack의 pop
  • list를 stack으로 곧바로 쓰지 않는 이유는, list는 삽입/삭제 연산 이외에 더 다양한 함수 제공하지만 stack은 삽입/삭제 딱 2가지만 제공
  • list를 쓰다가 다른 연산자로 자칫 실수할 수 있으므로 삽입/삭제만 필요한 경우에는 stack을 활용하도록
• (부가적인) 다른 연산 종류
  • top: stack의 맨 위의 값을 리턴, pop과 다른 점은 그 값을 지우지 않는다는 것
  • len: stack에 저장된 원소의 총 개수

code

class Stack:
	def __init__(self): # 생성 함수
    	self.items = [] # 데이터 저장을 위한 리스트 준비
        
    def push(self, val):
    	self.items.append(val)
        
    def pop(self):
    	try: # pop할 아이템이 있으면
        	return self.items.pop()
            
        except IndexError:
        	print("Stack is Empty")
    
    def top(self):
    	try:
        	return self.items[-1]
        except IndexError:
        	print("Stack is empty")
            
    def __len__(self): # len() 호출하면 stack의 item 수 반환
    	return len(self.items)

• push, pop, top, len: 모두 $O(1)$
  • len: self.items 라는 리스트에서 항상 몇 개인지 관리하고 있기 때문에 값만 리턴해주면 되기때문

---

Stack 예시 1 - 괄호 맞추기

• (2+5)*7-((3-1)/2+7)
• 괄호가 올바른 쌍으로 이루어져 있는지 맞추기
  • (()()) (O)
  • (()))( (X)

문제
입력: 왼쪽, 오른쪽 괄호의 문자열
출력: 괄호 쌍이 맞춰져있으면 True, 아니면 False 반환

• stack에서 왼쪽 괄호 push 해두고, 오른쪽 괄호를 만날 때까지 pop할 대기

  • 오른쪽 괄호 만났을 때 pop할 왼쪽 괄호가 없다면 올바른 괄호 쌍이 아닌 것

    • (()

  • 문자열 끝까지 갔을 때 stack이 비어있으면 올바른 괄호 쌍

    • (()())

  • 혹은, 문자열 끝까지 갔을 때 stack이 비어있지 않으면 올바른 괄호 쌍이 아닌 것

    • ()(

S = Stack()
for p in parseq:
	if p == '(': S.push(p)
    elif p == ')': S.pop() # 여기서 error 발생하면 오른쪽 괄호가 더 많다는 것
    else: print("Not allowed Symbol")
   		
if len(S) > 0: return False # 왼쪽 괄호가 더 많음
else: return True

---

Stack 예시 2 - 계산기 코드 작성

• 2 + 3 * 5 ➡️ '2', '+', '3', '*', '5'

  • '2', '3', '5': 피연산자(operand)
  • '+', '*': 연산자(operator)

• 연산자 우선순위에 따른 계산: (2 + (3 * 5)) = 17

• [예제에서 살펴볼 것] 이항 연산자 (binary operator)

  • 2 + 3 (operator가 2개의 피연산자 필요, 즉 이항이 필요)
  • 단항 연산자 (unary operator)
    • +3 -6 (이때 +는 3 하나만 필요하므로 단항 연산자, - 3과 6의 항 2개를 가지는 이항 연산자)

• infix 수식 ➡️ postfix 수식

  • 2 + 3 * 5 ➡️ 2 3 5 + *
  • 규칙 1. 우선순위에 따라 괄호 치기: ( 2 + ( 3 * 5 ) )
  • 규칙 2. 연산자의 오른쪽 괄호 다음으로 연산자 이동: ( 2 (3 5 ) * ) +
  • 규칙 3. 괄호 모두 지우기: 2 3 5 * +

infix ➡️ postfix 예시

• A + B * C ➡️ A B C * +

  • 1. 피연산자의 순서는 그대로
  • 2. 연산자는 뒤의 연산자에 따라 순서가 결정됨

    • +는 push 되었다가 더 높은 우선순위 만날 때까지 대기

    • *은 더 우선순위가 높은 연산자가 없으므로 push 됨

    • +는 자기보다 우선순위가 낮은 연산자를 만났을 때 자기가 나가면 됨

• A * B + C ➡️ A B * C +

  • *가 stack에 push 되었다가, 자기보다 우선순위가 낮은 +를 만났을 때 자기가 자기가 먼저 나가야하므로 그때 pop
  • 즉 + 입장에서 자기보다 우선순위가 높은 연산자들은 모두 pop

• ( A + B ) * C ➡️ A B + C *

  • 왼쪽 괄호 push: 왼쪽 괄호는 우선순위가 제일 낮지만, 일단 무조건 push (다른 연산자 pop 없어)

  • +는 오른쪽 괄호 다음에 빠져나가야 됨, +를 빼줄 수 있는 연산자는 자기보다 높은 연산자

    • )는 연산자 우선순위가 가장 높음

  • )는 자신의 짝인 ( 괄호가 있으므로 그 사이에 있는 연산자는 모두 pop 해야 됨 (괄호 안의 연산자는 더 우선시 되어야 하므로)

pseudo code

"""
리스트: outstack (출력 내용이 담길 stack)
스택: opstack 
"""
for each token in expr:
	if token == operand:
		outstack.append(token)
    if token == '(':
    	opstack.push(token)
    if token == ')':
    	# opstack에 저장된 연산자를 '('를 pop할 때까지 모두 pop하여 outstack에 append
    if token in ('+*-/'):
    	# push 되기 전에 opstack에 token보다 높은 우선순위의 연산자는 pop하고 들어감

# opstack에 남은 연산자 모두 pop -> outstack에 담기

postfix로 계산하기

• 피연산자 stack 마련

for each token in postfix.expr:
    if token == operand : s.push(token)
    if token in '+-*/':
        # 이항 연산자이므로 2개의 항이 필요
        a = s.pop()
        b = s.pop()
        # a와 b를 연산자로 계산 수행 후 결과를 다시 push
        s.push(a token b)