3장 - 수식 계산(Evaluation of Expressions)

Precedence : 연산자들 간의 우선 순위(*연산이 +연산보다 우선순위 높음)

Associativity: 동일한 우선순위를 갖는 연산자들간의 실행 순서 (ex: +,-,*,/ - >left to right)

 

중위 표기법(Infix notation)

: 피연산자들 사이에 연산자가 위치함. 사람이 쓰는 방식. 계산 과정이 복잡하다

 

후위 표기법(Postfix notation)

: 피연산자들 다음에 연산자가 위치. 괄호가 필요 없고 한번의 스캔으로 수식 계산 가능

 

중위표기법 3+4*2 ==> 후위표기법 342*+ 

(a/(b - c + d) ) * (e - a ) * c ==> abc-d+/ea-*c*

 

Postfix 수식의 계산

앞에서부터 차례대로

피연산자(숫자)는 스택에 저장,

연산자의 경우 스택에서 숫자 2개를 pop하여 연산하고, 결과값을 push 한다.

 

Infix 수식을 Postfix 수식으로 변환.

앞에서부터 차례대로

피연산자(숫자)는 그대로 출력,

연산자의 경우

(stack top에 있는 연산자를 top,

수식에서 읽은 연산자를 incoming이라고 하겠음)

연산자 우선순위를 비교한다.

top < incoming 인 경우 incoming을 스택에 push함.

top > incoming 인 경우 top을 출력하고 incoming을 push 함

top = incoming 인 경우 결합법칙에 따라 출력.(left to right 인지 right to left인지)

 

근데 우리가 짜는 프로그램에서는 연산자는 모두 left to right라고 가정함

그럼

top < incoming 인 경우 incoming을 스택에 push,

top>= incoming 인 경우 스택에서 top>=incoming에 해당하는 모든 연산자를 pop하고 incoming push.