자료구조 18강 - 스택의 응용

System stack(시스템 스택)

 

- 함수 호출에서 사용됨

- call stack이라고도 함

- 재귀 호출의 경우

function factorial(n){
  if(n==1) return 1;
  else n*(factorial(n-1);
}

 

괄호 검사(checking parenthesis)

 

- 괄호(Parenthesis) : (), {}, []

- 괄호 매칭 규칙(Parenthesis matching rule)

모든 여는 괄호(opening parenthesis)는 같은 종류의 닫는 괄호(Closing parenthesis)가 있어야 함

- ( → )

- { → }

- [ → ]

 

스택을 이용한 괄호 검사

 

규칙 1. 여는 괄호 : 여는 괄호는 스택에 저장

규칙 2. 닫는 괄호 : 닫는 괄호는 스택 탑의 괄호와 같은 타입일 때만 Pop

규칙 3. 종료 : 마지막 괄호까지 점ㄱ머한 후에 스택이 empty면 에러 없음

규칙 4. error 

① 닫는 괄호와 스택 탑의 괄호의 타입이 다르면 에러

② 닫는 괄호를 만났는데 스택이 엠티이면 에러

③ 마지막 괄호까지 점검한 후에 스택은 엠티가 아니면 에러

 

후위 표기(Postfix expression)

 

중위 표기(infix notation) : 피연산자1 연산자 피연산자2

중위 표기의 문제점 → 연산의 우선 순위

ex. *는 +보다 우선 순위가 높다 / a + b * c에서 a +b를 b * c보다 먼저 연산할 수 없음

/ 우선 순위를 무력화하기 위해서 괄호 ( )가 필요하다 (a + b) * c ≠ a + b * c

 

후위 표기 : 피연산자1 피연산자2 연산자

중위 표기와 달리 괄호 ( )를 필요로 하지 않는다

 

후위 표기 수식의 연산 규칙 스택을 이용

규칙 1. 피연산자(Operand) → 스택에 저장

규칙 2. 연산자 → 스택에서 2번 Pop / 제거된 값을 연산 / 연산된 값을 다시 스택에 Push

 

미로 찾기(Maze Problem)

 

미로의 조건

미로 : 2차원 배열 

- 통로 : 0

- 벽 : 1

입구 & 출구

 

미로의 시작 : 입구에서 출발

미로의 끝 : 출구에 도착

 

미로의 어려움

1. 길이 막힌 경우

지나간 길을 저장해서 돌아가는 데에 이용

길 : 위치들의 연속

돌아갈 때는 가장 마지막에 지나간 위치가 필요함

스택을 이용해서 위치를 저장

 

2. 지나간 길과 지나가지 않은 길 구분

스택을 이용해 이미 지나온 길을 표시

움직일 수 있는 경우 : 현재 위치를 스택에 push하고 이동

움직일 수 없는 경우 : 스택을 pop하고 pop된 위치로 이동

모든 위치를 이미지 지나온 길(v) 또는 더이상 갈 수 없음(x)로 표기할 것

 

그래프 또는 트리 탐색

깊이 우선 탐색(Depth-first search)