1. SWEA 1222 계산기 문제를 풀다가..
해당 문제의 풀이 시 후위 표기식을 활용해야 하는 상황이 있었다.
그런데 아직 후위 표기식에 대해서 아무것도 몰라서 해당 부분을 편하게 연산하는 방법을 찾다가 정리를 해본당.
2. 후위 표기식이란?
챗 gpt에게 물어보았다.. 요즘은 검색보다 빠르다
연산자 우선순위와 괄호를 쓰지 않는다고 한다. 비유하자면.. 계산기에서 괄호로 한 번에 연산하는 것이 아니고 계속 숫자와 수식을 써가면서 여러 번 계산 버튼 누르는 느낌?
스택 자료구조를 활용하여 연산한다고 한다. 왜 스택 자료구조를 사용하는지도 물어보았다.
스택 기반 계산이 효율적인 이유는 다음과 같은 특성과 장점을 가지고 있기 때문입니다:
1. 연산자 우선순위와 괄호 처리가 불필요
- 스택을 사용하면 연산자 우선순위와 괄호 규칙을 별도로 처리할 필요가 없습니다.
- 후위 표기식(Reverse Polish Notation, RPN)을 사용하면 연산 순서가 이미 명시되어 있어, 스택만으로 간단하게 계산할 수 있습니다.
- 예:
중위 표기식:(3 + 4) * 2
후위 표기식:3 4 + 2 *
→ 스택으로 바로 연산 가능.
2. 메모리와 연산 순서 관리가 용이
- 스택은 LIFO(Last-In, First-Out) 구조를 가지므로, 계산에 필요한 값을 순차적으로 푸시하고, 필요한 시점에 팝(pop)하여 연산을 수행할 수 있습니다.
- 스택의 특성 덕분에 중간 결과를 효율적으로 저장하고 불러올 수 있습니다.
- 예: 복잡한 수식에서 중간 값을 임시로 저장해야 할 때 스택을 사용하면 직관적이고 간단합니다.
3. 컴퓨터 구조와 자연스러운 연계
- 스택 기반 계산은 컴퓨터의 하드웨어 스택 구조와 밀접하게 연관되어 있습니다.
- 컴퓨터의 호출 스택(Call Stack)과 같은 동작 방식을 활용하여 연산을 수행할 수 있습니다.
- 예: 재귀 호출, 함수 반환, 메모리 관리 등.
4. 구현이 간단하고 확장성이 높음
- 스택 기반 알고리즘은 간결한 코드로 구현 가능하며, 자료구조가 단순하여 디버깅과 유지보수가 쉽습니다.
- 다양한 응용 분야에 확장할 수 있음:
- 후위 표기식 계산.
- 괄호 유효성 검사.
- 미로 탐색(DFS).
5. 메모리 효율성
- 스택은 필요한 만큼만 메모리를 동적으로 사용하므로, 불필요한 메모리 낭비가 없습니다.
- 연산 중간 값을 스택에 저장하므로, 전역 메모리나 추가 배열을 사용할 필요가 없습니다.
6. 알고리즘적 최적화
- 스택은 반복적인 연산을 간단하게 처리할 수 있어 알고리즘 설계에 유리합니다.
- 중위 표기식을 후위 표기식으로 변환하는 알고리즘(예: Shunting-yard algorithm)에서도 스택을 사용하여 효율적인 연산 순서를 결정합니다.
7. 재귀를 반복으로 변환 가능
- 스택을 활용하면 재귀 알고리즘을 반복문 기반으로 전환할 수 있습니다.
- 예: DFS(깊이 우선 탐색)를 스택 기반으로 구현.
- 재귀 호출 대신 스택에 현재 상태를 저장하고 다음 상태로 진행.
실제 사례
- 컴파일러:
- 컴파일러는 수학식을 파싱하고 계산하는 과정에서 스택을 사용.
- 계산기:
- 후위 표기식을 계산하는 계산기 구현.
- CPU 구조:
- CPU의 실행 흐름 제어(함수 호출/리턴, 인터럽트 처리 등)에 스택 활용.
요약
스택 기반 계산은 연산 우선순위를 관리하거나 중간 값을 저장하는 데 효율적이며, 컴퓨터 하드웨어와 자연스럽게 연계되어 메모리와 계산 자원을 효과적으로 사용할 수 있습니다. 이러한 특성 덕분에 수식 계산, 재귀 처리, 자료 탐색 등 다양한 분야에서 널리 사용됩니다.
그렇다고 한다.
3. 스택 사용법
CK