방송대/자료구조
스택
피클s
2022. 9. 13. 08:50
스택의 개념과 추상 자료형
스택의 정의
- FILO
- 0개 이상의 원소를 갖는 유한 순서 리스트
- push아 pop연산이 한곳에서 발생되는 자료구조
스택의 응용
스택의 응용
- 변수에 대한 메모리 할당과 수집을 위한 시스템 스택
- 서브루틴 호출 관리를 위한 스택
- 연산자들 간의 우선순위에 의해 계산 순서가 결정되는 수식 계산
- 인터럽트의 처리와 이후 리턴할 명령 수행 지점을 저장하기 위한 스택
- 컴파일러, 순환 호출 관리
사칙 연산식의 표현
수식의 계산
연산자의 계산순서를 생각해야함
ex)
a+b*c+d
중위 표기식의 후위 표기식 변환 방법
- 먼저 중위 표기식을 연산자의 우선순위를 고려하여 연산자/피연산자의 형태로 괄호로 묶어준다.
- 각 계산뭉치를 묶고 있는 괄호 안에서 연산자를 계산뭉치의 가장 오른쪽으로 이동시킨다.
- 각 계산뭉치를 하나의 피연산자로 고려하여 위를 반복한다.
- 괄호를 모두 제거한다
(A - ( ( B + K ) / D ) )
(A - ( ( BK+ ) / D ) )
(A - ( ( BK+ ) D / ) )
(A ( ( BK+ ) D / ) ) -
ABK+D/-스택에 순서대로 넣다가 연산자가 나오면 값을 꺼내서 계산한다.
- A
- A, B
- A, B, K
- A, B, K +
- A, B+K
- A, B+K, D
- A, B+K, D, /
- A, (B+K)/D
- A, (B+K)/D, -
- A-(B+K)/D