[C언어] 스택의 응용 (후위표현식)

후위표현식의 계산

$(A+B)*C$ $\to$ $AB+C*$

- 괄호를 사용하지 않고 왼편에서 오른편으로 수식을 읽으면서 바로 계산한다.

- 연산자 우선순위를 고려할 필요가 없어 컴파일러는 중위표현식을 후위표현식으로 변환 후 계산한다.

 

 

 

후위표현식에서의 스택 사용

1. 피연산자가 들어오면 스택에 푸시한다.

2. 연산자가 들어오면 스택에 쌓인 피연산자 두 개를 꺼내 해당 연산을 실행한다.

- 그러나 먼저 팝된 피연산자가 연산자의 오른쪽으로 놓고 연산을 실행한다.

3. 그 결과를 다시 스택에 푸시한다.

4. 마지막에는 스택에 최종 계산 결과만 남게 된다.

 

 

 

스택 구조체 선언

#include <stdio.h>
#define MaxStackSize 10

typedef struct {
	int Top;
	double data[MaxStackSize];
} stackType;

 

push 함수

void push(stackType* Sptr, double Item) {
	if (isFull(Sptr)) {
		printf("더 이상 넣을 수 없습니다!");
	}
	else {
		// data[Top+1]에 데이터 삽입, Top을 1증가
		Sptr->data[Sptr->Top + 1] = Item;
		Sptr->Top = Sptr->Top + 1;
	}
}

 

pop 함수

double pop(stackType* Sptr) {
	if (isEmpty(Stpr)) {
		printf("스택이 비었습니다.\n");
	}
	else {
		Sptr->Top = Sptr->Top - 1;
		return Sptr->data[Sptr->Top];
	}
}

 

stack_array_postfix 전체 코드

#include <stdio.h>
#define MaxStackSize 10

typedef struct {
	int Top;
	double data[MaxStackSize];
} stackType;


int init(stackType* Sptr) {
	Sptr->Top = -1;
}

int isFull(stackType* Sptr) {
	return (Sptr->Top >= MaxStackSize);
}

int isEmpty(stackType* Sptr) {
	return (Sptr->Top < 0);
}

int getSize(stackType* Sptr) {
	return (Sptr->Top + 1);
}


void push(stackType* Sptr, double Item) {
	if (isFull(Sptr)) {
		printf("더 이상 넣을 수 없습니다!\n");
	}
	else {
		// data[Top+1]에 데이터 삽입, Top을 1증가
		Sptr->data[Sptr->Top + 1] = Item;
		Sptr->Top = Sptr->Top + 1;
	}
}

double pop(stackType* Sptr) {

	double temp;
	if (isEmpty(Sptr)) {
		printf("스택이 비었습니다.\n");
		return -1;
	}
	else {

		temp = Sptr->data[Sptr->Top];
		Sptr->Top = Sptr->Top - 1;
		return temp;
	}
}

 

 

 

 

후위표현식 계산프로그램 구현

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "stack_array_postfix.h"

double cal_postfix(char expr[]) 
{
	// 연산에 필요한 임시 변수 정의
	char c;
	int i = 0;
	int st_value, val_left, val_right;

	stackType st1; // 스택 생성
	init(&st1);    // 스택 초기화


	for (i = 0; i < strlen(expr); i++) {
		c = expr[i]; // 각각의 문자를 변수 c에 저장

		// c가 숫자일 경우 스택에 넣고
		// 연산자일 경우 스택에서 2개를 꺼내 계산 후
		// 결과를 스택에 삽입
		if (c >= '0' && c <= '9') {
			st_value = c - '0';
			push(&st1, st_value);
		}
		else {
			val_right = pop(&st1);
			val_left = pop(&st1);
			switch (c) {
			case '+': push(&st1, (val_left + val_right)); break;
			case '-': push(&st1, (val_left - val_right)); break;
			case '*': push(&st1, (val_left * val_right)); break;
			case '/': push(&st1, (val_left / val_right)); break;
			}
		}

	}

	// 스택에는 최종 결과만 남아있게 됨.
	return pop(&st1);

}

 

 

계산해보기

void main() {

	// 연산식 2개 정의
	char expr1[10] = "25+3*1-";
	char expr2[10] = "25+3+2/";

	printf("연산식: %s의 값은 $lf 입니다.\n", expr1, cal_postfix(expr1));
	printf("연산식: %s의 값은 $lf 입니다.\n", expr2, cal_postfix(expr2));


}

 

연산식: 25+3*1-의 값은 20.000000 입니다.
연산식: 25+3+2/의 값은 5.000000 입니다.