C언어 스택을 이용한 후위 계산기

 후위 계산기라고 제목에 있습니다.

이를 하기 전 표기법부터 알아야합니다.

* 중위 표기법(infix) : 일반적으로 사용하는 (a + b)의 형태

* 후위 표기법(postfix) : 연산자를 피연산자의 뒷쪽에 표시하는 방법

ex) (a + b) * c / d + e

---> ( (a + b) * c / d ) + e

---> ( (a + b) * c / d ) e +

---> ( (a + b) * c ) d / e + 

---> (a + b) c * d / e + 

---> a b + c * d / e + 

이렇게 복잡해보이는 후위 표기법을 사용하는 이유는 컴퓨터는 이 상태를 더 이해하기 쉽다고 합니다. (신기...)

중위 표기법을 후위 표기법으로 변환할 때 스택을 사용하게 됩니다. 스택을 사용했을 때의 동작과정은 다음과 같습니다.

1. 일단 ( 는 무시 했습니다.

2. 피연산자(숫자)가 나오면 프린트

3. 연산자일 경우 스택에 저장

4. 피연산자 일 때, 스택에 연산자가 저장되어 있으면 출력

5. 피연산자가 없을때, 스택에 저장되어 있으면 출력

후위 연산식을 계산할 때에는 다음과 같이 했습니다.

1. 숫자가 입력되면 Stack에 input

2. 연산자가 입력되면, Stack에서 두 개의 피연산자(숫자)를 꺼내서 계산

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

typedef struct {
	char data[100]; //string
	struct Node* next;
} Node;

typedef struct {
	Node* top;
} Stack;

void push(Stack* stack, char* data) {
	Node* node = (Node*)malloc(sizeof(Node));
	strcpy(node->data, data);
	node->next = stack->top;
	stack->top = node;
}

char* getTop(Stack* stack) {
	Node* top = stack->top;
	return top->data;
}

char* pop(Stack* stack) {
	if (stack->top == NULL) {
		printf("UnderFlow\n");
		return -INF;
	}
	Node* node = stack->top;
	char* data = (char*)malloc(sizeof(char) * 100);
	strcpy(data, node->data);
	stack->top = node->next;
	free(node);
	return data;
}

int getPriority(char* i) {
	if (!strcmp(i, "(")) return 0;
	if (!strcmp(i, "+") || !strcmp(i, "-")) return 1;
	if (!strcmp(i, "*") || !strcmp(i, "/")) return 2;
	return 3;
}

char* transition(Stack* stack, char** s, int size) {
	char res[1000] = "";
	for (int i = 0; i < size; i++) {
		if (!strcmp(s[i], "+") || !strcmp(s[i], "-") || !strcmp(s[i], "*") || !strcmp(s[i], "/")) {
			while (stack->top != NULL && getPriority(getTop(stack)) >= getPriority(s[i])) {
				strcat(res, pop(stack)); strcat(res, " ");
			}
			push(stack, s[i]);
		}
		else if (!strcmp(s[i], "(")) push(stack, s[i]);
		else if (!strcmp(s[i], ")")) {
			while (strcmp(getTop(stack), "(")) {
				strcat(res, pop(stack)); strcat(res, " ");
			}
			pop(stack);
		}
		else { 
			strcat(res, s[i]); 
			strcat(res, " "); 
		}
	}
	while (stack->top != NULL) {
		strcat(res, pop(stack)); 
		strcat(res, " ");
	}
	return res;
}

void calculate(Stack* stack, char** s, int size) {
	int x, y, z;
	for (int i = 0; i < size; i++) {
		if (!strcmp(s[i], "+") || !strcmp(s[i], "-") || !strcmp(s[i], "*") || !strcmp(s[i], "/")) {
			x = atoi(pop(stack));
			y = atoi(pop(stack));
			if (!strcmp(s[i], "+")) z = y + x;
			if (!strcmp(s[i], "-")) z = y - x;
			if (!strcmp(s[i], "*")) z = y * x;
			if (!strcmp(s[i], "/")) z = y / x;
			char buffer[100];
			sprintf(buffer, "%d", z);
			push(stack, buffer);
		}
		else {
			push(stack, s[i]);
		}
	}
	printf("%s\n", pop(stack));
}

int main(void) {
	Stack stack;
	stack.top = NULL;
	char a[100] = "( ( 3 + 4 ) * 5 ) - 5 * 7 * 5 - 5 * 10";
	int size = 1;
	for (int i = 0; i < strlen(a); i++) {
		if (a[i] == ' ') size++;
	}
	char* ptr = strtok(a, " ");
	char** input = (char**)malloc(sizeof(char*) * size);
	for (int i = 0; i < size; i++) {
		input[i] = (char*)malloc(sizeof(char) * 100);
	}
	for (int i = 0; i < size; i++) {
		strcpy(input[i], ptr);
		ptr = strtok(NULL, " ");
	}
	char b[1000] = "";
	strcpy(b, transition(&stack, input, size));
	printf("후위 표기법: %s\n", b);

	size = 1;
	for (int i = 0; i < strlen(b) - 1; i++) {
		if (b[i] == ' ') size++;
	}
	char* ptr2 = strtok(b, " ");
	for (int i = 0; i < size; i++) {
		strcpy(input[i], ptr2);
		ptr2 = strtok(NULL, " ");
	}
	calculate(&stack, input, size);
	
	system("pause");
	return 0;
}