Stack

일단 기본적으로 삽입, 삭제, 탐색이 되어야 한다.

Stack에서의 삽입은 push, 삭제는 pop이라고 한다.
물론 list의 append와 pop과 똑같지만, 다양한 작업을 할 수 있는 list 대신 딱 두 가지만 함으로 다른 실수를 하지 않게 하기 위해 Stack을 아래와 같이 class로 정의하여 사용한다.

top은 맨 위의 값을 알려주는 것이며, len은 길이를 반환한다.

S = Stack()
S.push(10)
S.push(2)
print(S.pop()) = 2
print(S.top) = 10
print(len(S)) = 1 -> S.len() 이라고 잘 생각한다.

class Stack:
	def __init__(self):
    	self.items = [] # 데이터 저장을 위한 리스트 준비
        
    def push(self, val): # O(1)
    	self.items.append(val)
        
	def pop(self): # O(1)
    	try:
        	return self.items.pop()
        except IndexError:
        	print("Stack is empty")
            
    def top(self): # O(1)
    	try:
        	return self.items[-1]
        except IndexError:
        	print("Stack is empty")
            
	def __len__(self): # O(1)
    	return len(self.items)

Stack 문제 : 괄호 맞추기

(2+5)* 7-((3-1)/2+7)
(()()) or (()))(
<문제>
입력 : 위와 같이 괄호 쌍이 제시
출력 : 괄호쌍이 맞춰져 있으면 True 아니면 False

ex) (()()) : 왼쪽 괄호면 push, 오른쪽 괄호면 pop -> 최종 리스트에 남아있는 것이 없다면 True or 남아있는 것이 있거나, pop했는데 에러가 발생하면 False

S = Stack()
for p in parseq:
	if p=='(': 
    	S.push(p)
    elif p==')':
    	S.pop()
    else:
    print('not allowed stmbol')

if len(S)>0:
	return False
else:
	return True

https://www.youtube.com/watch?v=OzFXiukhv8o&list=PLsMufJgu5933ZkBCHS7bQTx0bncjwi4PK&index=8