[자료구조] 9. 스택의 응용

1. 스택의 응용 분야

문서 편집기의 되돌리기(Undo) 기능

• 사용자가 작업을 수행한 후 이전 상태로 되돌리기 위해 사용

• 실행한 작업을 순차적으로 기록하고, 역순으로 취소해야 하므로 스택 이용

 

컴퓨터 프로그램의 함수 호출

• 함수 호출 시 복귀 주소, 지역 변수, 매개변수 등을 스택에 저장

• 함수 실행 완료 후 스택에서 최근 복귀 주소를 가져와 원래 위치로 돌아감

 

컴파일러의 산술식 변환

• 컴파일러는 산술식을 분석하여 연산자와 피연산자를 구별하고 우선순위에 맞게 변환

• 전위 표기법, 중위 표기법, 후위 표기법 변환 시 스택 사용

 

문자열 뒤집기

• 문자열을 입력 순서대로 스택에 저장한 후, 역순으로 꺼내어 출력

• 예: "ABCD" → "DCBA"

 

괄호 검사

• 소스 코드에서 괄호의 짝을 확인하기 위해 사용

• 여는 괄호는 스택에 push하고, 닫는 괄호가 나오면 pop하여 짝이 맞는지 확인

• 남은 괄호가 없으면 정상적인 괄호 사용

 

인터럽트 처리 및 산술 계산

• 운영체제에서 인터럽트 발생 시 복귀 주소 저장 등에 활용

• 계산기 프로그램에서도 후위 표기법 계산을 위해 스택 사용

 

백트래킹(Backtracking)

• 해를 찾는 과정에서 막히면 되돌아가는 기법

• 깊이 우선 탐색(DFS)에서 경로를 추적하는 데 사용

 

미로 탐색

• 지나온 경로를 스택에 저장하고, 막다른 길을 만나면 되돌아감

• 스택을 이용해 탐색 과정 관리

 

 

 

2. 수식의 표기법

연산자와 피연산자

• 연산자(operator): 연산을 수행하는 기호

• 피연산자(operand): 연산의 대상이 되는 값

• 연산자의 우선순위: 연산을 수행하는 순서를 결정하는 규칙

 

수식 표기법

• 전위 표기법 (Prefix): 연산자 - 피연산자 - 피연산자 → +AB

• 중위 표기법 (Infix): 피연산자 - 연산자 - 피연산자 → A+B

• 후위 표기법 (Postfix): 피연산자 - 피연산자 - 연산자 → AB+

 

중위 표기식 변환 예시 (A*B-C/D)

전위 표기법 변환

• 괄호를 사용하여 우선순위 표현: -(*(A B) /(C D))

• 연산자를 왼쪽 괄호 앞에 배치: -*AB/CD

• 괄호 제거: -*AB/CD

 

후위 표기법 변환

• 괄호를 사용하여 우선순위 표현

• 연산자를 오른쪽 괄호 뒤로 이동: ((A B)* (C D)/)-

• 괄호 제거: AB*CD/-

 

수식 표기법 변환 예제 (5+A*B)

• 전위 표기법: +5*AB

• 중위 표기법: 5+A*B

• 후위 표기법: 5AB*+

 

비교

• 중위 표기법: 사람이 이해하기 쉽지만 컴퓨터에서는 우선순위와 괄호 처리가 필요

• 후위 표기법: 컴퓨터에서 연산을 처리하기에 가장 효율적이며, 괄호와 연산자 우선순위 처리가 불필요

 

 

 

3. 스택을 이용한 수식 계산

후위 표기법 수식 계산 방법

• 피연산자를 만나면 스택에 push

• 연산자를 만나면 필요한 개수만큼 pop하여 연산 수행 후 결과를 push

• 수식이 끝나면 스택에서 pop한 값이 최종 결과

 

예제: 후위 표기 수식 82/3-32*+ 계산

• 왼쪽에서 오른쪽으로 스캔하며 피연산자는 push, 연산자는 pop하여 계산 후 push

 

중위 표기식을 후위 표기식으로 변환하는 방법

(1) 왼쪽 괄호 (를 만나면 무시하고 다음 문자로 이동

(2) 피연산자는 출력

(3) 연산자는 스택에 push

(4) 오른쪽 괄호 )를 만나면 스택에서 pop하여 출력

(5) 수식이 끝나면 스택이 빌 때까지 pop하여 출력

 

예제: A*B-C/D → 후위 표기법 변환 과정

• 중위 표기법: A * B - C / D

• 후위 표기법: AB*CD/-

---

이 내용은 휴넷사회복지평생교육원의 자료구조 강의를 듣고 정리한 것입니다.