C 언어로 스택 기반 계산기 구현하기: 기초부터 실습까지

스택을 활용한 계산기는 컴퓨터 과학에서 핵심 개념을 이해하는 데 유용한 실습 과제입니다. 본 기사에서는 스택의 기초적인 작동 원리부터 C 언어를 사용한 계산기의 단계별 구현 과정을 자세히 설명합니다. 이를 통해 스택의 실질적인 응용과 함께 프로그래밍 능력을 강화할 수 있습니다.

스택과 계산기의 기본 개념

스택은 LIFO(Last In, First Out) 방식으로 작동하는 데이터 구조로, 가장 나중에 삽입된 요소가 가장 먼저 제거됩니다. 계산기에서는 이러한 스택의 특성을 이용해 복잡한 수식을 처리하거나 연산자의 우선순위를 관리합니다.

스택의 특징

스택은 다음과 같은 두 가지 주요 연산을 지원합니다.

푸시(Push): 스택에 데이터를 추가하는 연산.
팝(Pop): 스택에서 데이터를 제거하는 연산.

계산기에서 스택의 응용

스택은 주로 다음과 같은 방식으로 계산기에 사용됩니다.

후위 표기법 계산: 수식을 후위 표기법으로 변환한 후, 이를 계산하기 위해 사용.
연산자 관리: 중위 표기법에서 연산자 우선순위를 처리하기 위해 사용.

스택의 이러한 특성을 이해하면 계산기의 작동 원리를 보다 명확히 파악할 수 있습니다.

C 언어에서 스택 구조 정의하기

C 언어에서 스택을 구현하기 위해 적절한 데이터 구조를 설계하는 것이 첫 번째 단계입니다. 주로 배열 또는 연결 리스트를 사용하여 스택을 구현합니다. 여기서는 배열을 기반으로 한 스택 구조를 정의합니다.

스택 구조체 정의

스택의 기본 구조체는 다음과 같은 요소를 포함합니다.

배열: 스택 데이터를 저장할 공간.
정수형 변수(top): 현재 스택의 가장 상단 요소의 인덱스를 추적.
정수형 변수(capacity): 스택의 최대 크기.

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int *array;    // 스택 데이터를 저장하는 배열
    int top;       // 스택의 상단 인덱스
    int capacity;  // 스택의 최대 크기
} Stack;

스택 생성 함수

스택을 초기화하는 함수를 작성합니다.

Stack* createStack(int capacity) {
    Stack* stack = (Stack*)malloc(sizeof(Stack));
    stack->capacity = capacity;
    stack->top = -1;  // 초기 상태에서는 스택이 비어 있음
    stack->array = (int*)malloc(capacity * sizeof(int));
    return stack;
}

스택의 유용성

이 구조를 통해 우리는 데이터를 효율적으로 푸시(Push)하고 팝(Pop)할 수 있으며, 계산기 구현 시 스택의 동작을 쉽게 관리할 수 있습니다. 다음 단계에서는 스택 연산 구현을 다룹니다.

스택 연산 구현: 푸시와 팝

스택의 기본 연산인 푸시(Push)와 팝(Pop)은 데이터를 삽입하고 제거하는 기능을 제공합니다. 이 두 연산을 통해 계산기 프로그램에서 스택을 효율적으로 활용할 수 있습니다.

푸시(Push) 연산

푸시는 스택에 새로운 데이터를 추가하는 연산입니다. 배열 기반 스택에서, 푸시 연산은 스택이 가득 차지 않았는지 확인한 후 데이터를 삽입합니다.

void push(Stack* stack, int value) {
    if (stack->top == stack->capacity - 1) {
        printf("스택 오버플로우! 데이터를 푸시할 수 없습니다.\n");
        return;
    }
    stack->array[++stack->top] = value;  // top을 증가시키고 데이터를 삽입
}

팝(Pop) 연산

팝은 스택의 상단에서 데이터를 제거하고 반환하는 연산입니다. 스택이 비어 있는 경우, 팝 연산은 실패 메시지를 출력합니다.

int pop(Stack* stack) {
    if (stack->top == -1) {
        printf("스택 언더플로우! 데이터를 팝할 수 없습니다.\n");
        return -1;  // 오류 값을 반환
    }
    return stack->array[stack->top--];  // 데이터를 반환하고 top을 감소
}

도움이 되는 보조 함수

