[ch 06-4] 계산기 프로그램 구현_5(최종 통합 구현)

[계산기 처리 과정]

- 중위표기법 수식 → ConvToRPNExp 함수(후위표기법으로 변환) → EvalRPNExp 함수(후위표기법 계산) → 연산 결과

[소스 코딩]

※ 스택은 이전에 '연결 리스트 기반으로 구현된 스택' 소스를 활용

※ 후위표기법으로 변환 처리는 이전에 'InfixToPostfix' 소스를 활용

※ 후위표기법 계산 처리는 이전에 'PostCalculator' 소스를 활용

■ ListBaseStack.h

#ifndef __LB_STACK_H__
#define __LB_STACK_H__
 
#define TRUE    1
#define FALSE   0
 
typedef int Data;                        // 사용자 정의 int형 Data 선언
 
typedef struct _node                     // 사용자 정의 구조체 'Node' 정의
{
    Data data;                           // 입력 받은 데이터를 저장할 data 선언
    struct _node * next;                 // 다음 노드를 가리킬 노드 포인터 next 선언
} Node;
 
typedef struct _listStack                // 사용자 정의 구조체 'ListStack' 정의
{
    Node * head;                         // ListStack에 노드 포인터 'head' 선언
} ListStack;
 
 
typedef ListStack Stack;                 // ListStack 이름을 'Stack'으로 변경
 
void StackInit(Stack * pstack);          // 스택을 초기화 하는 함수
int SIsEmpty(Stack * pstack);            // 스택에 데이터가 비어있는지 확인하는 함수
 
void SPush(Stack * pstack, Data data);   // 스택에 데이터를 삽입하는 함수
Data SPop(Stack * pstack);               // 스택에서 데이터를 추출하는 함수
Data SPeek(Stack * pstack);              // 스택의 데이터를 확인하는 함수
 
#endif

■ ListBaseStack.c

#include <stdio.h>
#include <stdlib.h>
#include "ListBaseStack.h"
 
// 스택을 초기화 하는 함수 //
void StackInit(Stack * pstack)
{
    pstack->head = NULL;
}
 
// 스택에 데이터가 비어있는지 확인하는 함수 //
int SIsEmpty(Stack * pstack)
{
    if(pstack->head == NULL)
        return TRUE;
    else
        return FALSE;
}
 
// 스택에 데이터를 삽입하는 함수 //
void SPush(Stack * pstack, Data data)
{
    Node * newNode = (Node*)malloc(sizeof(Node));
 
    newNode->data = data;
    newNode->next = pstack->head;
 
    pstack->head = newNode;
}
 
// 스택에서 데이터를 추출하는 함수 //
Data SPop(Stack * pstack)
{
    Data rdata;
    Node * rnode;
 
    if(SIsEmpty(pstack)) {
        printf("Stack Memory Error!");
        exit(-1);
    }
 
    rdata = pstack->head->data;
    rnode = pstack->head;
 
    pstack->head = pstack->head->next;
    free(rnode);
 
    return rdata;
}
 
// 스택의 데이터를 확인하는 함수 //
Data SPeek(Stack * pstack)
{
    if(SIsEmpty(pstack)) {
        printf("Stack Memory Error!");
        exit(-1);
    }
 
    return pstack->head->data;
}

■ InfixToPostfix.h

#ifndef __INFIX_TO_POSTFIX_H__
#define __INFIX_TO_POSTFIX_H__
 
// 사용자에게 입력 받은 중위표기법 수식을 후위표기법 수식으로 변경하는 함수 //
void ConvToRPNExp(char exp[]);
 
#endif

■ InfixToPostfix.c

#include <string.h>           // malloc, strlen, strcpy 함수를 사용하기 위함
#include <stdlib.h>           // malloc, memset 함수를 사용하기 위함
#include <ctype.h>            // isdigit 함수를 사용하기 위함
#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);
}

■ PostCalculator.h

#ifndef POSTCALCULATOR_H_
#define POSTCALCULATOR_H_
 
// 후위표기법 수식을 계산하는 함수 //
int EvalRPNExp(char exp[]);
 
#endif

■ PostCalculator.c

#include <string.h>       // strlen 함수를 사용하기 위함
#include <ctype.h>        // isdigit 함수를 사용하기 위함
#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);
}

---

■ InfixCalculator.h

#ifndef INFIXCALCULATOR_H_
#define INFIXCALCULATOR_H_
 
// '중위표기법→후위표기법 변환→연산'처리하는 함수 //
int EvalInfixExp(char exp[]);
 
#endif

■ InfixCalculator.c

#include <string.h>                // strlen, strcpy 함수를 사용하기 위함
#include <stdlib.h>                // malloc 함수를 사용하기 위함
#include "InfixToPostfix.h"
#include "PostCalculator.h"
 
// '중위표기법→후위표기법 변환→연산'처리하는 함수 //
int EvalInfixExp(char exp[])
{
    int len = strlen(exp);
    int ret;
    char * expcpy = (char*)malloc(len+1);
    strcpy(expcpy, exp);
 
    ConvToRPNExp(expcpy);
    ret = EvalRPNExp(expcpy);
 
    free(expcpy);
    return ret;
}

■ 사용되는 함수 설명

int len = strlen(exp);
int ret;
char * expcpy = (char*)malloc(len+1);
strcpy(expcpy, exp);

- 'len'에 'exp 배열 인자의 길이'만큼 저장

- 변수 ret 선언

  ※ 최종 결과 값을 저장할 공간

- 문자형 포인터 변수 'expcpy'에 'len+1 길이'만큼 메모리 공간 생성(동적 메모리 할당)

  ※ 변환된 수식을 담을 공간. 호출된 exp 값을 건드리지 않게 임시 공간을 사용

- exp에 저장된 값을 expcpy에 복사

  ※ strcpy 함수: 오른쪽 인자에 저장된 값을 왼쪽 인자에 복사

ConvToRPNExp(expcpy);
ret = EvalRPNExp(expcpy);
 
free(expcpy);
return ret;

- 'expcpy'에 저장된 중위표기법 수식을 후위표기법으로 변환

- 'ret'에 'expcpy'수식의 계산된 결과를 저장

- 'expcpy' 메모리 공간 제거

- 'ret'에 저장된 값을 반환

■ InfixCalculatorMain.c

#include <stdio.h>
#include "InfixCalculator.h"
 
int main(void)
{
    char exp1[] = "8-6/3*2";
    char exp2[] = "(2+6)/2+1";
    char exp3[] = "((5+4)/3)*(3-1)";
 
    printf("%s = %d \n", exp1, EvalInfixExp(exp1));
    printf("%s = %d \n", exp2, EvalInfixExp(exp2));
    printf("%s = %d \n", exp3, EvalInfixExp(exp3));
 
    return 0;
}

- 문자형 배열 'exp1'에 '8-6/3*2' 수식을 저장

- 문자형 배열 'exp2'에 '(2+6)/2+1' 수식을 저장

- 문자형 배열 'exp3'에 '((5+4)/3)*(3-1)' 수식을 저장

- 배열 'exp1, exp2, exp3'을 후위표기법 수식으로 변환, 계산, 출력

■ 실행결과