자료구조(5) 스택

스택은 나중에 들어간것이 먼저 나오는 구조다 보니 "후입선출" 방식의 자료구조라고도 불리고 LIFO(Last-in, First-out)구조의 자료구조라고도 불린다.

 

스택자체는 어려운것 아니나, "스택의 활용", "스택 기반의 알고리즘"과 관련된 전통적인 예가 하나 있는데, 이것이 의외로 간단하지 않다. 오히려 스택을 공부하는 것보다 이것을 경험하는데 더 많은 노력이 필요할것이다.

 

스택은 배열을 이용해서도 구현이 가능하고, 또 연결 리스트를 이용해서도 구현이 가능하다.

 

사실 배열구조도 자료구조이다. 그럼에도 불구하고 리스트의 구현의 도구로 사용하지 않는가? 마찬가지로

연결리스트도 하나의 자료구조이만 다른 자료구조의 구현에 사용되는 중요한 도구이기도 하다. 어찌 보면

연결리스트는 다른 자료구조의 구현에 사용되는 도구로써 더 큰 의미를 지닌다고 볼 수 있다.

 

스택을 활용한 계산기 프로그램 구현

우리에게 익숙하지 않은 "전위 표기법의 수식"이나 "후위 표기법의 수식"에는 연산순서의 정보가 담겨 있다.

배치순서를 근거로 한 연산순서의 정보가 담기기 때문에, 이를 대상으로 한 연산자의 우선순위가 필요하지 않다. 연산자의 우선순위란 중위 표기법만을 위한 것이다. 뿐만 아니라, 연산자의 배치순서를 바꿈으로써 연산의 순서를 바꿀 수 있기 때문에, 소괄호를 필요로 하지도 않는다.

 

전위표기법의 수식과, 후위 표기법의 수식을 대상으로 한 계산기를 구현하는 것이 중위 표기법의 수식을 대상으로 한 계산기의 구현보다 훨씬 더 수월하다. 왜냐하면 연산자의 우선수위를 신경쓰지 않아도 되고, 소괄호도 처리할 필요가 없기 때문이다.

 

참고로 프로그램상에서 작성하는 연산문도 컴파일러에 의해서 후위표기법으로 바뀌어 처리가 된다.

 

구현할 계산기는 다음 과정을 거친다

• 중위 표기법의 수식 후위 표기법의 수식으로 바꾼다. (1.알고리즘)
• 후위 표기법로 바뀐 수식 계산하여 그 결과를 얻는다. (2.알고리즘)

각각의 과정 모두 알고리즘이 필요하다.

 

2/1중위 표기법을 후위 표기법으로 바꾸는 알고리즘(소괄호 고려 X)

1. 숫자는 바로 오른쪽으로 옮긴다.
2. 연산자의 경우 쟁반위에 쌓는다
3. 연산자가 쟁반에 있다면 우선순위를 비교하여 처리 방법을 결정한다.
4. 마지막까지 쟁반에 남아있는 연산자들은 하나씩 꺼내서 옮긴다.

 

쟁반에 위치한 연산자의 우선순위가 높다면

1. 쟁반에 위치한 연산자를 꺼내서 변환된 수식이 위치할 자리로 옮긴다.
2. 그리고 새 연산자는 쟁반으로 옮긴다.

쟁반에 위치한 연산자의 우선순위가 낮다면

1. 쟁반에 위치한 연산자의 위에 새 연산자를 쌓는다

쟁반에 위치한 연산자와 우선순위가 같다면

1. 쟁반에 위치한 연산자가 우선순위가 높다고 가정하고 일을 진행한다 즉,

쟁반에 위치한 연산자를 꺼내서 변환된 수식이 위치할 자리로 옮긴다
(사칙연산의 경우 연산자의 우선순위가 동일하면, 먼저 등장한 연산자를 먼저 진행한다)

쟁반에 위치한 연산자가 2개 이상이라면,  쟁반 위에있는 것부터 하나씩 비교연산하여 일을 진행한다.

1. 하나씩 비교하면서 쟁반에 위치한 연산자의 우선순위가 같거나, 높다면 변환된 수식이 위치할 자리로 옮긴다.

 

• 쟁반으로 이동하는 연산자는 자신보다 나중에 연산이 이뤄져야 하는 연산자의 위에 올라서 있어야 한다.
• 우선순위가 높은 연산자는 우선순위가 낮은 연산자 위에 올라서서, 우선순위가 낮은 연산자가 먼저 자리를 잡지 못하게 한다"

 

사실 후위표기법으로 작성된 수식 계산방법도 모르는 상태에서 변환의 원리를 이해하는 것은 무리가 있다.

후위표기법의 계산방법을 이해하고 나서 다시 변환의 과정을 돌아보면 변환의 과정에 나름의 이해가 생길것

 

