수식 표현 방법 (중위, 전위, 후위)

수식 표현 방법

중위표기법(Infix Notation) : 사람들이 일반적으로 사용하는 방식. 연산자가 피연산자 중간에 온다.

(예 : 1+1, 5 * 3, 10/2)

 

전위표기법(Prefix Notation) : 연산자가 피연산자 앞에 오는 방식

(예 : +11, * 5 3, / 10 2)

 

후위표기법(Postfix Notation) : 연산자가 피연산자 뒤에 오는 방식

(예 : 1 1 +, 5 3 *, 10 2 /)

 

* 중위표기법은 연산자 간 우선순위를 괄호를 통해 표현하기 때문에 연산에는 비효율적이다. 

-> 후위표기법을 이용하여 연산시간 단축한다. (스택이용)

 

스택을 이용한 후위표기법 변환

1. 입력 받은 데이터가 숫자(피연산자)라면 후위표기법변수에 저장 

2. 입력 받은 데이터가 기호(연산자)라면 스택에 Push

* 최상단 연산자보다 우선순위가 높다면 Push

* 최상단 연산자와 우선순위가 같거나 낮다면 pop을 하여 나온 연산자를 후위표기법변수에 저장 

3. 입력 받을 데이터가 없다면, 스택에 있는 연산자 모두 pop

 

스택을 이용한 수식 계산

1. 입력 받은 데이터가 숫자(피연산자)라면 숫자 스택에 push

2. 입력 받은 데이터가 기호(연산자)라면 

* 연산자 스택에 비어 있다면 바로 push

* 최상단 연산자보다 우선순위가 높다면 Push

* 최상단 연산자와 우선순위가 같거나 낮다면 pop을 하여 나온 연산자를 후위표기법변수에 저장 

3. 입력 받을 데이터가 없다면, 스택에 있는 연산자 모두 pop