Stack

Stack 은 LIFO(Last In First Out) 형태의 자료구조이다.

 

대표적인 응용 예시로는 계산기를 예로 들 수 있다.

보통 수식은 Infix notation 형식으로 입력한다. 

(3+4)*7

stack을 활용하기 위해선 이를 Postfix notation으로 변환해야 하는데,

3 4 + 7 *

이 때, stack을 활용하면 쉽게 이를 달성할 수 있다.

 

입력으로 들어온 Infix notation은 총 4가지의 경우에 따라 다르게 처리된다.

1. 왼쪽 괄호인가? '('

왼쪽 괄호의 경우에는 stack에 추가한다.

 

2. 숫자(변수와 같은 피연산자)인가?

숫자의 경우에는 출력한다.

 

3. 연산자인가? '+', '-', '*', '/'

연산자의 경우에는 아래의 세 조건을 만족할 때 까지 모든 연산자를 꺼내어 출력하는 동작을 한다.

    a. 스택이 비거나

    b. 왼쪽 괄호를 만나거나

    c. 자신보다 낮은 연산자 우선순위의 연산자를 만나거나

반복 후 자신이 stack에 들어간다.

 

4. 오른쪽 괄호인가? ')'

오른쪽 괄호의 경우 왼쪽 괄호를 만날 때 까지 모든 연산자를 꺼내어 출력하는 동작을 한다.

(다만, 왼쪽 괄호는 출력하지 않고 제거만 한다)

 

아래의 예시를 살펴보자.

3*X+(Y-12)-Z

3은 2번의 경우이므로 출력한다.

stack:

output: 3

 

*은 3번의 경우이지만 a 조건에 바로 걸리기 때문에 바로 스택에 들어간다.

stack: *

output: 3

 

X는 2번의 경우이므로 출력한다.

stack: *

output: 3 X

 

+는 3번의 경우이다. 이 때, stack에 상단에는 a, b, c조건을 만족하지 않기에 *를 꺼내어 출력한다.

stack: 

output: 3 X *

그리고 a 조건에 걸리기 때문에 자신이 들어간다.

stack: +

output: 3 X *

 

(은 1번의 경우이므로 stack에 들어간다.

stack: + (

output: 3 X *

 

Y는 2번의 경우이므로 출력한다.

stack: + (

output: 3 X * Y

 

-는 3번의 경우이다. 이 때, 스택 상단에 왼쪽 괄호가 있기에 조건 b에 걸려 바로 자신이 stack에 들어간다.

stack: + ( -

output: 3 X * Y

 

12는 2번의 경우이므로 출력한다.

stack: + ( -

output: 3 X * Y 12

 

)은 4번의 경우이므로 왼쪽 괄호를 만날 때 까지 스택에서 연산자를 꺼내어 출력한다. (단, 왼쪽 괄호는 출력하지 않는다)

stack: + (

output: 3 X * Y 12 -

stack: +

output: 3 X * Y 12 -

 

-는 3번의 경우이다. 이 때, 스택 상단에는 a, b, c조건을 만족하지 않기에 +을 꺼내어 출력한다.

stack: 

output:  3 X * Y 12 - +

그리고 a조건에 걸리기 때문에 자신이 들어간다.

stack: -

output:  3 X * Y 12 - +

 

Z는 2번의 경우이므로 출력한다.

stack: -

output:  3 X * Y 12 - + Z

 

입력이 끝났기에 스택을 모두 비워준다.

stack:

output:  3 X * Y 12 - + Z -

 

이렇게 stack을 사용해서 3*X+(Y-12)-Z Infix notation을 3 X * Y 12 - + Z - Postfix notaion으로 변환했다.

Postfix notation 식을 계산하는 과정 역시 stack으로 처리가 가능하다.

1. 숫자(변수와 같은 피연산자)인가?

숫자의 경우에는 stack에 추가한다.

 

2. 연산자인가? '+', '-', '*', '/'

stack에서 피연산자 2개를 꺼낸 후 연산 후 다시 stack에 넣어준다.

 

위에서 구한 Postfix notaion으로 예시를 들어보자.

3은 stack에 넣어준다.

stack: 3

 

X도 stack에 넣어준다.

stack: 3 X

 

*는 연산자이므로 stack에서 2개를 꺼내어 연산 후 넣어준다.

stack: 3X

 

Y, 12도 stack에 넣어준다.

stack: 3X Y 12

 

-는 연산자이므로 stack에서 2개를 꺼내어 연산 후 넣어준다.

stack: 3X Y-12

 

+는 연산자이므로 stack에서 2개를 꺼내어 연산 후 넣어준다.

stack: 3X+Y-12

 

Z는 stack에 넣어준다.

stack: 3X+Y-12 Z

 

-는 연산자이므로 stack에서 2개를 꺼내어 연산 후 넣어준다.

stack: 3X+Y-12-Z

 

실제로 숫자를 예로 들어보면 stack에 남아있는 최종 값이 Infix notaion 입력으로 들어온 수식의 계산 결과라는걸 알 수 있다.

 

stack의 구현 과정은 간단하기에 생략하도록 하겠다.

실제로 linked list로 구현할 경우 head에 추가와 삭제만 하면 되고,

static array로 구현하는 경우 마지막 index(used-1)에만 추가와 삭제를 하면 되기 때문..!