Stack2

2019. 02. 18 (Mon)

I. 문자열 계산기

stack을 이용하여 계산 처리

1. 중위 표기법을 후위 표기법으로 변환

stack 사용

괄호 사용

1. 연산자 기준으로 괄호 치기
2. 연산자를 괄호 밖으로 빼기
3. 괄호를 지우기

stack 사용

1. 중위 표기식에서 토근 읽기
2. 토큰 == 피연산자: 토큰 출력
3. 토큰 == 연산자(괄호포함):
   1. 스택의 top포자 우선순위가 높다: 스택에 push
   2. 작을때 까지 스택에서 pop하고 연산자 push
4. 토큰 == 끝 괄호: 시작 괄호 나올 때 까지 연산자 계산

예시

(6 + 5 * (2 - 8) / 2)

스택, post 스택 준비

연산자 => 스택에 push

• 스택에 push할 때 우선순위 고려
• top에 있는 연산자가 자신보다 우선순위가 작아야 push 가능
• 우선순위: ‘(‘, ‘*’ = ‘/’, ‘+’ = ‘-‘
• 우선순위가 같으면 우선순위가 자기보다 작을 때 까지 스택을 pop한다
• 괄호: 수식 안에서 가장 높고, 스택 안에서 가장 낮다
  • 닫는 괄호: 자기 pair가 나올 때 까지 스택을 pop하여 post에 출력

피연산자 => post 스택에 출력

남아있으면 모두 post 스택에 출력

2. 계산

post 스택에 있는 내용을 빼면서 연산자 일 경우 stack에서 2개를 빼서 계산

결과를 push

II. 순열

백 트래킹으로 해결 가능

부분 집합 구하는 논리와 유사

예시

1. {1, 2, 3}의 부분집합을 구한다.

2. 3! = 6 의 경우의 수

3. 최초의 원소를 추출하고 그 밑으로 2개의 원소 사용가능

4. {1, …}, {2, …}, {3, …}

5. 하나의 원소를 사용하면 마지막으로 1개의 원소 사용가능

• {1, 2, …}, {1, 3, …}, {2, 1, …}, {2, 3, …}, {3, 1, …}, {3, 2, …}

1. 구현 방법

노드에 들어가 후보군 생성

• 유망한 노드를 선별(지금 까지의 상황을 고려하여 미래 결과를 예측)

후보군 만큼 백트래킹

---

• ← Previous Post
• Next Post →