C 언어에서 스택 자료구조는 데이터의 선입후출(LIFO, Last In First Out) 특성을 활용하는 강력한 도구입니다. 스택을 기반으로 수식 계산기를 구현하면 효율적인 데이터 처리와 명확한 논리 구조를 갖춘 프로그램을 만들 수 있습니다. 본 기사에서는 스택의 기본 개념부터 이를 활용한 수식 계산기의 구현 과정까지 단계별로 알아봅니다. 이를 통해 스택 자료구조와 C 언어의 실용적인 활용법을 익힐 수 있을 것입니다.
스택 자료구조의 기본 개념
스택(Stack)은 선입후출(LIFO: Last In, First Out) 원칙에 따라 데이터를 처리하는 자료구조입니다. 이는 마지막에 삽입된 데이터가 가장 먼저 제거된다는 것을 의미합니다.
스택의 주요 연산
스택은 몇 가지 기본 연산을 통해 동작합니다:
- Push: 스택에 데이터를 추가합니다.
- Pop: 스택에서 데이터를 제거하고 반환합니다.
- Peek (또는 Top): 스택의 가장 위에 있는 데이터를 제거하지 않고 확인합니다.
- IsEmpty: 스택이 비어 있는지 확인합니다.
- IsFull: 스택이 가득 찼는지 확인합니다.
스택의 활용 사례
스택은 다양한 컴퓨터 과학 문제에서 유용하게 활용됩니다.
- 수식 계산: 후위 표기법을 이용한 수식 평가.
- 괄호 검사: 소스 코드나 수식에서 괄호의 짝이 맞는지 확인.
- 재귀 호출 시 함수 스택: 프로그램 실행 중 함수 호출 기록 관리.
스택은 이러한 단순한 동작 원리를 기반으로 많은 복잡한 문제를 해결할 수 있는 강력한 도구입니다. C 언어를 통해 스택의 구현과 응용을 이해하면 프로그래밍 능력을 크게 향상시킬 수 있습니다.
후위 표기법의 이해
수식 계산에서 후위 표기법(Postfix Notation)은 연산자의 위치를 피연산자 뒤에 두는 방법으로, 수식을 표현하는 방식 중 하나입니다. 이는 스택 자료구조를 이용해 간단하고 효율적으로 계산할 수 있습니다.
후위 표기법의 특징
- 괄호 불필요: 연산자의 우선순위가 내재적으로 결정되므로 괄호를 사용할 필요가 없습니다.
- 평가 간결성: 계산 순서를 명확히 정의하므로 프로그램에서 구현이 용이합니다.
예를 들어:
- 중위 표기법:
(3 + 5) * 2 - 후위 표기법:
3 5 + 2 *
후위 표기법의 장점
- 연산자 우선순위와 괄호 처리 없이도 수식의 계산이 가능합니다.
- 스택을 이용한 계산이 간단하고 빠르며, 프로그래밍에 적합합니다.
후위 표기법의 사용 사례
- 계산기 프로그램
- 컴파일러의 수식 변환 및 최적화
- 데이터 구조 및 알고리즘 문제 해결
후위 표기법은 중위 표기법에서 변환 과정을 통해 만들어지며, 다음 섹션에서는 이 변환 과정에 대해 설명합니다.
C 언어로 스택 구현
스택 자료구조를 C 언어로 구현하기 위해 배열과 연결 리스트를 사용할 수 있습니다. 본 섹션에서는 배열 기반 스택 구현을 다룹니다.
스택의 주요 구조와 정의
스택은 배열로 구현되며, 스택의 크기와 현재 위치를 나타내는 변수를 사용합니다.
#define MAX 100 // 스택의 최대 크기
typedef struct {
int data[MAX]; // 스택 데이터 저장
int top; // 스택의 최상단 인덱스
} Stack;스택 초기화
스택을 초기화하는 함수는 top을 -1로 설정해 비어 있음을 나타냅니다.
void initStack(Stack* s) {
s->top = -1;
}Push 연산
스택에 데이터를 추가합니다.
void push(Stack* s, int value) {
if (s->top == MAX - 1) {
printf("스택 오버플로우\n");
return;
}
s->data[++(s->top)] = value;
}Pop 연산
스택에서 데이터를 제거하고 반환합니다.
int pop(Stack* s) {
if (s->top == -1) {
printf("스택 언더플로우\n");
return -1; // 에러 값
}
return s->data[(s->top)--];
}Peek 연산
스택의 최상단 데이터를 확인합니다.
int peek(Stack* s) {
if (s->top == -1) {
printf("스택이 비어 있습니다\n");
return -1; // 에러 값
}
return s->data[s->top];
}IsEmpty 연산
스택이 비어 있는지 확인합니다.
int isEmpty(Stack* s) {
return s->top == -1;
}스택 활용
이 기본 구현을 통해 후위 표기법 변환 및 계산 알고리즘에서 사용할 수 있는 효율적인 스택 자료구조를 만들 수 있습니다. 다음 단계에서는 이를 활용하여 수식을 변환하는 방법을 알아봅니다.
후위 표기법으로 수식 변환하기
후위 표기법(Postfix Notation)으로 변환하려면 중위 표기법(Infix Notation)을 해석하고 연산자의 우선순위를 고려해야 합니다. 이를 위해 스택을 활용한 알고리즘을 구현할 수 있습니다.
중위 표기법에서 후위 표기법으로의 변환
중위 표기법을 후위 표기법으로 변환하는 주요 규칙은 다음과 같습니다:
- 피연산자는 그대로 출력: 피연산자(숫자 또는 변수)는 바로 출력합니다.
- 연산자는 스택에 저장: 연산자는 우선순위에 따라 스택에 푸시합니다.
- 괄호 처리:
- 여는 괄호는 스택에 푸시합니다.
- 닫는 괄호가 나오면 스택에서 여는 괄호가 나올 때까지 팝하며 출력합니다.
- 스택 정리: 수식의 끝에서 스택에 남아 있는 모든 연산자를 팝하여 출력합니다.
변환 알고리즘의 C 코드
다음은 간단한 중위 표기법을 후위 표기법으로 변환하는 코드입니다.
#include <stdio.h>
#include <ctype.h> // isdigit, isalpha 확인용
#include <string.h>
#define MAX 100
typedef struct {
char data[MAX];
int top;
} Stack;
void initStack(Stack* s) {
s->top = -1;
}
void push(Stack* s, char value) {
if (s->top == MAX - 1) {
printf("스택 오버플로우\n");
return;
}
s->data[++(s->top)] = value;
}
char pop(Stack* s) {
if (s->top == -1) {
printf("스택 언더플로우\n");
return '\0';
}
return s->data[(s->top)--];
}
char peek(Stack* s) {
if (s->top == -1) return '\0';
return s->data[s->top];
}
int precedence(char op) {
if (op == '+' || op == '-') return 1;
if (op == '*' || op == '/') return 2;
if (op == '^') return 3;
return 0;
}
void infixToPostfix(const char* infix, char* postfix) {
Stack s;
initStack(&s);
int k = 0; // Postfix 배열 인덱스
for (int i = 0; i < strlen(infix); i++) {
char ch = infix[i];
if (isalnum(ch)) { // 피연산자 (숫자나 변수)
postfix[k++] = ch;
} else if (ch == '(') { // 여는 괄호
push(&s, ch);
} else if (ch == ')') { // 닫는 괄호
while (peek(&s) != '(') {
postfix[k++] = pop(&s);
}
pop(&s); // 여는 괄호 제거
} else { // 연산자
while (s.top != -1 && precedence(peek(&s)) >= precedence(ch)) {
postfix[k++] = pop(&s);
}
push(&s, ch);
}
}
// 스택에 남아 있는 연산자 처리
while (s.top != -1) {
postfix[k++] = pop(&s);
}
postfix[k] = '\0'; // 문자열 종료
}
int main() {
char infix[MAX], postfix[MAX];
printf("중위 표기법 입력: ");
scanf("%s", infix);
infixToPostfix(infix, postfix);
printf("후위 표기법: %s\n", postfix);
return 0;
}알고리즘의 작동 예시
- 입력:
(3+5)*2 - 출력:
35+2*
결론
위 알고리즘은 중위 표기법을 후위 표기법으로 변환하는 방법을 명확히 보여줍니다. 이를 기반으로 후속 단계에서 후위 표기법 계산기를 구현할 수 있습니다.
후위 표기법을 활용한 수식 계산
후위 표기법으로 변환된 수식을 계산하기 위해 스택 자료구조를 활용할 수 있습니다. 이 과정은 간단하고 연산 순서가 명확하여 효율적입니다.
후위 표기법 계산 알고리즘
- 피연산자 처리:
- 후위 표기법에서 피연산자를 만나면 스택에 푸시합니다.
- 연산자 처리:
- 연산자를 만나면 스택에서 두 개의 피연산자를 팝하고, 해당 연산을 수행한 결과를 다시 스택에 푸시합니다.
- 결과 반환:
- 모든 연산이 끝난 후 스택에 남아 있는 값이 최종 결과입니다.
C 언어로 구현된 코드
다음은 후위 표기법을 계산하는 간단한 C 프로그램입니다.
#include <stdio.h>
#include <ctype.h> // isdigit 함수 사용
#include <stdlib.h> // atoi 함수 사용
#define MAX 100
typedef struct {
int data[MAX];
int top;
} Stack;
void initStack(Stack* s) {
s->top = -1;
}
void push(Stack* s, int value) {
if (s->top == MAX - 1) {
printf("스택 오버플로우\n");
return;
}
s->data[++(s->top)] = value;
}
int pop(Stack* s) {
if (s->top == -1) {
printf("스택 언더플로우\n");
return -1; // 에러 값
}
return s->data[(s->top)--];
}
int evaluatePostfix(const char* postfix) {
Stack s;
initStack(&s);
for (int i = 0; postfix[i] != '\0'; i++) {
char ch = postfix[i];
if (isdigit(ch)) { // 피연산자
push(&s, ch - '0'); // 문자를 숫자로 변환
} else { // 연산자
int operand2 = pop(&s);
int operand1 = pop(&s);
switch (ch) {
case '+':
push(&s, operand1 + operand2);
break;
case '-':
push(&s, operand1 - operand2);
break;
case '*':
push(&s, operand1 * operand2);
break;
case '/':
push(&s, operand1 / operand2);
break;
}
}
}
return pop(&s); // 최종 결과
}
int main() {
char postfix[MAX];
printf("후위 표기법 입력: ");
scanf("%s", postfix);
int result = evaluatePostfix(postfix);
printf("계산 결과: %d\n", result);
return 0;
}알고리즘 작동 예시
- 입력:
35+2* 3과5는 스택에 푸시 → 스택:[3, 5]+연산 수행:3 + 5 = 8→ 스택:[8]2는 스택에 푸시 → 스택:[8, 2]*연산 수행:8 * 2 = 16→ 스택:[16]- 출력:
16
결론
후위 표기법 계산 알고리즘은 스택의 특성을 활용하여 효율적이고 간단하게 구현할 수 있습니다. 이 코드는 계산기 프로그램의 핵심 기능을 제공하며, 다양한 응용 분야에 활용할 수 있습니다.
구현된 수식 계산기의 실행 예시
구현된 후위 표기법 기반 수식 계산기는 입력된 수식을 처리하고 결과를 출력합니다. 이 섹션에서는 입력과 출력 과정을 보여줍니다.
프로그램 실행 과정
아래는 실행 예제입니다:
예제 1: 간단한 계산
- 입력된 후위 표기법:
35+2* - 계산 과정:
3과5를 푸시 → 스택:[3, 5]+연산 수행:3 + 5 = 8→ 스택:[8]2를 푸시 → 스택:[8, 2]*연산 수행:8 * 2 = 16→ 스택:[16]
- 출력 결과:
16
예제 2: 복잡한 계산
- 입력된 후위 표기법:
6523+8*+3+ - 계산 과정:
6과5를 푸시 → 스택:[6, 5]2와3을 푸시 → 스택:[6, 5, 2, 3]+연산 수행:2 + 3 = 5→ 스택:[6, 5, 5]8을 푸시 → 스택:[6, 5, 5, 8]*연산 수행:5 * 8 = 40→ 스택:[6, 5, 40]+연산 수행:5 + 40 = 45→ 스택:[6, 45]+연산 수행:6 + 45 = 51→ 스택:[51]
- 출력 결과:
51
실행 화면
콘솔 출력 예시:
후위 표기법 입력: 6523+8*+3+
계산 결과: 51결론
위 실행 예시는 후위 표기법 수식 계산기가 정확하고 효율적으로 동작함을 보여줍니다. 입력된 수식이 복잡하더라도 스택을 활용하여 단계적으로 연산을 처리할 수 있습니다. 이 계산기는 수학적 연산을 프로그래밍적으로 이해하고 구현하는 데 유용한 도구입니다.
요약
C 언어에서 스택을 활용한 후위 표기법 기반 수식 계산기는 자료구조와 알고리즘의 실용적인 결합을 보여주는 훌륭한 사례입니다. 본 기사에서는 스택의 기본 개념, 중위 표기법에서 후위 표기법으로의 변환, 그리고 후위 표기법 계산 알고리즘까지를 단계적으로 다뤘습니다.
후위 표기법은 연산 우선순위를 명확히 하여 간단한 알고리즘으로 수식을 처리할 수 있게 합니다. 스택을 활용한 구현은 효율적이고 직관적이며, 계산기의 동작 과정을 명확히 이해할 수 있습니다. 이러한 접근법은 계산기 프로그램뿐만 아니라 다양한 응용 분야에서도 활용 가능하며, 알고리즘과 자료구조 학습에 강력한 기초를 제공합니다.
앞으로 이러한 개념을 확장하여 더 복잡한 계산기나 응용 프로그램을 개발할 수 있습니다.