스택과 표기법

상위목차 - [C강좌] 스택과 표기법

---

만약 C를 배웠다면 C의 원초격인 저급언어인 어셈블리를 대충은 어떤 언어인지 알고 있을 것이다. 

메모리 수준의 단위를 관리하며 프로그래밍을 하게되는 어셈블리에서 스택(stack)이란 요소는 아주 중요한데, 

일단 스택이 무엇인지 알아보자.

스택(stack)은 이름그대로 쌓고 뺄수있는 일종의 자료구조이다.

스택은 1차원 구조를 가지며 스택에 자료를 넣는것을 푸시(push) 빼는것을 팝(pop)이라 한다.

구조가 1차원이기에 먼저 넣었던 것을 가장 나중에 빼야하고 나중에 넣은걸 가정 먼저 빼야하는 후입선출(Last In First Out, LIFO)의 

구조를 갖는다.

아래의 스택구조를 이해한다면 어셈블리의 아주 기초적인 부분은 이해했다고 볼 수 있다.

10의 크기를 갖는 아래와 같은 스택이 있고 스택의 입구가 좌측이라 가정하자.

push 5

5

push 2 7

7

2

5

만약 여기서 우리가 5를 꺼내야 하는 상황이라면 pop 7 2 로 우선 7과 2를 빼내 임시로 다른곳에 저장 한후에 5를 꺼내서 전달하고 다시 7과2를 넣어야 한다. 

이러한 형태의 구조가 스택이기에 효율적으로 동선을 조절하려면 스택에 넣고 빼는 데이터의 순서와 관리방식이 매우 중요해진다.

현재의 대부분 메모리는 이런 후입선출형 스택 구조를 갖기에 효율적인 메모리관리를 위해서라면 이를 이해하고 있어야한다. 

(물론 요즘은 컴파일러가 알아서 효율적인 구조로 대부분 변환해준다.)

스택에 저장된 자료중에 최근 push된 자료를 확인하려면 원래 pop를 사용해야하지만 peek을 통해서도 최근에 들어간 값을 확인하는 것도 가능하다. 

만약 10의 스택 메모리에 11개의 데이터를 넣으면 스택 오버플로우(stack overflow)가 발생하며 스택이 하나도 없는 상태에서 pop를 시도하면 스택 언더플로우가 발생하게 된다(stack underflow)

이러한 스택의 특징은 프로그래밍 대부분에서 나타나게 되는데, 그중 앞서 배운 C에서는 함수가 함수를 호출하는 재귀함수(다시 돌아오는 함수)도 이러한 스택의 구조를 가지고 있습니다.

25

42

85

12

7

18

67

85

27

5

위와 같은 데이터 테이블이 존재할때 재귀함수를 통해서 10개의 데이터에 접근할 수 있습니다.

물론 배열이 편리하겠지만 이건 예제를 위한 것이므로 재귀함수는 좀더 복잡한 문제에 접근하는데 용의합니다.

먼저 데이터의 가장 앞에 있는 25를 확인하는 함수를 호출하고 만약 다음메모리에 데이터가 존재한다면 42를 확인하기 위해 확인하는 함수를 호출합니다. 

42를 확인하기에 앞서 25를 확인했던 함수가 다시 자신과 같은 함수를 호출하는데, 여기서 재귀가 발생하게됩니다. 

이때 스택에는 42를 확인하는 함수를 호출한 위치가 25를 확인한 함수란걸 기억하기 위해 스택에 이정보를 밀어넣습니다.

25확인!

이게 만약 마지막 데이터인 5까지 반복되면 

5 확인!

27 확인!

85 확인!

67 확인!

18 확인!

7 확인!

12 확인!

85 확인!

42 확인!

25 확인!

이렇게 스택에는 자신이 지나온 루트를 스택을 밀어넣어 기억할 것이고 마지막 5의 확인이 끝나고 다음데이터가 없음을 확인하면 원래 처음 자신을 호출했던 25를 확인하는 함수를 호출한 위치로 돌아가기 위해 스택을 순차로 pop 시키며 뒤로 돌아갈 것입니다. 

이러면 스택은 다시 정리되고 재귀로 호출된 함수들을 역순으로 돌아가 원래 위치로 돌아올 수 있습니다.

