- 후위표기법 (postfix)
: 수식의 피연산자를 먼저 표기하고 연산자를 나중에 표기하는 방법
( 1+2x3 ==> 123x+ )
[ 입력 ]
- 후위표기법으로 표기된 수식 입력
- 수식의 길이 ≤ 100
- 수식에는 공백 없이 입력
- 수식의 모든 계산과정의 결과 ≤ 2,147,483,647
- 0으로 나누는 경우는 없음
- 잘못된 수식이 입력되는 경우 없음
[ 출력 ]
- 입력으로 주어진 수식의 답 출력
후위표기법은 다음과 같이 표기가 된다. ( 보통의 수식 기준 )
- 피연산자 : 중위표기법 수식의 앞부터 순서대로 표기
- 연산자 : 중위표기법 수식의 뒤부터 순서대로 표기
- ex) 1 + 2 x 3 ( 중위표기 수식 )
- 피연산자 : 123
- 연산자 : x+
- ∴ 123x+ ( 후위표기 수식 )
위와 같이 표기가 되기 때문에 후위표기로 된 수식의 피연산자들을 stack에 push 하고, 연산자를 만났을 때 피연산자의 가장 뒷부분, 즉 stack의 top의 원소들을 가져와 연산자와 계산한다.
이때 연산자 종류 계산 시 if 문으로 4가지 경우를 나눠 계산한다.
※ 나눗셈 연산의 순서 주의
: stack에서 원소를 두개 추출하는데 가장 위에 있던 숫자를 a, 그 바로 아래에 있던 숫자를 b로 봤을 때
- a / b (x)
- b / a (o)
로 계산하여야 한다. ( +, -, x 는 상관없고 나누기에만 영항이 있음. )