[Data Structure] 스택 - 후위 표기 계산

알고리즘

- 후위 표기 수식 str이 존재

1. str에서 피연산자(숫자)를 만나면 stack에 push
2. str에서 연산자를 만나면 stack에서 pop2번 (숫자1, 숫자2)
3. pop한 숫자 2개를 연산자로 계산
4. 계산결과를 stack에 다시 push

int postfixCalc(const char*str) { // 후위 표기 수식을 계산한 값 리턴
	stack s;
	init_stack(&s);
	char ch; // 후위 표기 수식 str에서 하나하나 추출하는 자료형
	int value = 0; // str에서 추출한 숫자가 문자형일때 '1', '2' 숫자로 변환 1, 2 해서 저장하는 자료형
	int pop1, pop2; // pop1 = 스택에서 pop한 첫번째 값, pop2 = 스택에서 pop한 두번째 값
	int len = strlen(str);

	for (int i = 0; i < len; i++) {
		ch = str[i];
		if (ch != '+' && ch != '-' && ch != '*' && ch != '/') { // ch가 연산자가 아니면
			value = ch - '0'; 
			// 아스키 코드 48부터 숫자 0~9 할당, char형 '1'은 정수값 49
			//따라서 0의 아스키값인 48을 char형에서 빼면 숫자 얻기 가능
			push(&s, value); // 숫자는 stack에 push
		}
		else {
			pop1 = pop(&s);
			pop2 = pop(&s);
			switch (ch) {
			case '+' :
				push(&s, pop2 + pop1);
				break;
			case '-':
				push(&s, pop2 - pop1);
				break;
			case '*':
				push(&s, pop2 * pop1);
				break;
			case '/':
				push(&s, pop2 / pop1);
				break;
			}
		}
	}
	return pop(&s); // stack에 마지막으로 남은 값 = 최종 결과값
}

 

※ Example

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 후위 표기 수식 계산해서 리턴

#define MAX_STACK_SIZE 1000

typedef int element;

typedef struct {
	int top;
	element stack[MAX_STACK_SIZE];
} stack;

void init_stack(stack* s) {
	s->top = -1;
}

int is_full(stack* s) {
	return s->top == MAX_STACK_SIZE - 1;
}

int is_empty(stack* s) {
	return s->top == -1;
}

void push(stack* s, element item) {
	if (is_full(s)) {
		fprintf(stderr, "Error : Stack is full!!");
		return;
	}
	else
		s->stack[++(s->top)] = item;
}

element pop(stack* s) {
	if (is_empty(s)) {
		fprintf(stderr, "Error : Stack is empty!!");
		exit(1);
	}
	else
		return s->stack[(s->top)--];
}

element peek(stack* s) {
	if (is_empty(s)) {
		fprintf(stderr, "Error : Stack is empty!!");
		exit(1);
	}
	else
		return s->stack[s->top];
}

int postfixCalc(const char*str) { // 후위 표기 수식을 계산한 값 리턴
	stack s;
	init_stack(&s);
	char ch; // 후위 표기 수식 str에서 하나하나 추출하는 자료형
	int value = 0; // str에서 추출한 숫자가 문자형일때 '1', '2' 숫자로 변환 1, 2 해서 저장하는 자료형
	int pop1, pop2; // pop1 = 스택에서 pop한 첫번째 값, pop2 = 스택에서 pop한 두번째 값
	int len = strlen(str);

	for (int i = 0; i < len; i++) {
		ch = str[i];
		if (ch != '+' && ch != '-' && ch != '*' && ch != '/') { // ch가 연산자가 아니면
			value = ch - '0'; 
			// 아스키 코드 48부터 숫자 0~9 할당, char형 '1'은 정수값 49
			//따라서 0의 아스키값인 48을 char형에서 빼면 숫자 얻기 가능
			push(&s, value); // 숫자는 stack에 push
		}
		else {
			pop1 = pop(&s);
			pop2 = pop(&s);
			switch (ch) {
			case '+' :
				push(&s, pop2 + pop1);
				break;
			case '-':
				push(&s, pop2 - pop1);
				break;
			case '*':
				push(&s, pop2 * pop1);
				break;
			case '/':
				push(&s, pop2 / pop1);
				break;
			}
		}
	}
	return pop(&s); // stack에 마지막으로 남은 값 = 최종 결과값
}

int main(void) {
	int result = 0;
	char* str1 = "82/3-32*+";
	char* str2 = "234*+";
	char* str3 = "12+7*";

	printf("후위 표기식 %s >>>> 결과 : %d\n", str1, postfixCalc(str1));
	printf("후위 표기식 %s >>>> 결과 : %d\n", str2, postfixCalc(str2));
	printf("후위 표기식 %s >>>> 결과 : %d\n", str3, postfixCalc(str3));

	return 0;
}