계산기 프로그램 구현
우리가 만들 계산기는 다음 두가지를 고려해서 연산이 가능해야 한다.
1. 소괄호를 파악하여 그 부분을 먼저 연산한다.
2. 연산자의 우선순위를 근거로 연산의 순위를 결정한다.
계산기의 구현에 필요한 알고리즘을 소개한다.
수식표기법 : 중위(infix), 전위(prefix), 후위(postfix) 표기법
계산기의 구현에 필요한 부가적인 것을 설명하기에 앞서 우리가 구현할 계산기에 대해 다음과 같이 기능을 제한한다.
"수식을 이루는 피연산자는 한자리 숫자로만 이뤄진다고 가정"
즉 1과 3은 피연산자가 될 수 있지만, 24와 35는 피연산자가 될 수없다.
중위 표기법(infix notation) 5 + 2 / 7
전위 표기법(prefix notation) +5 / 2 7
후위 표기법(postfix notation) 5 2 7 / +
이 중에서 우리에게 익숙한 것은 '중위 표기법"이다. 그러나 중위 표기법을 이용해서 작성된 수식에는 연산 순서에 대한 정보가 담겨있지 않다.
우리는 이미 연산 순서의 우선순위를 알고있기 때문에 미리 판단이 가능하지만 , 만약 중위표기법에 대해 모르는 사람은 연산 순서를 알 수 없다.
하지만 우리에게 익숙하지 않은 후위 표기법의 수식과 전위 표기법의 수식에는 연산 순서의 정보가 담겨있다.
연산자의 종류나 우선순위를 알지 못해도, 연산자가 자리한 위치만 보고서도 판단이 가능하다.
이렇듯 '전위 표기법으로 작성된 수식'과 '후위 표기법으로 작성된 수식'에는 배치 순서를 근거로 한 연산순서의 정보가 담기기 때문에, 이를 대상으로 한 연산자에서는 연산자의 우선순위가 필요치 않다. 다시말해서 연산자의 우선순위란 중위 표기법만을 위한 것이다.
뿐만 아니라, 연산자의 배치 순서를 바꿈으로써 연산의 순서를 바꿀 수 있기 떄문에, 소괄호를 필요로 하지도 않는다. 즉 소괄호도 중위 표기법만을 위한 것이다. 따라서 다음과 같이 결론 내릴 수 있다.
"전위 표기법의 수식이나 후위 표기법의 수식은 연산자의 배치 순서에 따라서 연산 순서가 결정되기 떄문에, 이 두표기법의 수식을 계산하기 위해서 연산자의 우선순위를 알 필요가 없고, 소괄호도 삽입되지 않으니 소괄호에 대한 처리도 불필요 하다."
다음은 중위 표기법의 수식이다.
(1 + 2) * 7
이 중위 표기법의 수식은 다음과 같이 전위 표기법의 수식으로 , 그리고 후위 표기법의 수식으로 얼마든지 변환이 가능하다.
(1+2) * 7 (전위 표기법) -> *+127
(1+2) * 7(후위 표기법) -> 12+7*
그리고 이렇게 변환이 된 전위 표기법의 수식과 후위 표기법의 수식을 대상으로 한 계산기를 구현하는 것이, 중위 표기법의 수식을 대상으로 한 계산기의 구현보다 훨씬 수월하다. 왜냐면 연산자의 우선순위를 신경쓰지 않아도 되고, 소괄호도 처리할 필요가 없기 때문이다.
우리는 수식을 전위표기법 또는 후위 표기법의 수식으로 변환하여 계산이 진행되도록 할것이다. 따라서 우리는 계산기의 구현에 앞서, 중위 표기법의 수식을 전위 표기법 또는 후위 표기법의 수식으로 변환할 줄 알아야 한다.
중위 표기법을 후위 표기법으로 바꾸는 방법 : 1 /2 : 소괄호를 고려하지 않고
우리가 구현할 계산기는 다음의 과정을 거쳐서 연산을 진행하도록 할 계획이다.
1. 중위 표기법의 수식을 후위 표기법의 수식으로 바꾼다.
2. 후위 표기법으로 바뀐 수식을 게싼하여 그 결과를 얻는다.
각각의 과정 모두 별도의 알고리즘이 필요하다. 사실 위의 두 과정은 별개의 과정으로 봐야한다.
따라서 먼저 중위 표기법의 수식을 후위 표기법으로 수식으로 바꾸는 방법에 대해서 고민하겠다. 후위 표기법의 수식을 계산하는 것은 그 다음의 일이기 때문이다. 다음 수식을 후위 표기법으로 변환방법을 설명하겠다.
5 + 2 / 7
다음과 같이 위의 수식을 구성하는 연산자와 피 연산자를 각각을 블록으로 인식하자. 그리고 그 옆에는 쟁반이 있다 가정하자.
| 5 | + | 2 | / | 7 |
위의 상황에서는 우리는 왼쪽에 있는 5가 저장된 피연산잘 블록부터 시작해서 마지막 블록까지 일관된 방식으로 처리를 진행할 것이다. 그리고 그 일관된 처리 방식이 후위 표기법으로의 변환 방법이니 이에 주목해야한다.
위의 그림에서 보면 첫번째 블록은 숫자 5이다. 이렇듯 숫자는 그냥 변환된 수식이 놓일 위치에 놓으면 된다. 따라서 그 결과는 다음과 같다.
| + | 2 | / | 7 |
| 5 |
이어서 두번째 인자로 +연산자가 등장한다. 이렇듯 연산자가 등장하면 일단 쟁반으로 옮긴다. 마침 쟁반이 비어있으니 이곳으로 +연산자를 옮긴다.
쟁반 : +
다음으로 피연산자 숫자 2가 등장하였으니, 다음 그림과 같이 변환된 수식이 놓일 자리로 이동시킨다. 다시 한번 말하지만 숫자는 변환된 수식이 놓일 자리로 바로 이동하면 된다.
| 2 | / | 7 |
| 5 | 2 |
쟁반 : +
이번에는 / 연산자가 등장한다. 연산자이므로 쟁반으로 옮겨야 한다. 그런데 현재 쟁반에 연산자가 있는 관계로 두 연산자간의 우선순위를 비교해야 한다. 그리고 그 결과에 따라서 다음과 같이 행동해야 한다.
-쟁반에 위치한 연산자의 우선순위가 높다면
쟁반에 위치한 연산자를 꺼내서 변환된 수식이 위치할 자리로 옮긴다.
그리고 새 연산자는 쟁반으로 옮긴다.
-쟁반에 위치한 연산자의 우선순위가 낮다면
쟁반에 위치한 연산자의 위에 새 연산자를 쌓는다
따라서 쟁반에 위치한 연산자는 +이고 새 연산자는 /이니 , 다음과 같이 연산자를 쌓으면 된다
쟁반 : + /
참고로 다음과 같이 정리해두면 기억하기가 좋다.
"우선 순위가 높은 연산자는 우선순위가 낮은 연산자 위에 올라서서, 우선순위가 낮은 연산자가 먼저 자리를 잡지 못하게 한다"
후위 표기법에서는 우선순위가 높은 , 먼저 연산이 되어야 하는 연산자가 변환된 수식의 앞 부분에 위치해 야 한다. 때문에 위와 같이 이해하는 것도 하나의 방법이 될 수 있다. 이제 마지막 숫자 7이 남았다. 피 연산자이니 다음과 같이 위치시킨다.
| 5 | 2 | 7 |
쟁반 : / +
이제 끝으로 쟁반에 쌓인 연산자들을 하나씩 꺼내어 변환된 수식이 위치할 자리에 옮기면 된다. 그런데 주의하자.
연산자가 쟁반에 쌓여져잇다. 그래서 아래 있는 것을 먼저 꺼낼 수 없다. 위의 것부터 꺼내서 옮겨야 한다.
따라서 결과는 다음과 같다.
| 5 | 2 | 7 | / | + |
즉 쟁반도 스택이다.
이로써 중위 표기법의 수식을 후위 표기법의 수식으로 바꾸는 과정을 한차례 보였다. 그리고 이는 다음과 같이 정리할 수있다.
-피연산자는 그냥 옮긴다.
-연산자는 쟁반으로 옮긴다.
-연산자가 쟁반에 있다면 우선순위를 비교하여 처리 방법을 겨정한다.
-마지막까지 쟁반에 남아있는 연산자들은 하나씩 꺼내서 옮긴다.
우선 순위 비교후의 처리방법은 앞서 정리하였으니 여기서는 이 정도로 마무리 하겠다. 그런데 지금까지 보인 과정에서 설명하지 못한 경우의 수가 있다.
동일한 우선순위의 연산자가 등장하면 어떻게 해야할까?
사칙연산의 경우 연산자의 우선순위가 동일하면, 먼저 등장한 연산자를 먼저 진행한다.
즉 우선순위가 같아도 먼저 등장한 것이 먼저 연산을 진행하기 때문에 먼저 있는 연산자를 우선순위가 높다고 가정한다.
설명하지 못한 경우의 수가 하나 더있다.
만약 + 연산자와 / 연산자가 쌓여있는 상태에서 -연산자를 쌓아햐 하는 상황을 보여준다.
이경우에는 / 연산자와 +연산자를 모두 옮기고 나서 - 연산자를 쟁반으로 옮겨야 한다. 왜냐하면 둘다 -연산자 보다 먼저 진행되어야 하는 연산자들이기 때문이다.
정리하면 , 쟁반으로 이동하는 연산자는 자신보다 나중에 연산이 이뤄져야 하는 연산자의 위에 올라서 있어야 한다.
이렇게 해서 소괄호가 없 는 중위 표기법의 수식을 후위 표기법으로 바꾸는 방법을 모두 설명하였다.
중위 표기법을 후위 표기법으로 바꾸는 방법 2/2 : 소괄호를 고려하고
이제는 다음과 같이 소괄호가 포함되어 있는 중위 표기법의 수식을 후위 표기법의 수식으로 바꾸는 방법에 대해 생각해보자
( 1 + 2 * 3) /4
물론 문제는 소괄호이다. 이 소괄호를 어떻게 처리해야 할까?
"후위 표기법의 수식에는 먼저 연산이 이뤄져야 하는 연산자가 뒤에 연산이 이뤄지는 연산자보다 앞에 위치해야 한다"
따라서 위의 수식에서는 / 연산자보다 +연산자와 * 연산자가 먼저 쟁반에서 빠져나가야 한다. 그럼 어떻게 해야 그것이 가능하겠는가? 생각보다 간단하다.
"/ 연산자를 쟁반 위에 올릴 때, 쟁반 위에 + 연산자와 *연산자가 존재한다면, 이들을 모두 빼서 변환된 수식의 자리에 가져다 놓는다"
그럼 위의 수식을 대상으로 변환의 과정을 보이겠다. 참고로 이어서 보이는 과정에는 소괄호도 연산자와 마찬가지로 쟁반에 쌓아 올린다. 그래야 어디까지가 소괄호 안에 포함된 연산자인지 구분할 수 있기 때문이다.
| ( | 1 | + | 2 | * | 3 | ) | / | 4 |
위 에서 보이듯이, 변환 이전의 수식은 총 9개의 문자로 이뤄져있다. 하지만 변환 후에는 7개의 문자로 이뤄진 수식이된다. 왜냐하면 후위 표기법은 소괄호의 정보를 반영해서 연산자를 배치하기 때문이다. 즉 후위 표기법으로 변환을 하면서 소괄호는 소멸된다. 그럼 변환의 첫번째 과정을 보자.
| 1 | + | 2 | * | 3 | ) | / | 4 |
쟁반 : (
위와 같이 소괄호도 연산자로 인식하고 쟁반에 올려 놓 는다. 이어서 숫자 1을 옮겨야 하는데 이미 알다시피 숫자는 바로 변환된 수식의 일부가 되므로 과정을 생략한다.
그럼 이어서 +연산자를 옮길 차례이다.
| 2 | * | 3 | ) | / | 4 |
| 1 |
쟁반: ( +
위의 과정에서 주목할 사실이 하나 있다. 그것은 (연산자는 +연산자가 들어온다고해서 쟁반 밖으로 튀어나가면 안된다는 것이다. (연산자는 )연산자가 등장할 때까지 쟁반에 남아서 소괄호의 경계를 구분하는 도구로 사용되어야 한다. 따라서 ( 연산자의 우선 순위는 그 어떤 사칙 연산자들보다 낮다고 간주한다. 이는 변환 프로그램의 구현을 위해서도 알고 있어야 하는 중요한 사실이기 때문에 다음과 같이 정리하자.
" ( 연산자는 ) 연산자가 등장할 때 까지 쟁반 위에 남아 있어야 하기 때문에 사칙 연산자들보다 연산의 우선순위가 낮다고 간주한다"
이제 숫자 2가 변환된 수식의 자리로 이동하고 *연산자가 쟁반 위에 쌓일 차례이다. 그런데 현재 쟁반에 쌓여있는 +연산자보다 *연산자의 우선순위가 높으므로 다음과 같이 +연산자 위에 *연산자를 올려 놓아야 한다. 만약에 +연산자보다 우선순위가 낮은 연산자가 등장했다면 이전에 해오던 데로 +연산자를 변환된 수식의 자리로 이동시키고 나서 새로운 연산자를 쟁반에 올려놔야 한다.
| 3 | ) | / | 4 |
| 1 | 2 |
쟁반 : ( + *
이어서 숫자 3을 변환된 수식의 자리로 옮기고 )연산자를 쟁반 위로 옮길 차례이다. 그런데 이때 등장하는 )연산자가 의미하는 바는 다음과 같다.
"소괄호의 끝이므로, (연산자 이후에 쌓인 연산자들을 쟁반에서 꺼내어 변환된 수식의 자리로 옮겨라"
따라서 소괄호 (을 만날 때까지 쟁반에서 연산자를 하나씩 꺼내어 변환된 수식의 자리로 옮겨야 한다. 이렇듯 소괄호 ) 은 쟁반으로 옮길 필요가 없다. 그저 ( 이후에 쌓인 연사들을 변환된 수식의 자리로 옮기라는 메세지로만 받아들이면 된다. 따라서 )연산자의 등장 결과는 다음과 같다.
| / | 4 |
| 1 | 2 | 3 | * | + |
쟁반 :
지금 설명한 ) 연산자의 의미도 프로그램을 작성할 때 고려해야 할 사항 중 하나이므로 다음과 같이 정리하자.
"소괄호의 끝을 의미하는 ) 연산자가 담고있는 메세지는 , (이후에 쌓인 연산자들을 변환된 수식의 자리로 옮기라는 것이다. 때문에 ) 연산자는 변환된 수식의 자리로 옮기지 않아도 된다. 메세지만 취하고 버리면 된다"
이제 남은 것은 / 연산자와 숫자 4의 처리이다. 일단 / 연산자가 쟁반으로 이동하고 나서 숫자 4가 변환된 수식이 위치할 자리로 이동하고, 마지막으로 / 연산자가 수식의 마지막을 채운다. 따라서 최종 겨과는 다음과 같다.
| 1 | 2 | 3 | * | + | 4 | / |
이로써 소괄호를 포함하는 중위 표기법의 수식을 후위표기법의 수식으로 변환하는 방법을 모두 설명하였다.
중위 표기법을 후위 표기법으로 바꾸는 프로그램의 구현
이제 남은 것은 지금까지 설명한 내용을 프로그램 코드로 옮기는 일이다. 그런데 앞서 언급한 쟁반은 스택을 의미하니, 변환 프로그램을 구현하기 위해서 스택을 활용해야 한다.
void ConvToRPNExp(char exp[]) //후위 표기법의 수식으로 변환
{
...
}
따라서 함수 ConvToRPNExp는 다음의 형태로 호출이 이뤄져야 한다.
int main()
{
char exp[] = "3-2+4"; //중위 표기법의 수식
ConvToRPNExp(exp); //후위 표기법의 수식으로 변환을 요청
}
int GetOpPrec(char op) //연산자의 연산 우선 순위 정보를 반환한다.
{
switch(op)
{
case '*':
case '/':
return 5; //가장 높은 연산의 우선순위
case '+':
case '-':
return 3; //5보다 작고 1보다 높은 연산 우선순위
case '(':
return 1; //가장 낮은 연산의 우선순위
}
return -1; //등록되지 않은 연산자임을 알림
}
위의 함수는 인자로 전달된 연산자의 우선순위 정보를 정수의 형태로 반환하는 함수이다. 반환 값이 클수록 우선순위가 높음을 의미한다. 물론 반환 값 5, 3, 1 은 우리가 임의로 정한것이다. 이 값이 아니더라도 곱셈과 나눗셈 연산자의 반환 값이 덧셈과 뺄셈의 연산자의 반환 값보다 크면 된다.
함수를 하나 더 정의하겠다. 이 함수는 지금 막 소개한 GetOpPrec 함수의 호출 결과를 바탕으로 두 연산자의 우선순위를 비교하여, 그 결과를 반환하는 함수이다.
int WhoPrecOp(char op1, char op2)
{
int op1Prec= GetOpPrec(op1);
int op2Prec= GetOpPrec(op2);
if(op1Prec > op2Prec) // op1의 우선순위가 더 높다면
return 1;
else if(op1Prec<op2Prec) //op2의 우선순위가 더 높다면
return -1;
else
return 0; //op1과 op2의 우선순위가 같다면
}
주석에서 언급하듯이, 이는 첫번째 인자로 전달된 연산자의 우선순위가 높으면 1을 , 두번째 인자로 전달된 연산자의 우선순위가 높으면 -1을, 그리고 두 연산자의 우선순위가 같으면 0을반환하는 함수이다.
그럼 이제 후위 표기법으로의 변환을 담당하는 ConvToRPNExp 함수를 보이겠다.
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]; // exp로 전달된 수식을 한 문자씩 tok에 저장
if(isdigit(tok)) //tok에 저장된 문자가 숫자인지 확인
{
convExp[idx++] = tok; //숫자이면 배열 convExp에 그냥 저장
}
else //숫자가 아니라면(연산자라면)
{
switch(tok)
{
case '(' : //여는 소괄호라면
SPush(&stack, tok); // 스택에 쌓는다.
break;
case ')' : //닫는 소괄호라면
while(1) //반복해서
{
popOp = SPop(&stack); //스택에서 연산자를 꺼내어,
if(popOp == '(') //연산자 (을 만날 때 까지,
break;
convExp[idx++] = popOp; //배열 convExp에 저장한다.
}
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); //배열 convExp로 이동한다.
strcpy(exp, convExp); //변환된 수식을 exp에 복사하고,
free(convExp); //convExp는 소멸시킨다.
}
위의 함수에서 사칙 연산자가 switch 문으로 전달되었을 때 실행되는 다음 반복문에 대해서는 주석으로 설명하지 않았으니 이에 대한 설명을 이어서 진행한다.
while(!SIsEmpty(&stack)&& WhoPrecOp(SPeek(&stack), tok) >= 0)
convExp[idx++]= SPop(&stack);
SPush(&stack, tok);
이는 연산자가 변수 tok에 저장되었을 때, 이를 스택으로 옮기거나 배열 convExp에 바로 옮기기 위한 문장이다. 그래서
다음 함수 호출을 통해서우선 스택에 연산자가 존재하는지 확인을 하고,
SIsEmpty(&stack)
연산자가 존재한다면 SPeek 함수를 호출해서 , 그 연산자를 지우지 않고 잠시 꺼낸다. 그리고 다음 함수 호출을 통해서 두 연산자의 우선순위를 비교한다.
WhoPrecOp(SPeek(&stack), tok)
그 결과 스택에 저장된 연산자가 먼저 연산이 되어야 하는 경우, 다음 문장을 통해서 스택에서 연산자를 꺼내어 배열에 저장한다.
convExp[idx++] = SPop(&stack);
이 과정은 먼저 연산되어야 하는 연산자가 스택에 있는 동안 계속 진행되어야 한다. 따라서 while문으로 구성하였으며, while문을 빠져나갔다는 것은 변수 tok에 저장된 연산자가 들어갈 스택의 위치를 찾았다는 뜻이므로, 다음 문장을 통해서 tok에 저장된 연산자를 스택에 저장한다.
SPush(&stack, tok);
이로써 함수 ConvToRPNExp 에 대한 설명이 끝이 났다.
<ctype.h>
void *memset(void *ptr, int val, size_t len);
->ptr로 전달된 주소의 메모리서부터 len 바이트를 val값으로 채운다
<string.h>
int isdigit(int ch);
->ch로 전달된 문자의 내용이 10진수라면 1을 반환한다.
중위 표기법을 후위 표기법으로 바꾸는 프로그램의 실행
이제 ConvToRPNExp 함수의 동작 결과를 확인할 차례이다.
스택을 필요로 하기 때문에, 앞서 구현한 헤더파일과 소스파일이 필요하다.
LishBaseStack.h
ListBaseStack.c
따라서 main 함수가 담기는 소스파일을 포함하여 총 5개의 파일을 하나의 프로젝트로 묶어서 컴파일 해야 한다.
//InfixToPostfix.h
#ifndef __INFIX_TO_POSTFIX_H__
#define __INFIX_TO_POSTFIX_H__
void ConvToRPNExp(char exp[]);
#endif//InfixToPostFix.c
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#include "ListBaseStack.h"
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);
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);
}//InfixToPostfixMain.c
#include <stdio.h>
#include "InfixToPostfix.h"
int main()
{
char exp1[] = "1+2*3";
char exp2[] = "(1+2)*3";
char exp3[] = "((1-2)+3)*(5-2)";
ConvToRPNExp(exp1);
ConvToRPNExp(exp2);
ConvToRPNExp(exp3);
printf("%s \n", exp1);
printf("%s \n", exp2);
printf("%s \n", exp3);
return 0;
================================실행 결과============================
123*+
12+3*
12-3+52-*후위 표기법으로 표현된 수식의 계산 방법
이제 남은 일은 변환된 후위 표기법의 수식을 계산하여 그 결과를 얻는 것이다. 따라서 아직까지 설명하지 않은, 후위 표기법의 수식을 계산하는 방법을 설명하고자 한다. 먼저 다음 수식을 보자.
3+ 2 *4
이를 후위표기법 수식으로 바꾸면 다음과 같다.
324*+
그럼 위 수식의 계산 방법을 보이도록 하겠다. 앞서 몇번 언급했듯이, 후위 표기법에서는 먼저 연산되어야 하는 연산자가 수식의 앞쪽에 배치된다. 때문에 위의 수식은 곱셈이 우선 진행되고 이어서 덧셈이 진행된다.
그렇다면 우선 진행이 되는 곱셉 연산자의 피연산자는 무엇일까? 후위 표기법에서는 다음의 기준을 근거로 피연산자를 선택하게 된다.
"후위 표기법의 수식에서는 연산자의 앞에 등장하는 두개의 숫자가 피연산자 입니다."
즉 위의 식에서는 곱셈이 먼저 진행되는데, 곱셈의 두 피연산자는 아래에서 보이듯이 2와 4이다.
324*+
그리고 연산의 결과는 그 자리를 대신하게 된다. 즉 위의 식은 곱셉 이후에 다음과 같이 정리가 된다.
38+
이제 남은것은 덧셈이다. 물론 덧셈도 앞의 두 피연사자를 대상으로 진행이된다. 따라서 최종 결과로 11을 얻게 된다.
(1 * 2 + 3) / 4
이수식을 후위표기법으로 바꾸면 다음과 같다.
12*3+4/
위의 후위 표기법의 수식에서 제일 앞쪽에 *연산자가 위치하니, 1과 2의 곱셈을 먼저 진행한다. 따라서 그 결과는 다음과 같다.
23+4/
이어서 +연산을 진행한다.
54/
마지막으로 5를 4로 나누는 연산을 진행한다. 그리고 그 결과가 최종 결과가 된다.
1
후위 표기법으로 표현된 수식을 계산하는 프로그램의 구현
후위 표기법의 계산 방법을 이해했다 하더라도 이를 프로그램으로 옮기기 위해서는 그 방법을 별도로 고민해야 한다. 그런데 앞서 보인 계산 방법은 스택을 이용하면 매우 쉽게 프로그램으로 옮길 수 있다. 프로그램으로 옮기기 위한 기본 원칙 세 가지는 다음과 같으며, 이는 수식을 구헝하는 문자의 처리 기준이 된다.
-피연산자는 무조건 스택으로 옮긴다.
-연산자를 만나면 스택에서 두개의 피 연산자를 꺼내서 계산을 한다.
-계산 결과는 다시 스택에 넣는다.
앞서 우리가 경험한 후위 표기법으로의 변경 방법에 비하면 매우 간단하다. 그럼 다음 식을 대상으로 위의 규칙을 적용해보자.
324*+
우선 3과 2와 4 가 모두 피연산자이니 , 다음과 같이 이들 모두가 차례로 스택에 쌓여야 한다.
스택 : 3 2 4
이어서 *연산자를 처리할 차례이다. 따라서 스택으로 부터 두개의 피 연산자를 꺼내어 연산을 진행한다.
그런데 여기서 주목할 것은 4와 2를 꺼내어 진행이 되는 연산은 다음과 같다는 사실이다.
2 * 4
즉 4 *2 가 아니라 2 * 4 이다. 물론 곱셈에서는 상관없는 이야기지만 뺄셈이나 나눗셈이라면 이야기는 달라진다. 즉 스택에서 먼저 꺼낸 피연산자가 두 번째 피연산자가 되고 ( 오른쪽 피연산자가 되고) , 나중에 꺼낸 피연산자가 첫 번째 피연산자가 된다(왼쪽 피연산자가 된다) . 따라서 연산이 이뤄지고 그 결과로 얻어진 값 8이 다시 스택으로 들어가서 다음의 상황이 된다.
스택 : 3 8
후위표기법은 +만 남음
이제 마지막 남은 덧셈연산을 위해 스택으로부터 두 개의 피연산자를 모두 꺼내어 덧셈이 진행되고 그 결과로 11을 얻게된다. 그럼 지금까지 설명한 내용을 바탕으로 다음 함수를 완성하자.
int EvalRPNExp(char exp[]) //후위 표기법의 수식을 계산하여 그 결과를 반환
{
...
}
위 함수는 후위 표기법의 수식을 담고 있는 문자열의 주소 값을 인자로 전달 받는다. 그리고 그 수식의 계산결과를 반환한다.
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]; //한 문자씩 tok에 저장하고,
if(isdigit(tok)) //문자의 내용이 정수인지 확인한다.
{
SPush(&stack, tok-'0'); //정수면 숫자로 변환 후 스택에 PUSH
}
else //정수가 아닌 연산자라면
{
op2 = SPop(&stack); //스택에서 두번째 연산자를 꺼낸다.
op1 = SPop(&stack); //스택에서 첫 번째 연산자를 꺼낸다.
switch(tok) //연산하고 그 결과를 다시 스택에 PUSH
{
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); //마지막 연산 결과를 스택에서 꺼내어 반환
}
이 함수 역시 조금 복잡해 보이지만, 앞서 언급한 후위 표기법의 수식을 계산하는 세 가지 원리를 그대로 반영한 것이 전부이니, 이를 참조하여 코드를 분석하기 바란다.
후위 표기법으로 표현된 수식을 계산하는 프로그램의 실행
위에서 정의한 EvalRPNExp 함수의 실행 결과를 확인할 차례이다.
PostCalculator.h EvalRPNExp 함수의 선언
postCalculator.c EvalRPNExp 함수의 정의
그리고 위의 함수도 스택을 필요로 하기 때문에, 다음 헤더파일과 소스 파일도 함께 컴파일 해야한다.
ListBaseStack.h
ListBaseStack.c
//PostCalculator.h
#ifndef __POST_CALCULATOR_H__
#define __POST_CALCULATOR_H__
int EvalRPNExp(char exp[]);
#endif//PostCalculator.c
#include <string.h>
#include <ctype.h>
#include "ListBaseStack.h"
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- '0');
}
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);
}//PostCalculatorMain.c
#include <stdio.h>
#include "PostCalculator.h"
int main()
{
char postExp1[] = "42*8+";
char postExp2[] = "123+*4/";
printf("%s = %d \n", postExp1, EvalRPNExp(postExp1));
printf("%s = %d \n", postExp2, EvalRPNExp(postExp2));
return 0;
}
================================실행결과========================
42*8+ = 16
123+*4/ = 1이제 하나로 몪는 일만 남았다
중위 표기법의 수식을 후위 표기법의 수식으로 변환하는 함수도 정의하였고, 후위 표기법의 수식을 계산하는 함수도 정의하였으니, 프로그램 사용자로부터 소괄호를 포함하는 중위 표기법의 수식을 입력 받아서, 그 결과를 계산하여 출력하는 것이 가능해졌다. 따라서 마지막으로 다음 프로그램을 작성하자
"프로그램 사용자로부터 소괄호가 포함된 중위 표기법의 수식을 입력 받아서 그 연산결과를 출력해준다"
물론 이를 위해서 앞서 정의한 다음 두 함수를 활용해야 한다.
ConvToRPNExp 함수 : 중위 표기법의 수식을 후위 표기법의 수식으로 변환
EvalRPNExp 함수 : 후위 표기법의 수식을 계산하여 그 결과를 반환
활용의 방법은 다음과 같다. 프로그램 사용자로부터 입력 받은 중위 표기법의 수식은 다음의 과정을 거쳐서 연산의 결과를 얻어야 한다.
중위 표기법 수식 -> ConvToRPNExp ->EvalRPNExp ->연산결과
우리는 위의 과정을 하나의 함수에 담을 것이다.
//InfixCalculator.h
#ifndef __INFIX_CALCULATOR__
#define __INFIX_CALCULATOR__
int EvalInfixExp(char exp[]);
#endif//InfixCalculator.c
#include <string.h>
#include <stdlib.h>
#include "InfixToPostfix.h" //ConvTpRPNExp 함수의 호출을 위해서
#include "PostCalculator.h" //EvalRPNExp 함수의 호출을 위해서
int EvalInfixExp(char exp[])
{
int len = strlen(exp);
int ret;
char *expcpy = (char *)malloc(len+1); //문자열 저장공간 마련
strcpy(expcpy, exp); //exp를 expcpy에 복사
ConToRPNExp(expcpy); //후위 표기법의 수식으로 변환
ret = EvalRPNExp(expcpy); //변환된 수식의 계산
free (expcpy); //문자열 저장공간 해제
return ret; //계산결과 반환
}//InfixCalculatorMain.c
#include <stdio.h>
#include "InfixCalculator.h"
int main()
{
char exp1[] = "1+2*3";
char exp2[] = "(1+2)*3";
char exp3[] = "((1-2)+3)*(5-2)";
printf("%s = %d \n", exp1, EvalInfixExp(exp1));
printf("%s = %d \n", exp2, EvalInfixExp(exp2));
printf("%s = %d \n", exp3, EvalInfixExp(exp3));
return 0;
}
======================================실행결과==========================
1+2*3 = 7
(1+2)*3 =9
((1-2)+3)*(5-2) = 6비로소 소괄호를 포함하는 중위 표기법의 수식을 계산할 수 있게 되었다. 마지막으로 필요한 헤더파일과 소스파일을 정리해보자.
스택의 활용 : ListBaseStack.h , ListBaseStack.c
후위 표기법의 수식으로 변환 : InfixToPostfix.h , InfixToPostfix.c
후위 표기법의 수식을 계산 : PostCalculator.h , PostCalculator.c
중위 표기법의 수식을 계산 : InfixCalculator.h , InfixCalculator.c
main 함수 : InfixCalculatorMain.c
'휴지통 > 자료구조-C' 카테고리의 다른 글
| 큐(Queue)의 연결리스트 기반 구현 (0) | 2021.02.28 |
|---|---|
| 큐(Queue) (0) | 2021.02.27 |
| 스택 (0) | 2021.02.23 |
| 양방향 연결 리스트 (0) | 2021.02.16 |
| 원형 연결 리스트 (0) | 2021.02.15 |