스택의 현재 상태 확인

   int isEmpty(Stack* stack) {
       return stack->top == -1;
   }

   int isFull(Stack* stack) {
       return stack->top == stack->capacity - 1;
   }

스택 상단 값 확인

   int peek(Stack* stack) {
       if (stack->top == -1) {
           printf("스택이 비어 있습니다.\n");
           return -1;  // 오류 값을 반환
       }
       return stack->array[stack->top];
   }

구현 테스트

아래는 스택 연산을 간단히 테스트하는 코드입니다.

int main() {
    Stack* stack = createStack(5);
    push(stack, 10);
    push(stack, 20);
    printf("스택 상단 값: %d\n", peek(stack));  // 출력: 20
    printf("팝: %d\n", pop(stack));             // 출력: 20
    printf("스택 상단 값: %d\n", peek(stack));  // 출력: 10
    return 0;
}

요약

푸시와 팝 연산은 스택의 기본 동작으로, 계산기 프로그램에서 수식 처리 및 연산자 관리에 중요한 역할을 합니다. 다음 단계에서는 후위 표기법(Postfix Notation)의 개념과 변환 방법을 다룹니다.

후위 표기법(Postfix Notation) 개념 이해

후위 표기법은 연산자를 피연산자 뒤에 배치하는 수식 표기법으로, 컴퓨터가 연산을 수행하기에 적합한 방식입니다. 이 표기법은 스택을 활용한 계산에 주로 사용되며, 괄호 없이도 연산의 우선순위를 명확히 표현할 수 있습니다.

후위 표기법의 특징

연산자 배치

중위 표기법: (A + B) * C
후위 표기법: A B + C *

우선순위
후위 표기법은 괄호가 필요 없으며, 연산 순서는 연산자 위치에 따라 자동으로 결정됩니다.
스택 기반 계산
후위 표기법은 스택을 사용해 간단하게 계산을 수행할 수 있습니다.

후위 표기법의 장점

간결함: 괄호가 없어 수식이 더 단순하게 표현됩니다.
연산 효율성: 중위 표기법보다 컴퓨터가 연산 순서를 더 쉽게 결정할 수 있습니다.
스택 활용: 스택 구조를 사용해 연산을 처리하기 용이합니다.

후위 표기법 변환의 필요성

중위 표기법은 사람이 이해하기 쉬운 반면, 컴퓨터는 이를 직접 계산하기 어렵습니다. 따라서, 연산자 우선순위를 반영해 중위 표기법을 후위 표기법으로 변환해야 합니다.

후위 표기법 변환 예제

중위 표기법 A + B * C를 후위 표기법으로 변환하는 과정:

연산자 우선순위를 고려.

곱셈(*)이 덧셈(+)보다 우선.

변환 결과: A B C * +

후위 표기법 활용

후위 표기법으로 변환된 수식은 스택을 이용해 순차적으로 연산할 수 있습니다.
예를 들어, A B + C *를 계산하려면:

A와 B를 더한다.
결과에 C를 곱한다.

후위 표기법의 이해는 스택 기반 계산기의 핵심이며, 다음 단계에서는 변환 알고리즘과 코드를 구현합니다.

후위 표기법을 위한 연산자 우선순위

중위 표기법을 후위 표기법으로 변환하려면 연산자 우선순위를 이해하고 이를 스택을 활용해 처리해야 합니다. 올바른 변환은 계산기의 정확한 동작을 보장합니다.

연산자 우선순위 정의

연산자 우선순위는 다음과 같이 정의됩니다:

괄호: 가장 높은 우선순위.

(는 항상 스택에 저장하며, )가 나타날 때까지 스택에서 제거하지 않습니다.

곱셈/나눗셈 (*, /): 덧셈/뺄셈보다 높은 우선순위.
덧셈/뺄셈 (+, -): 가장 낮은 우선순위.

중위 표기법 → 후위 표기법 변환 알고리즘

피연산자: 결과에 바로 추가합니다.
연산자: 스택에 삽입하며, 현재 연산자의 우선순위가 스택 상단 연산자보다 낮거나 같으면, 상단 연산자를 결과로 이동시킵니다.
괄호:

