[자료구조] 스택(Stack)의 이해 - python을 통한 실습 (2)

스택(Stack)

- 스택은 일종의 리스트

- 데이터의 삽입과 삭제가 한쪽의 끝에서만 이루어진다

- LIFO (Last-In, First-Out)

- 삽입/삭제가 일어나는 쪽을 스택의 top이라고 부름

스택의 연산

- push : 스택에 새로운 원소를 삽입하는 연산

- pop : 스택의 top에 있는 원소를 스택에서 제거하고 반환

- peek : 스택 top의 원소를 제거하지 않고 반환

- empty : 스택이 비었는지 검사

 

#Python 예제

stack = [1,2,3] stack.append(4)  #stack push print(stack) # [1,2,3,4] top = stack.pop() #stack pop print(top) #4 print(stack) #[1,2,3] top = stack[-1] #stack peek print(top) #3

 

#스택 예제 : 괄호 검사 문제

Q. 입력 수식의 괄호가 올바른지 검사

     [a + b * {c / (d -e) } ] + ( d / e )

- 단순히 여는 괄호와 닫는 괄호의 개수 비교만으로 확인 불가

- Stack을 이용하여 검사

   ㄴ Tip. 여는 괄호는 스택에 push

   ㄴ 닫는 괄호가 나오면 스택에서 pop한 후, 두 괄호가 같은 유형이어야 함

   ㄴ 마지막에 스택에 남은 괄호가 없어야 함

 

#Python으로 구현한 괄호 검사 코드

#입력은 숫자 공백 없이 괄호로만 입력되는 것으로 가정 (중간에 공백도 없음)

OPEN = '([{'
CLOSE = ')]}'

stack = []

def is_close(ch):
    for i in range(len(CLOSE)):
        if(CLOSE[i] == ch):
            return i #소괄호는 0, 대괄호는 1, 중괄호는 2 반환
    return -1

def is_open(ch):
    for i in range(len(OPEN)):
        if(OPEN[i] == ch):
            return i
    return -1

def is_empty():
    if len(stack) == 0:
        return 1
    return 0


def is_balanced(arr):
    balanced = 1
    index = 0
    while (balanced and index < len(arr)):
        ch = arr[index]
        if (is_open(ch) > -1):
            stack.append(ch)
        elif (is_close(ch) > -1):
            if is_empty(): #닫는 괄호가 나왔으나 스택이 비었다면 return
                balanced = 0
                break
            top_ch = stack.pop()
            if (is_open(top_ch) != is_close(ch)):
                balanced = 0
        index += 1
    return (balanced == 1 and is_empty() == 1)        

arr = input() #입력

if is_balanced(arr):
    print(arr + 'balanced')
else:
    print(arr + 'unbalanced')

 

#[복습] 프로그래머스 비슷한 문제 / 올바른 괄호

 

https://school.programmers.co.kr/learn/courses/30/lessons/12909

프로그래머스

def solution(s):
    stack = []
    index = 0

    while(index < len(s)):
        ch = s[index]
        if (ch == '('):
            stack.append(ch)
        elif (ch == ')'):
            if(len(stack) == 0):
                return False
            stack.pop()
        index +=1
    return (len(stack) == 0)