자료구조: 후위 표기식 계산기 예시

정지인·2025년 6월 21일

📌 스택 기본 구현 예제 (Stack Operations in C)

✅ 전체 기능 요약

이 코드는 배열 기반 스택 구조를 C 언어로 구현한 예제입니다. 주요 기능은 다음과 같습니다:

스택 초기화, 삽입(push), 제거(pop), 확인(peek)
스택 전체 출력(print)
오버플로우, 언더플로우 검사
예제 실행: 문자 'c', 'a', 't', 's'를 삽입하고 출력 후 peek 수행

🧾 전체 코드

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

#define N 100

typedef struct StackType {
    int top;
    char stack[N];
} StackType;

void init(StackType* S) {
    S->top = -1;
}

int isFull(StackType* S) {
    return S->top == N - 1;
}

int isEmpty(StackType* S) {
    return S->top == -1;
}

void push(StackType* S, char c) {
    if (isFull(S))
        printf("Overflow!\n");
    else {
        S->top++;
        S->stack[S->top] = c;
    }
}

char peek(StackType* S) {
    if (isEmpty(S)) {
        printf("Empty!\n");
        return -1;
    }
    return S->stack[S->top];
}

char pop(StackType* S) {
    if (isEmpty(S)) {
        printf("Empty!\n");
        return -1;
    }
    return S->stack[S->top--];
}

void print(StackType* S) {
    for (int i = 0; i <= S->top; i++) {
        printf("%c", S->stack[i]);
    }
    printf("\n");
}

// -------------------------------------------------------------

int main() {
    StackType S;
    init(&S);

    push(&S, 'c');
    push(&S, 'a');
    push(&S, 't');
    push(&S, 's');

    print(&S);  // 출력: cats

    getchar();  // 엔터 대기 (디버깅용)

    printf("After pop : %c\n", peek(&S));  // top에 있는 's' 출력

    return 0;
}

✅ 출력 예시

cats
After pop : s

✅ 요약

이 코드는 스택 연산의 기본을 연습할 수 있는 좋은 예제입니다.
문자열을 문자 단위로 스택에 넣고 꺼내보는 테스트에 적합합니다.
응용 확장: 정수 스택, 동적 할당, 구조체 저장 등

필요 시, 다양한 타입(Generic) 또는 동적 메모리 할당 기반으로 리팩터링할 수 있습니다.

📌 괄호 검사 프로그램 (Bracket Matching using Stack)

✅ 전체 기능 요약

스택 자료구조 정의 및 연산
- 구조체 StackType을 정의하고, push, pop, peek, isEmpty, isFull, print 등의 기본 스택 연산을 구현합니다.
괄호 검사 기능 (check)
- 중괄호 {}, 대괄호 [], 소괄호 ()의 짝이 맞는지 검사합니다.
- 여는 괄호는 스택에 push하고, 닫는 괄호가 나올 때 스택에서 pop하여 짝이 맞는지 비교합니다.

실행 흐름

char expr[N];
scanf("%s", expr);
if (check(expr))
    printf("Success!\n");
else
    printf("Fail\n");

입력된 문자열 내 괄호의 짝이 올바른지 판단하고 그 결과를 출력합니다.

