http://blog.daum.net/broodsc/2714333
오늘은 스택을 이용한 CALC 유틸리티(이하 CALC)에 관해서 설명(??)하겠습니다. ㅋ
CALC는 그냥 계산기 정도로 생각하시면 될듯...
CALC 유틸리티
수식을 중위표기법(Infix notation)으로 받아서 그걸 후위표기법(Postfix notation)으로 바꾸고...
이 후외 표기법의 수식을 스택을 이용하여 연산하여서 화면에 출력하게 하는 것...
이게 이 프로그램의 작동방식(??) 입니다. ;;;
여기서도 제한을 둡시다.
이 CALC는 간단한 정수와 사칙연산만 가능하게 한다는것.
그리고 입력시 스페이스를 넣으면 원하지 않으면 결과가 나올 수도 있다는 것.
뭐 다른 기능을 포함시키는것도 이 소스를 바탕으로 개선하시면 될듯 합니다.
방법 )
1. 수식의 표기법
보통 우리가 사용하는 수식은 뭘까요??
2 + 3 * (1 + 2) 이런 수식이죠??
이런걸 중위표기법(Infix notation)이라고 한답니다.
이유는?? 연산자가 두 피연산자 사이에 있어서... ;;;
1 + 2 를 보면 피연산자 1, 2 사이에 연산자 '+' 가 있죠?? ㅋ
그럼 연산자가 뒤에나 앞에 올 수도 있을까요?? 정답은 "그렇다" 입니다.
1 + 2 를 전위표기법(Prefix notation)으로 고치면 + 1 2 가
되겠고...
후위표기법(Postfix notation)으로 고치면 1 2 + ㅇㅋ??
그렇다면 왜 중위표기법을 놔두고 후위표기법을 이용하여 계산을 할려고 하는지??
그 이유가 궁금하지 않으신가요?? ;;;
그 이유는 중위표기법은 우리가 이해하기는 쉽지만 괄호를 만드시 써야하는 단점이 있다는 ;;;
위에보면 2 + 3 * (1 + 2) 이 식 있죠??
이 식에서 괄호를 제외한다면... 2 + 3 * 1 + 2 ...
두개의 수식이 서로 같나요?? 다르죠??
그럼 후위표기법은 괄호 없이도 가능하다는 말인가?? 정답은 "그렇다" 입니다. ㅋ
2. 중위표기법을 후위표기법으로 변환하는 방법 1
우선 뭄풀기(쫌 힘들지만 ;;) 단계로... 이해부터 하기 위해서...
한가지 제한을 두고 합시다.
뭐냐하면... 수식을 쓸때 무조건 괄호를 씌우는걸로...
예를들면 2+3*2 같은 경우에도 (2+(3*2)) 이런 식으로...
그럼 이걸 어떻게 후위표기법으로 변환할까요??
1. '(' 문자는 무시하고 넘어간다.
2. 피연산자는 그대로 출력한다.
3. 연산자는 스택에 푸시한다.
4. ')' 를 만나면 스택에서 팝하여 출력한다.
예를 들어 봅시다. (A + (B * C)) 라는 식...
'('는 무시한다고 그랬으니깐... 넘어가고 그 다음 'A'
'A'는 여기서 피연산자죠?? 그렇다면 출력. ( 출력 : A | 스택 : )
그 다음 '+' 이건 연산자... 그러니깐 푸시 ( 출력 : A | 스택 : + )
다음은 '(' ... 이건 무시.
그 다음 'B' 피연산자니깐 출력 ( 출력 : A B | 스택 : + )
다음은 '*' 연산자니깐 푸시 ( 출력 : A B | 스택 : * + )
그 다음 'C' 피연산자이므로 출력 ( 출력 : A B C | 스택 : * + )
그 다음 ')' ...
')' 만나면 스택에서 팝하여 출력이니깐... (출력 : A B C * | 스택 : + )
그 다음 또 ')'를 만났으니깐... 팝 하여 출력 (출력 : A B C * + | 스택 : )
그럼 (A + (B * C)) 의 후위표기법은 A B C * + 라는 결과가 나왔죠??
이제 이걸 가지고 C로 만들어 봅시다.
void postfix1(char *dst, char *src)
{
char c;
init_stack(); /* 스택을 초기화
*/
while(*src)
{
if(*src==')') /* ')'를 만나면 팝하여 출력(dst에 저장)
*/
{
*dst++=pop();
*dst++=' '; /* 문자의 구분을 위해 */
src++;
}
else if(*src=='+' || *src=='-' || *src=='*' ||
*src=='/')
{ /* 연산자이면 스택에 푸시 */
push(*src);
src++;
}
else if(*src>='0' &&
*src<='9')
{ /* 숫자는 피연산자. 숫자를 그대로 복사 */
do
{
*dst++=*src++;
}
while(*src>='0' && *src<=9');
*dst++=' ';
}
else /* 그 외에는 무시 */
src++;
}
*dst=NULL; /* 마지막에 NULL 문자
추가해서 문자열로... */
}
이건 쫌 쉽죠?? ;;;
3. 중위표기법을 후위표기법으로 변환하는 방법 2
위에 방법은 괄호가 꼭 있어야 했습니다.
그렇다면 이제 괄호가 없어도 우선순위에 맞춰서 변환하는걸 해 봐야겠죠??
이게 실제적으로 더 편리하고 유용한거니깐...
일단 우선순위를 고려해 줘야하니깐... 연산자별로 우선순위를 줍시다.
'(' 는 0, '+' 와 '-' 는 1, '*' 와 '/' 는 2 ...
1. '(' 를 만나면 스택에 푸시한다.
2. ')' 를 만나면 스택에서 '(' 가 나올 때까지 팝하여 출력하고 '(' 는 팝하여
버린다.
3. 연산자를 만나면 스택에서 그 연산자보다 낮은 우선순위의 연산자를 만날 때까지 팝하여 출력한 뒤에
자신을 푸시한다.
4. 피연산자는 그대로 출력한다.
5. 모든 입력이 끝나면 스택에 있는 연산자들을 모두 팝하여 출력한다.
후... 역시 이 책의 최대 약점이 또 다시 느껴지는군요...
직접 만들어볼 틈을 주기전에 이런 알고리즘을 제공하니깐... ;;;
보고 또 보고 해서 우리걸로 만들면 되겠죠?? 전 그렇게 할 수 있다고 스스로 믿을겁니다. ^^
예를 들어 봅시다.
(2 * (3 + (6 / 2) + 2) / 4 + 3 ... 차례대로... (그림 눌러서 보세요. 3자가 잘 안보이네요 ㅋ)
휴~
이걸 가지고 함수를 만들기 전에...!!
몇가지 간단한 함수부터 만들고 넘어갑시다. ^^
먼저...
int get_stack_top(void)
{
return (top < 0) ? -1 :
stack[top];
}
이 함수는 스택의 최상단값을 리턴해주는 겁니다.
푸시될 연산자보다 높은 순위의 연산자가 스택의 상단에 있는지 없는지 보기 위해서...
그 다음 주어진 문자가 연산자인지 아닌지 판별하는 함수
int is_operator(int k)
{
return (k == '+' || k ==
'-' || k == '*' || k == '/');
}
두개 다 간단하죠??
그 다음... 연산자 우선순위를 수치로 바꿔주는 함수
int precedence(int op)
{
if (op == '(') return
0;
if (op == '+' || op ==
'-') return 1;
if (op == '*' || op ==
'/') return 2;
else
return 3;
}
흠... 이제 이 세 함수를 사용해서... 중위표기법 → 후위표기법 함수를 만들어 볼까요?? ;;;
void postfix(char *dst, char *src)
{
init_stack(); /* 스택 초기화
*/
while
(*src)
{
if (*src == '(') /* ( 를 만나면 푸시
*/
{
push(*src);
src++;
}
else if (*src == ')') /* ) 를 만나면 ( 가 나올 때까지 팝
*/
{
while
(get_stack_top() != '(')
{
*dst++ = pop();
*dst++ = ' ';
}
pop();
src++;
}
else if (is_operator(*src)) /* 연산자이면
*/
{
while
(!is_stack_empty() &&
precedence(get_stack_top()) >=
precedence(*src))
{ /*
우선순위가 높은 연산자들을 모두 팝 */
*dst++ = pop();
*dst++ = ' ';
}
push(*src); /* 그리고 푸시 */
src++;
}
else if (*src >= '0' && *src <=
'9') /* 피연산자는 그냥 출력 */
{
do
{
*dst++ = *src++;
}
while (*src >= '0' && *src <= '9');
*dst++
= ' ';
}
else
src++;
}
while (!is_stack_empty())
/* 모두 끝났으면 스택에 있는 모든 내용을 팝 */
{
*dst++ = pop();
*dst++ = ' ';
}
dst--;
*dst =
0;
}
4. 후위표기법 수식의 평가
후위 표기법 계산을 나타내는건 의외(??)로 쉽습니다.
1. 숫자를 만나면 스택에 푸시
2. 연산자를 만나면 두번 팝해서 그 두 데이터를 가지고 연산한 다음 다시 스택에
푸시
쉽... 죠?? 그러리라 믿습니다. ㅋ
예를들어 2 + 3 * 4 ... 이걸 후위표기법으로 나타내면 2 3 4 * +
2 3 4 는 숫자이므로 차례대로 푸시 ( 스택 : 4 3 2 )
그 다음 * ... '*' 는 연산자니깐 팝 두번하면 4 3 이거 두개를 * 연산해주면 12
12을 다시 푸시 ( 스택 : 12 2 )
그 다음 + ... '+' 는 연산자니깐 팝 두번하면 12 2 이거 두개를 + 연산하면 14 끝 !!
간단하죠??
단 한가지만 조심하면 됩니다. '-' 와 '/' 연산...
'+' 나 '*' 는 교환법칙이 성립하므로 팝 두번하여 그냥 계산하면 됩니다.
그러나 '-' 또는 '/' 는 교환법칙이 성립안합니다. 그러므로 팝을 따로 해주어야합니다.
그냥 pop() - pop() 를 하면 앞에 팝이 먼저 실행될지 뒤에 팝이 먼지 실행될지 모르기때문에...
그래서 팝을 한번 해서 저장해 둔 뒤에 그 값과 다음에 팝 하는 값을 계산해 주어야함.
그럼 이제 계산하는 함수를 만들어 볼까요??
int calc(char *p)
{
int i;
init_stack();
while
(*p)
{
if (*p >= '0' && *p <=
'9')
{
i =
0;
do
{
i = i * 10 + *p - '0';
p++;
}
while (*p >= '0' && *p <= '9');
push(i);
}
else if (*p == '+')
{
push(pop() + pop());
p++;
}
else if (*p == '*')
{
push(pop() * pop());
p++;
}
else if (*p == '-')
{
i =
pop();
push(pop() - i);
p++;
}
else if (*p == '/')
{
i =
pop();
push(pop() / i);
p++;
}
else
p++;
}
return
pop();
}
한가지 눈여겨 볼것 더... 바로 숫자열을 정수로 변환하는 것...
atoi() 라는 아시는 분이라면 쉽게 이해하실텐데...
int atoi(char *s)
{
int
i=0;
while(*s>='0'
&& *s<='9')
i = i * 10 + *s++ - '0';
return
i;
}
이게 바로 atoi() 함수입니다. 보시고 쪼끔만 생각하시면 이해하실듯...
결과 )
실행은
"CALC(파일이름) 수식" 하면 됩니다.
단, 스페이스를 사이에 집어 넣으면 원치 않은 결과가 나오니깐...
(공백이 있다면 argc 3으로 컴퓨터가 이해하니깐 ;;;) 조심~
