2주차 화요일(3)

스택stacks
링크드 리스트 같은 것들은 기본이라면,
스택, 큐 , 힙 이런것들은
특정 문제를 풀기 위한 자료구조라고 한다.

스택 : 자료를 보관할 수 있는 선형 구조
단 넣을떈 한쪽 끝에서 넣고 뽑을때도 거기서 꺼내야 함
= push pop
=LIFO 후입선출 Last In First Out

비어있는 스택에서 원소를 꺼내려 할 때 = Stack underflow

꽉 찬 스택에 데이터 원소를 넣으려 할 때 = Stack overflow

스택의 추상적 자료구조의 구현의 대표적 두가지 방법

1. 배열 array 이용 : 파이썬 리스트와 메서드 이용
2. 연결리스트 이용 : 지난시간 구현한 양방향 연결리스트 이용

연산의 정의

참고 : 생성자 메서드(construcor method)

객체를 생성할 때 사용되는 메소드인데, 객체를 초기화하는 역할을 수행한다.
객체를 생성함과 동시에 기억 공간이 만들어졌으니 데이터를 저장할 수 있다.
저장하는 행위를 initialize 초기화 라고 한다.
클래스 이름과 동일한 메서드이며, return type이 없다.
객체를 생성할 때 생성자메소드를 통해 객체가 만들어지기 때문에 직접 만들지 않더라도 자동으로 삽입이 되고, 이것을 <기본생성자> 라고 한다.

결론:특별히 객체를 생성할 때 사용되는 메소드를 생성자 라고 한다.

def size(self): #스택 크기 리턴
	return len(self.data)
    
def isEmpty(self): #스택이 비어있는지 판단
	return self.size() ==0 #이러면 True가 나오고 아니면 False가 나오는 부울연

class ArrayStack : 
	def push(self,item):
    	self.data.append(item) #데이터 원소를 추가
        
    def pop(self):
    	return self.data.pop() #데이터 원소를 삭제(리턴)
        
	def peek(self):
    	return self.data[-1] #스택의 꼭대기 원소 반환

from doublylinkedlist import Node
from doublylinkedlist import DoublyLinkedList
#우리가 앞서 구현한 doublylinkedlist를 불러왔다.

class LinkedListStack:

	def __init__(self):
		self.data = DoublyLinkedList()

	def size(self):
		return self.data.getLength()
#doublylinkedlist안에 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
#현재 사이즈를 구해서 맨 마지막에 있는 데이터를 리턴한다.

이런 라이브러리를 누군가 이미 만들어놨다.
from pythonds.basic.stack import Stack

연습문제 - 수식의 괄호 유효성 검사.

알고리즘을 설계해보자

• 수식을 왼쪽부터 한 글자씩 읽어서:
  - 여는 괄호가 있다 : 스택에 푸시
  • 닫는 괄호가 있는데 1. 스택이 비어있다 : 올바르지x
    2. 스택에서 쌍을 이루는 여는 괄호이지 않다 : 올바르지 X 올바른 경우는 pop 해준다.
    끝까지 검사한 후, 스택이 비어있어야 올바른 수식!

빈칸 채우는예제를 준다고 했는데 ㅜ 안나와있어서 다른 블로그를 참고하여 찾아보았다.

수식을 왼쪽부터 한글자씩 읽어서, 여는 괄호 (,{,[" 를 만나면 스택에 push 하고, 닫힌 괄호를 만나면 스택에서 그 여는 괄호를 pop하여 딕셔너리의 쌍을 이루는 괄호인지 검사한다. 끝까지 검사한 후에는 스택에 비어있어야 올바른 수식이다.

Point는 열린괄호와 닫힌괄호를 딕셔너리를 통해 쌍을 지어주는 것이다! (닫힌 괄호를 key로 지정하기)

def solution(expr):
    match = {')' : '(', 
             '}':'{', 
             ']':'['
            }         # 맞는 괄호를 딕셔너리로 지정
    
    S = ArrayStack()
    for c in expr:
        if c in '({[':    # 여는 괄호를 스택에 넣음
            S.push(c)
            
        elif c in match:  # 닫힌 괄호(key)일 때
            
            if S.isEmpty():  # 만약 스택이 비어있으면 False
                return False
            
            else:
                t = S.pop()
                if t != match[c]:  # 스택에 담긴 괄호(열린괄호)와 닫힌 괄호가 같지 않으면
                    return False
                
    return S.isEmpty()   # 끝까지 검사한 후 스택이 비어있어야 올바른 수식

중위 표현식 = 후위표현식
AB+C = ABC+
A+BC = ABC+

연산자의 우선순위를 지키기 위해 스택을 사용할 수 있다.
스택에 담아주고 우선순위가 먼저거나 같다면 pop해주고 새로운걸 push해준다.
우선순위가 밀린다면 그위에 우선순위가 높은걸 push해주고 우선순위 낮은게 나올때까지 pop을 하지 않는다.

괄호가 있다면, 괄호의 우선순위를 가장 낮게 잡아준다.
그러면 끝!

#연산자의 우선순위 설정
prec={
'*':3 , '/':3, '+':2 , '-':2, '(':1
}

중위 표현식을 왼쪽부터 한글자씩 읽어서
피연산자 : 출력
'(' push
')' 이면 '('이 나올때까지 안에 있는 연산자 원래 규칙과 같이 처리
''만나면 pop,출력

스택에 남아있는 연산자는 모두 pop 출력

코드의 구현 - 힌트 : 스택의 맨 위에 있는 연산자와의 우선순위 비교 -> peek()이용!

스택에 남아있는 연산자 모두 pop()하는 순환문 : while not opStack.isEmpty():

내 오류나는 풀이

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]

prec = {
    '*': 3, '/': 3,
    '+': 2, '-': 2,
    '(': 1
}

def solution(S):
    opStack = ArrayStack()
    answer =''
    for i in S:
        if i not in prec:
            if i == ')':
                while opStack.peek() != '(':
                    answer += opStack.pop()
                opStack.pop()
                
            else : answer += i   
        elif opStack.size() > 0:
            new = prec[i]
            prev = prec[opStack.peek()]
            if 1< new <= prev:
                answer += opStack.pop()
                opStack.push(i)
            else : opStack.push(i)
            
        else : opStack.push(i)
        
    while not opStack.isEmpty():
        answer += opStack.pop()
    return answer

찾아보니
"A+BC/(DE-F)+G" -> "ABCDEF-/+G+"
이런 반례가 있다고 한다...
아놔 ㅋㅋㅋ 이 반례를 해결해보겠다...
일단진도 나가고ㅜㅜ