[ch 06-4] 계산기 프로그램 구현_4(후위표기법 수식 계산 구현)

[소스 코딩]

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

■ 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;
}

---

■ 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);
}

■ 사용되는 함수 설명

Stack stack;
int expLen = strlen(exp);
int i;
char tok, op1, op2;
 
StackInit(&stack);

- Stack 구조체 'stack' 선언

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

- 변수 i 선언

  ※ i: 후위표기법으로 저장된 배열의 인덱스 순서

- 변수 tok, op1, op2 선언

  ※ tok: 후위표기법으로 저장된 배열의 수식을 한 문자씩 임시로 저장하기 위함

  ※ op1: 계산 시 왼쪽에 배치될 피연산자를 저장할 공간

  ※ op2: 계산 시 오른쪽에 배치될 피연산자를 저장할 공간

- 스택 생성 및 초기화

for(i=0; i<expLen; i++)
{
    tok = exp[i];

--- 후위표기법 계산 반복문 시작 ---

- 'tok'에 exp 배열 i번째 값을 저장

if(isdigit(tok))
{
    SPush(&stack, tok - '0');
}

// tok에 저장된 값이 '숫자'일 경우

  ※ isdigit 함수: 인자 값이 숫자이면 0이 아닌 값을 반환

- 문자형 '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;
    }
}

// tok에 저장된 값이 '문자'일 경우

- 'op2'에 스택에서 꺼낸 피연산자를 저장

  ※ 먼저 꺼낸 피연산자는 계산 시 연산자 오른쪽에 배치되기 때문에 op2에 저장

- 'op1'에 스택에서 꺼낸 피연산자를 저장

- tok의 종류에 따라 다르게 처리

// '+'일 경우

- 'op1 + op2' 계산 처리 후 결과 값을 스택에 저장 후 switch 종료

// '-'일 경우

- 'op1 - op2' 계산 처리 후 결과 값을 스택에 저장 후 switch 종료

// '*'일 경우

- 'op1 * op2' 계산 처리 후 결과 값을 스택에 저장 후 switch 종료

// '/'일 경우

- 'op1 / op2' 계산 처리 후 결과 값을 스택에 저장 후 switch 종료

--- 후위표기법 계산 반복문 종료 ---

return SPop(&stack);

- (변환된 수식에 더 이상 처리할 데이터가 없으면) 스택에 저장된 데이터(계산 결과 값)를 꺼내어 반환

■ PostCalculatorMain.c

#include <stdio.h>
#include "PostCalculator.h"
 
int main(void)
{
    char postExp1[] = "563/-";
    char postExp2[] = "315+*2/";
 
    printf("'%s' → %d \n", postExp1, EvalRPNExp(postExp1));
    printf("'%s' → %d \n", postExp2, EvalRPNExp(postExp2));
 
    return 0;
}

※ 후위표기법으로 작성된 수식을 배열에 저장

- 문자형 배열 'postExp1'에 '563/-' 수식을 저장

- 문자형 배열 'postExp2'에 '315+*2/' 수식을 저장

- 각각 계산 처리된 결과 값을 출력

■ 실행결과