우리 인간은 2 - 9 * (4 + 3) 형태의
infix(중위표기법)를 사용한다.
하지만 컴퓨터는
postfix(후위표기법) 형태를 사용한다.
그리고
prefix(전위표기법) 라는 것도 있다.
요 3개의 형태를 살펴보면 다음과 같다.
infix 는 4 * 3
postfix 는 4 3 *
prefix 는 * 4 3
스택 계산기라는 것은 사용자에게
infix 형태의 문자열 수식을 입력 받아서
postfix 형태의 수식으로 바꾼 후
계산하는 것이라고 보면 되겠다.
infix 를
postfix 로 바꾸는 방법을 간단히 살펴보면
5 - ( 3 * 4 ) / 3 + 10 이라는 식이 있다.
1. 먼저 이 식에 가능한 모든 괄호를 다 취한다.
( ( 5 - ( ( 3 * 4) / 3 ) ) + 10 )
2. 각 괄호를 기준으로 연산자는 각각 속해있는 괄호의 뒤로 뺀다 .
( ( 5 - ( ( 3 4) * / 3 ) ) + 10 )
( ( 5 - ( ( 3 4) * 3 ) / ) + 10 )
( ( 5 ( ( 3 4) * 3 ) / ) - + 10 )
( ( 5 ( ( 3 4) * 3 ) / ) - 10 ) +
3. 괄호를 모두 지운다.
5 3 4 * 3 / - 10 +
요것이 postfix 이다.
첨부파일은 스택계산기를 구현한 c파일이다.
실행화면은 다음과 같다.
<StackCalc.c>
개발환경 : Ubuntu 11.04 커널 Linux 2.6.38-11-generic
컴파일러 : gcc 4.5.2
gcc로 -lm 붙여서 컴파일했다.
아직 구현 못한 기능이 있는데
- 단항 연산자(unary) 처리는 아직 하지 못했다.
스택이용해서 짜보는게 목적이었기에...
끝.