2/2중위 표기법을 후위 표기법으로 바꾸는 알고리즘(소괄호 고려 O)

 

후위 기법의 특징

"후위 표기법 수식에서는 먼저 연산이 이뤄져야 하는 연산자가 뒤에 연산이 이뤄지는 연산자보다 앞에 위치해야 한다" 따라서 예시 (1 + 2 * 3) / 4  이 수식에서는 / 연산자보다 +연산자와 *연산자가 먼저 쟁반에서 빠져나가야 한다.

 

소괄호도 연산자와 마찬가지로 쟁반에 쌓아 올린다. 그래야 어디까지가 소괄호 안에 포함된 연산자인지 구분할 수 있기 때문이다

 

연산자 ( 와 ) 를 포함한 수식 + , 1 , ( , ) 이 9개의 문자로 이뤄져 있다면, 변환 후에는 7개의 문자로 이뤄진 수식이 된다. 왜냐하면 후위 표기법은 소괄호의 정보를 반영해서 연산자를 배치하기 때문이다. 즉, 후위 표기법으로 변환을 하면서 소괄호는 소멸된다!

 

( 연산자는 +연산자가 들어온다고 해서 쟁반 밖으로 튀어나가면 안된다. ( 연산자는 ) 연산자가 등장할 때 까지 쟁반에 남아서 소괄호의 경계를 구분하는 도구로 사용되어야 한다. 따라서 ( 연산자의 우선순위는 그 어떤 사칙 연산자들보다 낮다고 간주한다.

 

스택에서의 ) 연산자의 의미는 "제가 소괄호의 끝입니다! 그러니 ( 연산자 이후에 쌓인 연산자들은 쟁반에 꺼내어 변환된 수식의 자리로 옮겨야 합니다" 따라서 ( 연산자를 만날때까지 쟁반에서 연산자를 하나씩 꺼내어 변환된 수식의 자리로 옮겨야 한다. 물론 소괄호 ) 은 쟁반으로 옮길 필요가 없고, 소괄호 ( 은 변환된 수식이 위치할 자리에 옮기지 않아도 된다.

 

정리 : 소괄호의 끝을 의미하는 ) 연산자가 담고 있는 메세지는, ( 이후에 쌓인 연산자들의 변환된 수식의 자리로 옮기라는 것이다. 때문에 ) 연산자는 변환된 수식의 자리로 옮기지 않아도 된다. 메세지만 취하고 버리면됨.

 

Quiz

문제 : ( 1 * 2 + 3 ) / 4

정답 : 1 2 * 3 + 4 /

나의 오답 : 1 2 3 + *  /

오답의 이유 :

연산자가 스택에 쌓이면 그 이후의 모든 연산자가 ) 연산자를 만날때까지 스택에 쌓이는줄암

즉, 연산자를 만날때까지 다른 연산자들을 스택에 쌓는게 아니라 원래처럼 우선순위비교를 한다는 뜻

 

중위 표기법을 후위 표기법으로 프로그램의 구현

• void ConvToRPNExp(char exp[ ]) // 후위 표기법의 수식으로 변환
• int GetOpPrec(char op) // 연산자의 연산 우선순위 정보를 반환
• int WhoPrecOp(char op1, char op2) // GetOpPrec 함수의 호출 결과를 바탕으로 두 연산자의 우선순위를 비교하여, 그 결과를 반환하는 값

 

GetOpPrec함수에서 ) 연산자에 대한 반환 값은 정의되어 있지 않다.

그 이유는 연산자는 소괄호 끝에 관한 메세지를 전달할 뿐이므로, 메세지만 취하고 버려지기 때문이다.

 

후위 표기법으로 표현된 수식의 계산방법

 

앞에서 언급했듯이, 후위 표기법에서는 먼저 연산되어야 하는 연산자의 수식의 앞쪽에 배치된다. 그렇다면

진행이 되는 피연산자는 무엇일까? 후위 표기법에서는 다음의 기준을 근거로 피연산자를 선택하게 된다.

"후위 표기법의 수식에서는 연산자의 앞에 등장하는 두 개의 숫자가 피연산자입니다"

즉 (3 2 4 * + )은 (3 8 +)이되고 11이 된다.

 

앞서 보인 계산방법 스택을 이용하면 매우 쉽게 프로그램으로 옮길 수 있다. 프로그램으로 옮기기 위한 기본 원칙 세가지는 다음과 같으며, 이는 수식을 구성하는 문자의 처리 기준이 된다.

• 피연산자(숫자)는 무저건 스택으로 옮긴다.
• 연산자를 만나면 스택에서 두 개의 피연산자를 꺼내서 계산을 한다.
• 계산결과는 다시 스택에 넣는다