스택

 

 

스택의 개념과 추상 자료형

스택의 정의

• FILO
• 0개 이상의 원소를 갖는 유한 순서 리스트
• push아 pop연산이 한곳에서 발생되는 자료구조

스택의 응용

스택의 응용

• 변수에 대한 메모리 할당과 수집을 위한 시스템 스택
• 서브루틴 호출 관리를 위한 스택
• 연산자들 간의 우선순위에 의해 계산 순서가 결정되는 수식 계산
• 인터럽트의 처리와 이후 리턴할 명령 수행 지점을 저장하기 위한 스택
• 컴파일러, 순환 호출 관리

사칙 연산식의 표현

수식의 계산

연산자의 계산순서를 생각해야함

 

ex)

a+b*c+d

 

중위 표기식의 후위 표기식 변환 방법

1. 먼저 중위 표기식을 연산자의 우선순위를 고려하여 연산자/피연산자의 형태로 괄호로 묶어준다.
2. 각 계산뭉치를 묶고 있는 괄호 안에서 연산자를 계산뭉치의 가장 오른쪽으로 이동시킨다.
3. 각 계산뭉치를 하나의 피연산자로 고려하여 위를 반복한다.
4. 괄호를 모두 제거한다

(A - ( ( B + K ) / D ) )
(A - ( ( BK+ ) / D ) )
(A - ( ( BK+ ) D / ) )
(A ( ( BK+ ) D / ) ) - 
ABK+D/-

스택에 순서대로 넣다가 연산자가 나오면 값을 꺼내서 계산한다.

1. A
2. A, B
3. A, B, K
4. A, B, K +
5. A, B+K
6. A, B+K, D
7. A, B+K, D, /
8. A, (B+K)/D
9. A, (B+K)/D, -
10. A-(B+K)/D