[자료구조] 스택(stack)의 응용2 : 후위 표기(postfix) 계산 - 컴도리돌이

 

후위(postfix) 표기법

연산자를 피연산자 뒤에 표기

- 컴퓨터에서 수식 계산 순서는 중위표기식 에서 후위표기식으로 걸쳐서 계산을 한다.

  예 ) 2+3*4 --> 234*+ --> 14

- 모두 스택을 사용

 

후위(postfix) 표기법의 장점

 

-괄호를 사용하지 않고도 계산 순서를 알 수 있다.

-연산자의 우선순위를 고려할 필요가 없다.

-수식을 읽으면서 바로 계산할 수 있다.

 

 

후위(postfix) 표기 수식 알고리즘 예시

 

 

 

후위(postfix) 표기 수식 계산 - 수도코드

 

후위(postfix) 표기 수식 계산 - c언어 코드

 

중위 표기 수식의 후위 표기 변환

 

- 피연산자를 만나면 그대로 출력을 하며 연산자를 만나면 스택에 저장했다가 스택보다 우선순위가 낮은 연산자가 나오면 그때 출력한다.

-왼쪽 괄호는 우선순위가 가장 낮은 연산자로 취급하며 오른쪽 괄호가 나오면 스택에서 왼쪽 괄호위에 쌓여있는 모든 연산자를 출력한다.

 

중위 -> 후위 표기 변화 예시