[TIL] KDT_20230411

📚 KDT WEEK 2 DAY 2 TIL

1. 연결리스트(Linked List)
2. 스택(Stack)
3. 후위 표기 수식

---

연결리스트의 장단점

• 원소의 삽입, 삭제가 선형 배열의 경우보다 쉽다.
• 선형 배열의 구조보다 구조 표현에 소요되는 저장 공간의 소요가 크다.
• 특정 원소를 참조하는 경우 선형 배열의 경우보다 느리다. O(n)

 

이때, head는 dummy node라고도 부른다

 

---

 

양방향 연결 리스트 (Doubly Linked Lists)의 특징

• head와 tail에 각각 dummy node를 하나씩 가진다.
• 당연히 일반 연결리스트보다 메모리 사용량이 늘어난다.
• 하지만 더 효율적이고 빠른 탐색이 가능하다.

Doubly Linked Lists의 삽입 예시

 

---

 

스택(Stack)

• 후입선출(LIFO) 방식의 자료구조

 

수식의 후위 표기법(Postfix Notation)

• 괄호없이 연산의 우선순위를 표현 가능한 방법으로써, 연산자가 뒤에 표현된다.
• 컴퓨터가 수식을 계산하는 데에 유리한 방법 => 스택 사용

 

---

중위표현식 ▶ 후위표현식 예시

( A + B ) * ( C + D ) ➡ AB+CD+*

---

 

---

 

🤔 공부하면서 어려웠던 내용

12강 실습 과정 중, 중위표현 수식을 후위표현 수식으로 바꾸는 과정에서 조금 헤맸다..😭

세가지 테스트 케이스가 통과되지 않았는데, 오류도 모르고 출력도 모르니 어쩌지 하다가..

같은 문제를 겪는 동기분이 올린 글에서 엣지 케이스를 추가하고 해답을 얻었다..! 👏

 

---

 

문제의 엣지 케이스

"A+B*C/(D*E-F)+G" ➡  "ABC*DE*F-/+G+"

내 코드 결과로는 "ABC*DE*F-/G++" 가 나왔었다.

 

문제는, 두 연산자이상이 연속으로 스택에 들어있던 상황에서 스택에 들어가려는 연산자가 스택의 두 연산자 중 하나와만 비교하고 스택에 들어갔기 때문이다.

 

연속으로 존재하던 두 번째 연산자는 스택에 들어가려는 연산자보다 이미 앞서 들어가있던 연산자이므로, 이 연산자와도 우선순위를 비교하고 스택에 들어가는 것이 맞는 것 같다.

 

다음은 함수의 인자에서 연산자가 나왔으므로, 스택과 우선순위를 비교하던 구문이다.

while not opStack.isEmpty() and prec[opStack.peek()] >= prec[e]: # 우선순위가 높거나 같을 경우 스택거는 pop
	result.append(opStack.pop())
opStack.push(e) # 스택의 우선순위가 더 낮거나 낮아진 경우 e를 스택에 PUSH

 

 

코드 전문( 개나 줘버린 가독성.. )

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()
    result = []
    
    for e in S:
        
        if e in prec or e == ')': # 연산자와 괄호일 경우
            
            if opStack.isEmpty() or e == '(': # 스택이 비었거나 여는 괄호일 경우 스택에 PUSH
                opStack.push(e)
                
            elif e != ')': # 스택에 뭔가 있을 경우 우선순위 비교              
                while not opStack.isEmpty() and prec[opStack.peek()] >= prec[e]: # 우선순위가 높거나 같을 경우 스택거는 pop
                    result.append(opStack.pop())
                        
                opStack.push(e) # 우선순위가 더 낮거나 낮아진 경우 e를 스택에 PUSH
                    
            else: # 닫는 괄호일 경우
                while opStack.peek() != '(': # 여는 괄호가 나올 때까지 계속해서 pop
                    if opStack.peek() != '(':
                        result.append(opStack.pop())
                opStack.pop() # 여는 괄호 제거
                    
        else: # 문자일 경우
            result.append(e)
            
        
    while not opStack.isEmpty(): # 남은 스택 털어 넣기
        result.append(opStack.pop())
    
    return "".join(result)