C++ 로 짠 스택 계산기

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으로 컴퓨터가 이해하니깐 ;;;) 조심~