[ch 06-4] 계산기 프로그램 구현_2(중위표기법->후위표기법 변환 구현)

[소스 코딩]

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

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

■ 사용되는 함수 설명

// 연산자의 우선순위 정보를 반환해주는 함수 //
int GetOpPrec(char op)
{
    switch(op)
    {
        case '*':
        case '/':
            return 5;
 
        case '+':
        case '-':
            return 3;
 
        case '(':
            return 1;
    }
 
    return -1;
}

- 호출 받은 연산자(op)의 종류에 따라 다른 우선순위를 반환

// 연산자가 '*' 또는 '/'일 경우

- 가장 높은 우선순위인 '5'를 반환

// 연산자가 '+' 또는 '-'일 경우

- 다음 우선순위인 '3'을 반환

// 연산자가 '('일 경우

- 가장 낮은 우선순위인 '1'을 반환

// 위에 아무것도 해당되지 않으면

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

- 'op1Prec'에 op1 연산자의 우선순위 값을 저장

- 'op2Prec'에 op2 연산자의 우선순위 값을 저장

// op1의 우선순위가 더 높을 경우

- '1'을 반환

// op2의 우선순위가 더 높을 경우

- '-1'을 반환

// 둘 다 아닐 경우(op1 == op2)

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

Stack stack;

int expLen = strlen(exp);

char * convExp = (char*)malloc(expLen+1);

- Stack 구조체 'stack' 선언

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

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

  ※ 변환된 수식을 담을 공간

int i, idx = 0;

char tok, popOp;

- 변수 i, idx 선언

  ※ i: 사용자 입력으로 저장된 배열(중위표기법)의 인덱스를 증가시키기 위함

  ※ idx: 변환된 배열의 인덱스를 증가시키기 위함

- 변수 tok, popOp 선언

  ※ tok: 사용자 입력으로 저장된 배열(중위표기법)의 수식을 한 문자씩 임시로 저장하기 위함

  ※ popOp: stack에서 꺼내진 연산자를 임시로 저장하기 위함

memset(convExp, 0, sizeof(char) * expLen+1);

StackInit(&stack);

- 'convExp' 배열의 'sizeof(char) * expLen+1' 길이만큼 '0'으로 초기화

  ※ memset 함수: malloc() 이나 calloc() 에서 할당 받은 메모리를 특정 값으로 특정 크기(길이)만큼 초기화

- 스택 생성 및 초기화

for(i=0; i<expLen; i++)

tok = exp[i];

--- 중위표기법→후위표기법 변환 반복문 시작 ---

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

if(isdigit(tok))

convExp[idx++] = tok;

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

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

- tok에 저장된 값을 배열 'convExp'에 저장

  ※ idx는 처리 후 '1' 증가

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

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

- 종류에 따라 다르게 처리

// '('일 경우

- 스택에 저장 후 switch 종료

// ')'일 경우 아래를 반복

- 스택에서 추출하여 'popOp'에 저장

- 'popOp'에 저장된 값이 '('일 경우 반복 종료 후 switch 종료

- 아닐 경우 popOp에 저장된 값을 'convExp' 배열에 저장

  ※ idx는 처리 후 '1' 증가

// '+' 또는 '-' 또는 '*' 또는 '/'일 경우 아래 조건을 만족 시 반복

   ※ 스택에 데이터가 존재하고, 스택에서 꺼낸 연산자와 우선순위를 비교하여 반환된 값이 '0 이상'일 경우

- 스택에서 연산자를 추출하여 'convExp' 배열에 저장

  ※ idx는 처리 후 '1' 증가

// 반복 조건에 해당되지 않을 경우

- 연산자를 스택에 저장 후 switch 종료

--- 중위표기법→후위표기법 변환 반복문 종료 ---

while(!SIsEmpty(&stack))
    convExp[idx++] = SPop(&stack);
 
strcpy(exp, convExp);
free(convExp);

// 스택에 데이터가 존재할 경우 반복

- 스택에서 연산자를 꺼내어 'convExp' 배열에 저장

  ※ idx는 처리 후 '1' 증가

// 스택에 데이터가 존재하지 않을 경우

- 'convExp' 배열에 저장된 값을 'exp' 배열에 저장 (= 변경된 수식을 사용자 입력으로 저장된 공간에 다시 저장)

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

- 'convExp' 메모리 공간 제거

■ InfixToPostfixMain.c

#include <stdio.h>
#include "InfixToPostfix.h"
 
int main(void)
{
    char exp1[] = "6+7*3";
    char exp2[] = "(5+2)*9";
    char exp3[] = "((1-2)+5)*(7-5)";
 
    ConvToRPNExp(exp1);
    ConvToRPNExp(exp2);
    ConvToRPNExp(exp3);
 
    printf("6+7*3 = %s \n", exp1);
    printf("(5+2)*9 = %s \n", exp2);
    printf("((1-2)+5)*(7-5) = %s \n", exp3);
 
    return 0;
}

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

- 문자형 배열 'exp1'에 '6+7*3' 수식을 저장

- 문자형 배열 'exp2'에 '(5+2)*9' 수식을 저장

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

- 배열 exp1, exp2, exp3을 후위표기법 수식으로 변환

- 각각 변경된 수식을 출력

■ 실행결과