(는 스택에 삽입합니다.
)는 스택에서 (가 나올 때까지 모든 연산자를 결과로 이동시킵니다.

스택 남은 연산자: 입력이 끝난 후, 스택에 남아 있는 연산자를 결과로 이동시킵니다.

변환 알고리즘 예제

중위 표기법 A + B * C를 후위 표기법으로 변환:

피연산자 A는 결과로 추가: A.
+는 스택에 삽입.
피연산자 B는 결과로 추가: A B.
*는 +보다 우선순위가 높으므로 스택에 삽입.
피연산자 C는 결과로 추가: A B C.
스택에 남아 있는 연산자 *, +를 결과로 이동: A B C * +.

C 언어 구현: 연산자 우선순위 함수

int precedence(char operator) {
    switch (operator) {
        case '+':
        case '-':
            return 1;  // 낮은 우선순위
        case '*':
        case '/':
            return 2;  // 높은 우선순위
        case '(':
            return 0;  // 가장 낮음 (스택 관리용)
    }
    return -1;  // 잘못된 연산자
}

변환 알고리즘의 한계

이 알고리즘은 잘못된 입력(예: 괄호 불일치)을 처리하지 않으므로, 예외 처리를 추가해야 합니다.
다항 연산자와 같은 복잡한 수식의 변환은 추가 구현이 필요합니다.

다음 단계

이제 후위 표기법으로 변환된 수식을 계산하는 알고리즘을 구현합니다. 이를 통해 스택과 후위 표기법의 실질적인 응용을 다룹니다.

후위 표기법 계산 알고리즘 구현

후위 표기법으로 변환된 수식을 계산하려면 스택을 사용하여 피연산자를 저장하고 연산자가 나타날 때마다 계산을 수행합니다. 이 방법은 계산기의 핵심 동작 원리로, 효율적이고 간단한 방식으로 연산을 처리할 수 있습니다.

후위 표기법 계산 알고리즘

피연산자: 스택에 푸시.
연산자:

스택에서 두 개의 피연산자를 팝.
연산을 수행한 결과를 다시 스택에 푸시.

수식의 끝: 스택에 남아 있는 값이 최종 결과.

후위 표기법 계산 예제

수식: 5 3 + 8 *

5 푸시 → 스택: [5]
3 푸시 → 스택: [5, 3]
+ 연산: 5 + 3 = 8 → 결과 푸시 → 스택: [8]
8 푸시 → 스택: [8, 8]
* 연산: 8 * 8 = 64 → 결과 푸시 → 스택: [64]
결과: 64

C 언어로 구현

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

// 후위 표기법 계산 함수
int evaluatePostfix(const char* expression) {
    Stack* stack = createStack(100);  // 스택 생성
    for (int i = 0; expression[i] != '\0'; i++) {
        char ch = expression[i];

        // 피연산자일 경우 스택에 푸시
        if (isdigit(ch)) {
            push(stack, ch - '0');  // 문자형 숫자를 정수형으로 변환
        } 
        // 연산자일 경우 연산 수행
        else {
            int operand2 = pop(stack);  // 두 번째 피연산자
            int operand1 = pop(stack);  // 첫 번째 피연산자

            switch (ch) {
                case '+': push(stack, operand1 + operand2); break;
                case '-': push(stack, operand1 - operand2); break;
                case '*': push(stack, operand1 * operand2); break;
                case '/': push(stack, operand1 / operand2); break;
            }
        }
    }
    return pop(stack);  // 최종 결과 반환
}

테스트 코드

int main() {
    const char* expression = "53+8*";  // 후위 표기법 수식
    printf("후위 표기법 결과: %d\n", evaluatePostfix(expression));  // 출력: 64
    return 0;
}

알고리즘의 장점

단순성: 연산 우선순위와 괄호를 따로 고려할 필요 없음.
효율성: 한 번의 스캔으로 결과 계산.

한계 및 확장

현재 구현은 한 자릿수 피연산자만 지원하므로, 다자릿수 피연산자와 소수점 연산을 지원하려면 추가 처리가 필요합니다.
입력의 유효성 검사(예: 올바르지 않은 연산자, 빈 스택)는 강화되어야 합니다.

다음 단계에서는 이 알고리즘을 통합해 완전한 스택 기반 계산기를 작성합니다.

C 코드로 완전한 계산기 구현하기

이 단계에서는 앞서 배운 내용을 통합하여 후위 표기법으로 수식을 계산하는 스택 기반 계산기를 작성합니다. 프로그램은 중위 표기법의 입력을 받아 이를 후위 표기법으로 변환한 뒤 계산 결과를 반환합니다.

전체 프로그램 구조

중위 표기법 → 후위 표기법 변환

연산자 우선순위를 반영하여 입력을 변환합니다.

후위 표기법 계산

변환된 후위 표기법을 스택을 이용해 계산합니다.

전체 코드

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>

// 스택 구조체 정의
typedef struct {
    char *array;
    int top;
    int capacity;
} Stack;

// 스택 생성 함수
Stack* createStack(int capacity) {
    Stack* stack = (Stack*)malloc(sizeof(Stack));
    stack->capacity = capacity;
    stack->top = -1;
    stack->array = (char*)malloc(capacity * sizeof(char));
    return stack;
}

// 스택 관련 연산
int isEmpty(Stack* stack) {
    return stack->top == -1;
}

void push(Stack* stack, char value) {
    stack->array[++stack->top] = value;
}

char pop(Stack* stack) {
    return isEmpty(stack) ? '\0' : stack->array[stack->top--];
}

char peek(Stack* stack) {
    return isEmpty(stack) ? '\0' : stack->array[stack->top];
}

// 연산자 우선순위 반환 함수
int precedence(char operator) {
    switch (operator) {
        case '+': case '-': return 1;
        case '*': case '/': return 2;
        case '(': return 0;
    }
    return -1;
}

// 중위 → 후위 변환 함수
void infixToPostfix(const char* expression, char* result) {
    Stack* stack = createStack(strlen(expression));
    int k = 0;

    for (int i = 0; expression[i] != '\0'; i++) {
        char ch = expression[i];

        // 피연산자일 경우 결과에 추가
        if (isdigit(ch)) {
            result[k++] = ch;
        } 
        // '('는 스택에 푸시
        else if (ch == '(') {
            push(stack, ch);
        } 
        // ')'는 '('까지 스택에서 팝
        else if (ch == ')') {
            while (!isEmpty(stack) && peek(stack) != '(') {
                result[k++] = pop(stack);
            }
            pop(stack);  // '(' 제거
        } 
        // 연산자 처리
        else {
            while (!isEmpty(stack) && precedence(peek(stack)) >= precedence(ch)) {
                result[k++] = pop(stack);
            }
            push(stack, ch);
        }
    }

    // 남아 있는 연산자 추가
    while (!isEmpty(stack)) {
        result[k++] = pop(stack);
    }

    result[k] = '\0';
}

// 후위 표기법 계산 함수
int evaluatePostfix(const char* expression) {
    Stack* stack = createStack(strlen(expression));

    for (int i = 0; expression[i] != '\0'; i++) {
        char ch = expression[i];

        // 피연산자일 경우 스택에 푸시
        if (isdigit(ch)) {
            push(stack, ch - '0');
        } 
        // 연산자일 경우 계산 수행
        else {
            int operand2 = pop(stack);
            int operand1 = pop(stack);
            switch (ch) {
                case '+': push(stack, operand1 + operand2); break;
                case '-': push(stack, operand1 - operand2); break;
                case '*': push(stack, operand1 * operand2); break;
                case '/': push(stack, operand1 / operand2); break;
            }
        }
    }
    return pop(stack);
}

// 메인 함수
int main() {
    char infix[100];
    char postfix[100];

    printf("중위 표기법 수식을 입력하세요: ");
    scanf("%s", infix);

    infixToPostfix(infix, postfix);
    printf("후위 표기법: %s\n", postfix);

    int result = evaluatePostfix(postfix);
    printf("계산 결과: %d\n", result);

    return 0;
}

코드 설명

중위 표기법 입력: 사용자로부터 중위 표기법 수식을 입력받습니다.
후위 표기법 변환: infixToPostfix 함수를 통해 수식을 후위 표기법으로 변환합니다.
결과 계산: evaluatePostfix 함수를 사용해 변환된 후위 표기법을 계산합니다.

테스트 예제

입력: (5+3)*2
출력: 후위 표기법: 53+2*
계산 결과: 16

확장 가능성

다자릿수 피연산자 지원.
예외 처리 강화(잘못된 수식 입력 등).
소수점 연산 및 부동소수점 계산 지원.

다음 단계에서는 디버깅과 테스트 사례를 다루어 프로그램의 신뢰성을 검증합니다.

디버깅과 테스트

구현된 계산기의 신뢰성을 보장하기 위해 다양한 테스트 케이스를 실행하고, 발생할 수 있는 오류를 분석하여 수정합니다. 디버깅과 테스트는 안정적이고 정확한 결과를 제공하는 프로그램을 개발하는 데 필수적인 과정입니다.

테스트 케이스 작성

다양한 입력을 고려하여 테스트 케이스를 작성합니다.

기본 수식 테스트

입력: (2+3)*4
후위 표기법: 23+4*
예상 결과: 20

복잡한 괄호 수식

입력: ((1+2)*3)-(4/(2+2))
후위 표기법: 12+3*42+2/-
예상 결과: 8

연산자 우선순위 테스트

입력: 2+3*4-5
후위 표기법: 234*+5-
예상 결과: 9

단일 연산 테스트

입력: 5+0
후위 표기법: 50+
예상 결과: 5

잘못된 입력 처리

입력: 5+*3
예상 결과: 오류 메시지.

테스트 코드 작성

테스트를 자동화하여 다양한 입력을 반복적으로 검증합니다.

void runTests() {
    struct TestCase {
        const char* infix;
        const char* expectedPostfix;
        int expectedResult;
    };

    struct TestCase testCases[] = {
        {"(2+3)*4", "23+4*", 20},
        {"((1+2)*3)-(4/(2+2))", "12+3*42+2/-", 8},
        {"2+3*4-5", "234*+5-", 9},
        {"5+0", "50+", 5},
    };

    for (int i = 0; i < 4; i++) {
        char postfix[100];
        infixToPostfix(testCases[i].infix, postfix);

        int result = evaluatePostfix(postfix);
        printf("테스트 %d:\n", i + 1);
        printf("  중위 표기법: %s\n", testCases[i].infix);
        printf("  예상 후위 표기법: %s, 계산 결과: %d\n", testCases[i].expectedPostfix, testCases[i].expectedResult);
        printf("  실제 후위 표기법: %s, 계산 결과: %d\n", postfix, result);

        if (strcmp(postfix, testCases[i].expectedPostfix) == 0 && result == testCases[i].expectedResult) {
            printf("  테스트 성공!\n");
        } else {
            printf("  테스트 실패!\n");
        }
    }
}

디버깅 전략

입력 검사

유효하지 않은 연산자나 피연산자가 포함된 경우 오류 메시지를 출력합니다.
괄호 불일치 여부 확인.

스택 상태 점검

디버깅 중 각 연산 후 스택의 상태를 출력하여 연산이 올바르게 수행되는지 확인합니다.

로그 추가

각 단계에서 로그를 추가하여 변환 및 계산 과정을 추적합니다.

디버깅 코드 추가

void debugPostfixConversion(const char* infix) {
    char postfix[100];
    printf("중위 표기법: %s\n", infix);
    infixToPostfix(infix, postfix);
    printf("변환된 후위 표기법: %s\n", postfix);
}

void debugPostfixEvaluation(const char* postfix) {
    printf("후위 표기법: %s\n", postfix);
    int result = evaluatePostfix(postfix);
    printf("계산 결과: %d\n", result);
}

결과 분석

정상 입력: 예상대로 동작.
잘못된 입력: 적절한 오류 메시지 출력.
복잡한 수식: 연산 순서와 결과 정확.

확장 가능성

자동화된 테스트 프레임워크 사용.
유효하지 않은 입력에 대해 더 구체적인 예외 처리 추가.
실행 시간 및 메모리 사용량 최적화.

디버깅과 테스트를 통해 계산기의 신뢰성과 정확성을 보장하며, 다음 단계에서는 최종 요약을 작성합니다.

요약

본 기사에서는 C 언어로 스택 기반 계산기를 구현하는 과정을 다뤘습니다. 스택의 기본 개념부터 시작해 중위 표기법을 후위 표기법으로 변환하고 이를 계산하는 알고리즘까지 자세히 설명했습니다.

스택은 데이터 구조의 핵심을 이해하고 복잡한 연산을 처리하기 위한 강력한 도구입니다. 계산기를 구현함으로써 연산자 우선순위, 후위 표기법의 유용성, C 언어의 메모리 관리 등을 배울 수 있습니다. 추가적으로 디버깅과 다양한 테스트를 통해 프로그램의 안정성과 신뢰성을 확보할 수 있었습니다.

이 프로젝트는 C 언어와 데이터 구조 학습의 실질적인 사례로 활용될 수 있습니다.