예시 입력/출력
- 입력: ({[]}) → 출력: Success!
- 입력: ({[}) → 출력: Fail

🧾 전체 코드

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define N 100

typedef struct StackType
{
	int top;
	char stack[N];
} StackType;

void init(StackType *S) {
	S->top = -1;
}

int isFull(StackType* S) {
	return S->top == N - 1;
}

int isEmpty(StackType* S) {
	return S->top == -1;
}

void push(StackType* S, char c) {
	if (isFull(S))
		printf("Overflow!\n");
	else {
		S->top++;
		S->stack[S->top] = c;
	}
}

char peek(StackType* S) {
	if (isEmpty(S)) {
		printf("Empty!\n");
		return -1;
	}
	return S->stack[S->top];
}

char pop(StackType* S) {
	if (isEmpty(S)) {
		printf("Empty!\n");
		return -1;
	}
	return S->stack[S->top--];
}

void print(StackType* S) {
	for (int i = 0; i <= S->top; i++) {
		printf("%c", S->stack[i]);
	}
	printf("\n");
}

int check(char expr[]) {
	StackType S;
	init(&S);

	char c, t;
	int n = strlen(expr);

	for (int i = 0; i < n; i++) {
		c = expr[i];
		if (c == '(' || c == '{' || c == '[')
			push(&S, c);
		else if (c == ')' || c == '}' || c == ']') {
			if (isEmpty(&S))
				return 0;
			t = pop(&S);
			if ((t == '(' && c != ')') ||
				(t == '{' && c != '}') ||
				(t == '[' && c != ']'))
				return 0;
		}
	}
	return isEmpty(&S);
}

int main() {
	char expr[N];
	scanf("%s", expr);

	if (check(expr))
		printf("Sucess!\n");
	else
		printf("Fail\n");

	/* 디버그용 코드 (사용 안함)
	StackType S;
	init(&S);
	push(&S, 'c');
	push(&S, 'a');
	push(&S, 't');
	push(&S, 's');
	print(&S);
	getchar();
	printf("After pop : %c\n", peek(&S));
	*/

	return 0;
}

✅ 요약

스택을 사용하여 괄호 짝을 검사하는 전형적인 문제 해결 코드입니다.
실전에서 중첩 구조 검증, HTML/XML 태그 처리, 코드 정적 분석 등에 활용될 수 있습니다.

후위 표기식 계산기 (C 언어 기반)

📌 개요

이 코드는 C 언어로 구현된 후위 표기식 계산기로, 스택 구조를 이용해 수식을 처리합니다. 한 자리 숫자로 구성된 후위 표기식(예: 23+5*)을 입력받아 최종 계산 결과를 출력합니다.

🔧 사용된 자료구조

StackType 구조체

typedef struct StackType {
    int top;
    char stack[N];
} StackType;

스택 자료구조를 배열로 구현 (char형 사용)
top은 현재 스택의 가장 위 인덱스를 의미함

🧱 스택 관련 함수

초기화

void init(StackType* S) {
    S->top = -1;
}

상태 확인

int isFull(StackType* S) {
    return S->top == N - 1;
}

int isEmpty(StackType* S) {
    return S->top == -1;
}

삽입 및 제거

void push(StackType* S, char c) {
    if (isFull(S)) printf("Overflow!\n");
    else S->stack[++S->top] = c;
}

char pop(StackType* S) {
    if (isEmpty(S)) {
        printf("Empty!\n");
        return -1;
    }
    return S->stack[S->top--];
}

char peek(StackType* S) {
    if (isEmpty(S)) {
        printf("Empty!\n");
        return -1;
    }
    return S->stack[S->top];
}

디버그용 출력

void print(StackType* S) {
    for (int i = 0; i <= S->top; i++) {
        printf("%c", S->stack[i]);
    }
    printf("\n");
}

✅ 후위 표기식 계산 함수

함수 정의

int evaluate(char postfix[]) {
    StackType S;
    init(&S);

    int op1, op2, value;
    char c;
    int n = strlen(postfix);

    for (int i = 0; i < n; i++) {
        c = postfix[i];
        if (c != '+' && c != '-' && c != '*' && c != '/') {
            value = c - '0';  // 문자 숫자를 정수로 변환
            push(&S, value);
        } else {
            op2 = pop(&S);
            op1 = pop(&S);
            switch (c) {
                case '+': push(&S, op1 + op2); break;
                case '-': push(&S, op1 - op2); break;
                case '*': push(&S, op1 * op2); break;
                case '/': push(&S, op1 / op2); break;
            }
        }
    }
    return pop(&S);
}

예시 입력/출력

입력: 23+5*   (== (2+3)*5)
출력: 25

🧪 main 함수와 실행 흐름

int main() {
    char postfix[N];
    scanf("%s", postfix);

    printf("%d\n", evaluate(postfix));
    return 0;
}

사용자로부터 후위 수식 문자열 입력을 받아 계산 결과 출력

⚠️ 제한 사항

숫자는 한 자리 숫자만 입력 가능
예: 123+* → 해석 불가능 (문자 하나씩만 인식함)
음수, 공백 구분, 여러 자리 숫자, 실수 등은 처리 불가능

📂 전체 코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N 100

typedef struct StackType {
    int top;
    char stack[N];
} StackType;

void init(StackType* S) {
    S->top = -1;
}

int isFull(StackType* S) {
    return S->top == N - 1;
}

int isEmpty(StackType* S) {
    return S->top == -1;
}

void push(StackType* S, char c) {
    if (isFull(S))
        printf("Overflow!\n");
    else {
        S->top++;
        S->stack[S->top] = c;
    }
}

char peek(StackType* S) {
    if (isEmpty(S)) {
        printf("Empty!\n");
        return -1;
    }
    return S->stack[S->top];
}

char pop(StackType* S) {
    if (isEmpty(S)) {
        printf("Empty!\n");
        return -1;
    }
    return S->stack[S->top--];
}

void print(StackType* S) {
    for (int i = 0; i <= S->top; i++) {
        printf("%c", S->stack[i]);
    }
    printf("\n");
}

int evaluate(char postfix[]) {
    StackType S;
    init(&S);

    int op1, op2, value;
    char c;
    int n = strlen(postfix);

    for (int i = 0; i < n; i++) {
        c = postfix[i];
        if (c != '+' && c != '-' && c != '*' && c != '/') {
            value = c - '0';
            push(&S, value);
        } else {
            op2 = pop(&S);
            op1 = pop(&S);
            switch (c) {
                case '+': push(&S, op1 + op2); break;
                case '-': push(&S, op1 - op2); break;
                case '*': push(&S, op1 * op2); break;
                case '/': push(&S, op1 / op2); break;
            }
        }
    }
    return pop(&S);
}

int main() {
    char postfix[N];
    scanf("%s", postfix);
    printf("%d\n", evaluate(postfix));
    return 0;
}

✅ 마무리

이 코드는 후위 수식을 계산하는 스택 응용 예제로서, 컴파일러, 계산기, 수식 변환 알고리즘 등을 학습할 때 매우 유용한 구조입니다. 필요한 경우 여러 자리 숫자, 공백 구분 등을 처리하는 버전으로 확장 가능합니다.

📌 후위 표기식 계산기 (Postfix Expression Evaluator)

✅ 전체 기능 요약

스택 자료구조 정의 및 연산
- StackType 구조체를 정의하고 push, pop, peek, isEmpty, isFull 등 기본 스택 연산을 구현함
후위 표기식 계산 (evaluate)
- 문자열로 주어진 후위 표기식을 입력받아 스택을 이용해 계산함
- 예: 23+5* → (2 + 3) * 5 → 25
실행 흐름
```
char postfix[N];
scanf("%s", postfix);
printf("%d\n", evaluate(postfix));
```
- 문자열 형태로 수식을 입력받아 evaluate() 함수로 계산 후 결과 출력
제약 사항
- 입력은 한 자리 정수만 가능하며, 공백 없음
- 두 자리 이상의 숫자, 실수, 음수는 처리하지 않음

🧾 전체 코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N 100

typedef struct StackType {
    int top;
    char stack[N];
} StackType;

void init(StackType* S) {
    S->top = -1;
}

int isFull(StackType* S) {
    return S->top == N - 1;
}

int isEmpty(StackType* S) {
    return S->top == -1;
}

void push(StackType* S, char c) {
    if (isFull(S))
        printf("Overflow!\n");
    else {
        S->top++;
        S->stack[S->top] = c;
    }
}

char peek(StackType* S) {
    if (isEmpty(S)) {
        printf("Empty!\n");
        return -1;
    }
    return S->stack[S->top];
}

char pop(StackType* S) {
    if (isEmpty(S)) {
        printf("Empty!\n");
        return -1;
    }
    return S->stack[S->top--];
}

void print(StackType* S) {
    for (int i = 0; i <= S->top; i++) {
        printf("%c", S->stack[i]);
    }
    printf("\n");
}

int evaluate(char postfix[]) {
    StackType S;
    init(&S);

    int op1, op2, value;
    char c;
    int n = strlen(postfix);

    for (int i = 0; i < n; i++) {
        c = postfix[i];
        if (c != '+' && c != '-' && c != '*' && c != '/') {
            value = c - '0';
            push(&S, value);
        } else {
            op2 = pop(&S);
            op1 = pop(&S);
            switch (c) {
                case '+': push(&S, op1 + op2); break;
                case '-': push(&S, op1 - op2); break;
                case '*': push(&S, op1 * op2); break;
                case '/': push(&S, op1 / op2); break;
            }
        }
    }
    return pop(&S);
}

int main() {
    char postfix[N];
    scanf("%s", postfix);
    printf("%d\n", evaluate(postfix));
    return 0;
}

✅ 예시 입력 및 출력

입력:

23+5*

출력:

해석:

2 + 3 = 5
5 * 5 = 25

✅ 확장 방향 (아이디어)

한 자리 숫자 → 여러 자리 숫자 처리 (토큰 기반 파싱 필요)
공백 구분 허용 ("12 3 +") → strtok 또는 sscanf 활용
음수, 실수 지원 → float, double + 예외 처리 추가
연산자 추가 (%, ^, etc)

후위 표기식 계산기는 스택 자료구조의 대표적인 응용 사례로, 컴파일러, 계산기, 알고리즘 수업 등에서 자주 등장합니다.

정지인

멋쟁이사자 13기 백엔드

이전 포스트

자료구조 정복하기 2

다음 포스트

자료구조: 후위 표기식 계산기 예시

📌 스택 기본 구현 예제 (Stack Operations in C)

✅ 전체 기능 요약

🧾 전체 코드

✅ 출력 예시

✅ 요약

📌 괄호 검사 프로그램 (Bracket Matching using Stack)

✅ 전체 기능 요약

🧾 전체 코드

✅ 요약

후위 표기식 계산기 (C 언어 기반)

📌 개요

🔧 사용된 자료구조

StackType 구조체

🧱 스택 관련 함수

초기화

상태 확인

삽입 및 제거

디버그용 출력

✅ 후위 표기식 계산 함수

함수 정의

예시 입력/출력

🧪 main 함수와 실행 흐름

⚠️ 제한 사항

📂 전체 코드

✅ 마무리

📌 후위 표기식 계산기 (Postfix Expression Evaluator)

✅ 전체 기능 요약

🧾 전체 코드

✅ 예시 입력 및 출력

✅ 확장 방향 (아이디어)

자료구조 정복하기 2

자료구조 정복하기 3

0개의 댓글