이러한 스택의 구조덕에 컴퓨터는 통상 인간이 하는 연산관 다른 연산을 하게되는데, 이는 중위표기법과 후위 표기법에서 차이를 알 수 있습니다.

중위 표기법은 명시적인 규칙을 가지고 연산을 표기합니다.

우리가 흔히 보는 (7+3) * 10 + 2 + 8 * 7 와 같은 연산이 인간이 보기편하게끔 만들어진 중위 표기식입니다.,

중위 표기법에서는 () 안의 값을 우선 계산하고 다음은  * / 등이 우선이 됩니다. 

이러한 규칙덕에 인간이 보고 파악하는건 편하지만 한번에 하나의 일을하는 컴퓨터는 규칙을 확인하기 위한 검사까지 추가로해야해서 매우 비효율적인 구조가 됩니다.

이러한 컴퓨터는 후위 표기법을 기반으로 연산을 진행하는데

위의 식을 후위표기식으로 변환하면 다음과 같습니다.

(7+3) * 10 + 2 + 8 * 7  

= 73+10*2+87*+

뭔가 보기 더러워졌습니다.

하지만 스택구조에서는 이 구조가 상당한 효율을 갖습니다. 

먼저 변환 중위 -> 후위 변환 방법을 알아보죠.

일단 변환시 이 규칙을 따릅니다.

1. 계산에 대상이 되는 숫자가 나오면 output에 숫자를 저장해줍니다.

2. ( 괄호가 나오면 스택에 저장해둡니다.

3. ) 괄호가 나오면 스택에 저장해둔 ( 이후에 저장된 모든 연산자를 팝 합니다.

4. 덧셈이나 곱셈등의 연산자가 나올시 동일한 연산순위나 낮은 연산순위가 나올때 까지 스택에서 팝을해서 output에 저장하고 해당 연산자를 스택에 넣어둔다. 

5. 식의 끝에 다다르면 모든 스택을 팝한다.

현재 위치	putput	stack
( 7 + 3 ) * 10 + 2 + 8 * 7		(
( 7 + 3 ) * 10 + 2 + 8 * 7	7	(
( 7 + 3 ) * 10 + 2 + 8 * 7	7	(+
( 7 + 3 ) * 10 + 2 + 8 * 7	73	(+
( 7 + 3 ) * 10 + 2 + 8 * 7	73+	(
( 7 + 3 ) * 10 + 2 + 8 * 7	73+	*
( 7 + 3 ) * 10 + 2 + 8 * 7	73+10	*
( 7 + 3 ) * 10 + 2 + 8 * 7	73+10*	+
( 7 + 3 ) * 10 + 2 + 8 * 7	73+10*2	+
( 7 + 3 ) * 10 + 2 + 8 * 7	73+10*2+	+
( 7 + 3 ) * 10 + 2 + 8 * 7	73+10*2+8	+
( 7 + 3 ) * 10 + 2 + 8 * 7	73+10*2+8	+*
( 7 + 3 ) * 10 + 2 + 8 * 7	73+10*2+87	+*
( 7 + 3 ) * 10 + 2 + 8 * 7	73+10*2+87*+

이렇게 변환된 후위 표기법연산은 아래와 같이 연산된다.

1, 숫자를 만나면 스택에 push

2. 연산자를 만나면 넣어둔 스택에 두개의 숫자를 해당연산자로 연산후 해당 값을 푸쉬

위의 규칙을 적용하면 아래의 순서를 가진다.

현재위치	stack
73+10*2+87*+	7
73+10*2+87*+	7 3
73+10*2+87*+	10
73+10*2+87*+	10 10
73+10*2+87*+	100
73+10*2+87*+	100 2
73+10*2+87*+	102
73+10*2+87*+	102 8
73+10*2+87*+	102 8 7
73+10*2+87*+	102 56
73+10*2+87*+	158

의외로 위의 변환규칙을 읽으면서 하는게 더 헷갈린 묘한 표기법이 나타난다. 

물론 프로그래밍하면서 이걸 세세하게 염두하는건 2000년대 이전에서 였기에 컴퓨터가 이런식으로 연산을 하는걸 선호한다! 정도로 기억해두면 좋다.