후위표기식으로표현한 스택좀도와주세여~

저는 2001년 대학 2학년 시절 자료구조를 배웠는데 당시는 전산과 학생들의 필수 과목이었습니다.

 

생소한 개념 등으로 이해가 안가고 이거 어디에 써먹나 생각했는데,

전산학의 기초가 되는 과목으로 현재도 자주 인용해 먹곤 합니다. (기초가 중요하다는 이야기)

 

저도 당시 수업시간에 전위, 중위, 후위 표기식으로 계산하는 것이 이해가 안되었는데...

(왜.. 교수님들은 쉽게 설명을 안해주는지... 횽아 들이 더 잘 설명할 때도 종종... 생각이 듭니다.)

 

암튼.. 제가 썼던 방법은 이진 트리 순회(binary tree traverse)를 이용하는 법이었습니다.

사실 제가 가지고 있던 호로비츠의 'C로 쓴 자료 구조론' 책에서는 트리 구조에서 순회시에 전위,중위,후위 표기법을 설명했었습니다.

 

암튼 위에서 제시한 식(a+b)*((c-d)*e+f)을 이진 트리로 그려보면...

아래와 같습니다. (손으로 그린것을 사진으로 찍었습니다.ㅡㅡ)

 

해당 식으로 나오는 트리는 동일한데, 순회를 어떻게 하느냐에 따라 중위, 전위, 후위 표기가 바뀝니다.

순회란 트리에 있는 모든 노드를 한 번씩만 방문하는 것을 의미합니다.

 

중위(질문자가 제시한 표기법이 바로 그것임)의 경우는 아래와 같은 형태로 순회 한다고 보시면 됩니다.

 

번호를 붙여보면

 와 같습니다.

잘 보시면 4번 이후에 + 가 5가 아니라 c가 5번인 것을 알수 있는데
우 대각으로 내려갈 경우에 왼쪽에 노드가 있을 경우에는
처음처럼 좌 대각으로 끝을 만날 때까지 내려간다고 생각하시면 되겠습니다.

a+b * c-d *e + f 맞지요...우선순위를 위해 괄호를 써야 되겠네요...(a+b) * (((c-d) *e) + f)

 

이해가 되시나요?

 

이젠 질문하신 후위 표기법으로 넘어가겠습니다.

 

후위는 아래 자식 노드 2개를 방문하고
그 위의 부모를 방문하는 방식입니다.

그림으로 설명하면 아래와 같은 방향으로 진행합니다.

 

번호를 붙여보면

과 같습니다.

맨처음 좌 대각으로 쭉 내려가고,,, 막다른 노드면 오른쪽 자식 노드 방문하고, 부모 노드 방문하고...

이런 순서대로 반복을 하면되는데..

여기서 3번 다음 4번이 +가 아니라 c인 이유는 좌대각 아래에 노드가 있기 때문입니다.

처음 처럼 좌 대각으로 쫙 내려가서 오른쪽 자식 노드-부모 노드를 진행하면 되겠습니다.

 

따라서 답은 ab+cd-e*f+* 이네요...

 

위에서 스택을 언급하셨는데...

재미있는 것은 이 후위 표기식이 스택 기반 머신에서 연산하기에 적합하다는 것입니다.

이 스택 머신은 피 연산자가 오면 스택에 넣고(push), 연산자(+-/* 등)가 오면 피연산자를 꺼내서(pop)

계산(평가, evaluation)을 하고 다시 결과를 스택에 넣는(push) 식으로 동작을 합니다.

 

설명을 돕기 위해 간단히 예를 들어보면

와 같습니다.

 

뒷 부분은 생략했으나 위의 정도까지 따라 오신다면 끝까지 그려보실 수 있을 거에요..