스택 연습 계산기 프로그램 구현하기
단순한 사칙연산이 아니라 복잡한 연산을 할 수 있는 수준의 계산기를 구현할 예정
계산할 수식 예시는 다음과 같다
( 3 + 4 ) * ( 5 / 2 ) + ( 7 + ( 9 - 5 ) )
위 같은 계산을 하기위해 다음 두 가지를 고려해야한다.
- 소괄호를 파악하여 그 부분을 먼저 연산한다.
- 연산자의 우선순위를 근거로 연산의 순위를 결정한다.
계산기를 구현하기 위해서는 별도의 알고리즘을 이해할 필요가 있다
수식 표기법 : 중위(infix), 전위(prefix), 후위(postifix) 표기법
중위, 전위, 후위 표기법은 다음과 같다
- 중위 표기법(infix notation)
- 예) 5 + 2 / 7
- 전위 표기법(prefix notation)
- 예) + 5 / 2 7
- 후위 표기법(postfix notation)
- 예) 5 2 7 / +
보면 일반적으로 우리에게 익숙한 것은 중위 표기법이다. 우리는 중위 표기법을 보면서 우리는 수식의 우선순위를 알 수 있지만 컴퓨터는 그렇지 않다
그래서 우리는 연산 순서를 컴퓨터가 알아 볼 수 있도록 연산 순서의 정보를 담아서 전달 할 수 있게 후위 표기법을 사용한다.
후위 표기법은 연산 순서의 정보가 담겨있다.
만약 후위 표기법으로 작성된 수식이 다음과 같다면 5 2 4 op1 op2 op1이 op2 보다 앞에 위치해 있기 때문에 op1을 연산하고 op2를 연산하는 것을 알 수 있다.
사실 연산자의 우선순위는 중위 표기법에만 있는 개념이다. 전위, 후위 표기법에는 연산자의 위치로 연산 순서를 알 수 있다.
중위 표기법을 후위 표기법으로 변경하기
우선 우리가 구현할 계산기를 위해 가장 먼저 해야할 작업이 중위 표기법을 후위 표기법으로 변경하는 것이다.
변경하는 과정은 다음과 같다.
우선 수식의 모든 요소들 연산자와 피연산자를 각각 하나의 블럭으로 생각한다.
5 + 2 / 7이라는 수식을 예시로 한다면 5 + 2 / 7으로 본다.
그럼 가장 왼쪽 블럭부터 끝까지 하나씩 옮긴다
5 + 2 / 7 |||| . . . . .
만약 피연산자라면 그냥 옮긴다.
. + 2 / 7 |||| 5 . . . .
연산자는 중간에 스택에 담는다
. . 2 / 7 || + || 5 . . . .
. . . / 7 || + || 5 2 . . .
중요한 부분
다음 연산자를 가운데 스택을 넣어야 하는데 스택에 넣을 때는 스택에 담겨있는 연산자와 우선순위를 비교해야한다.
- 스택에 위치한 연산자의 우선순위가 높거나 같으면
- 스택에 위치한 연산자를 꺼내 변환된 수식으로 옮긴다
- 새 연산자는 스택에 담는다
- 스택에 위치한 연산자의 우선순위가 낮으면
- 스택에 위치한 연산자 위에 다음 연산자를 쌓는다.
+ 보다 /가 연산 순위가 높기 때문에 그냥 쌓는다
. . . . 7 || + / || 5 2 . . .
. . . . . || + / || 5 2 7 . .
. . . . . || + || 5 2 7 / .
. . . . . || || 5 2 7 / +
최종적으로 5 2 7 / +로 수식이 변경됐다.
✔만약 둘 이상의 연산자가스택에 있을 때는
만약 위 예시에서 + / 두 개의 연산자가 있는 상태에서 -가 들어가야 한다면 앞의 두 연산자를 모두 빼고 - 연산자를 넣는다
'(' 와 함께 사용하기
여기서 우리는 괄호를 사용한다
그럼 (를 가장 먼저 스택에 넣고 위 연산자 순서대로 처리한 이후 )가 나오면 끝내는 방식으로 진행하면 된다.
프로그램 구현
중위 표기법을 후위 표기법으로 바꾸는 프로그램을 구현할 차례이다
하지만 구현하기 전에 우선적으로 정의해야 하는 함수가 있다.
첫 번째로 연산자의 우선순위를 구분하는 함수를 정의한다.
연산자 우선순위 구분
int GetOpPrec(char op)
{
switch(op)
{
case '*':
case '/':
return 5;
case '+':
case '-':
return 3;
case '(':
return 1;
}
return -1;
}*, /은 가장 우선순위로 +,-은 그 다음 마지막으로 (를 가장 아래 순위로 설정한다.
( 연산자가 가장 낮은 우선순위인 이유는 )를 받을때까지 스택에 남아있어야하기 때문
연산자 대소 비교
그 다음은 연산자들의 대소를 비교하는 함수를 작성한다
int WhoPrecOp(char op1, char op2)
{
int op1Prec = GetOpPrec(op1);
int op2Prec = GetOpPrec(op2);
if (op1Prec > op2Prec) return 1;
else if (op1Prec < op2Prec) return -1;
else return 0;
} 표기법 변환 코드
void ConvToRPNExp(char exp[])
{
Stack stack;
int expLen = strlen(exp);
char * convExp = (char *)malloc(expLen+1); // 변환된 수식을 담을 공간 준비
int i, idx = 0;
char tok, popOp;
memset(convExp, 0, sizeof(char)*expLen+1); // 할당된 배열을 0으로 초기화
StackInit(&stack);
for(i=0; i<expLen; i++)
{
tok = exp[i];
if(isdigit(tok))
{
convExp[idx++] = tok;
}
else
{
switch(tok)
{
case '(':
SPush(&stack, tok);
break;
case ')':
while(1)
{
popOp = SPop(&stack);
if(popOp == '(') break;
convExp[idx++] = popOp;
}
break;
case '+': case '-': case '*': case '/':
while(!SIsEmpty(&stack) && WhoPrecOp(SPeek(&stack), tok) >= 0)
convExp[idx++] = SPop(&stack);
SPush(&stack, tok);
break;
}
}
}
while(!SIsEmpty(&stack))
convExp[idx++] = SPop(&stack);
strcpy(exp, convExp);
free(convExp);
}계산하기
후위 표기법으로 변경한 수식을 계산할 차례가 왔다
수식을 계산하는 프로그램의 순서
- 피연산자(숫자)는 전부 스택으로 옮긴다
- 연산자를 만나면 스택에서 피연산자 두 개를 꺼내서 계산
- 계산한 값을 다시 스택에 넣는다
계산 구현
int EvalRPNExp(char exp[])
{
Stack stack;
int expLen = strlen(exp);
int i;
char tok, op1, op2;
StackInit(&stack);
for(i=0; i<expLen; i++)
{
tok = exp[i];
if(isdigit(tok))
{
SPush(&stack, tok);
}
else
{
op2 = SPop(&stack);
op1 = SPop(&stack);
switch(tok)
{
case '+':
SPush(&stack, op1+op2);
break;
case '-':
SPush(&stack, op1-op2);
break;
case '*':
SPush(&stack, op1*op2);
break;
case '/':
SPush(&stack, op1/op2);
break;
}
}
}
return SPop(&stack);
}최종정리
중위 표기법을 후위 표기법으로 변경하는 코드, 후위 표기법 계산하는 코드
두 가지를 모두 완성했으니 이제 두 코드를 하나로 만들차례이다.
int EvalInfixExp(char exp[])
{
int len = strlen(exp);
int ret;
char * expcpy = (char *)malloc(sizeof(len+1));
strcpy(expcpy, exp);
ConvToRPNExp(expcpy);
ret = EvalRPNExp(expcpy);
free(expcpy);
return ret;
}