본문 바로가기
C/알고리즘

스택 응용(수식 계산)

by 덤더리덤떰 2023. 9. 15.

1. 수식표기법

(1) 중위표기법(infix notation)

: 연산자를 피연산자의 가운데 표기하는 방법 => 우리가 사용하는 방식

ex) A+B

 

(2) 후위표기법(postfix notation)

: 연산자를 피연산자 뒤에 표기하는 방법 => 컴퓨터 처리 방식

: 응용하여 중위표기법->후위표기법->수식 계산

: 스택 이용

ex) AB+

 

1.1 괄호 검사 

: 이때 수식을 계산하기 위해서는 올바른 수식인지 확인하기 위해 괄호 검사가 필요하다

: 수식에 포함된 괄호는 가장 마지막에 열린 괄호가 가장 먼저 닫아주어야 하는 구조를 스택을 통해 구현가능

: 수식검사가 완료된 경우, 공백 스택 상태여야함

  • 왼쪽 괄호를 만나면 스택에 push
  • 오른쪽 괄호를 만나면 스택에서 pop하여 같은 종류의 쌍의 괄호인지 확인
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <stdbool.h>

typedef struct _STACK_NODE_ {
	int item;
	struct _STACK_NODE_* link;
}STACK_NODE;

typedef struct _STACK_HEAD_ {
	STACK_NODE* top;
}STACK_HEAD;

STACK_HEAD* MakeStack() {
	STACK_HEAD* head = (STACK_HEAD*)calloc(1, sizeof(STACK_HEAD));
	assert(head != NULL);

	return head;
}

void push(STACK_HEAD* H, char item) {
	STACK_NODE* newNode = (STACK_NODE*)calloc(1, sizeof(STACK_NODE));
	assert(newNode != NULL);
	newNode->item = item;
	newNode->link = NULL;

	if (H->top == NULL) {
		H->top = newNode;
	}
	else {
		newNode->link = H->top;
		H->top = newNode;
	}
}

int IsEmpty(STACK_HEAD* H) {
	return H->top == NULL;
}

char pop(STACK_HEAD* H) {
	if (IsEmpty(H)) {
		printf("\n공백 스택입니다\n");
		return;
	}
	else {
		char data = H->top->item;

		STACK_NODE* curNode = H->top;
		H->top = H->top->link;
		free(curNode);
		curNode = NULL;
		
		return data;
	}
}


int testPair(char* express) {
	STACK_HEAD* head = MakeStack();

	for (int i = 0; i < strlen(express); i++) {
		if (express[i] == '(' || express[i] == '{' || express[i] == '[') {
			push(head, express[i]);
		}
		else if (express[i] == ')' || express[i] == '}' || express[i] == ']') {
			if (IsEmpty(head)) {
				return false;
			}
			char data = pop(head);
			switch (express[i]) {
			case ')':
				if (data != '(') {
					return false;
				}break;
			case ']':
				if (data != '[') {
					return false;
				}break;
			case '}':
				if (data != '{') {
					return false;
				}break;
			}
		}
	}
	if (!IsEmpty(head)) {
		return false;
	}
	else {
		return true;
	}
}


int main() {

	char* express = "((A*B)-(C/D))";
	if (testPair(express) == 1) {
		printf("수식의 괄호가 맞게 사용되었습니다!\n");
	}
	else {
		printf("수식의 괄호가 틀렸습니다!\n");
	}



	getchar();
	return 0;
}

1.2 중위표기법 -> 후위표기법 

(1) 소괄호가 명확하게 제공되는 경우 

  • 왼쪽 괄호를 만나는 경우 무시
  • 피연산자를 만나는 경우 바로 출력
  • 연산자를 만나는 경우 스택에 push
  • 오른쪽 괄호를 만나는 경우 스택 pop하여 출력
  • 수식이 끝나면 공백스택이 될 때까지 pop하여 출력
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <stdbool.h>

typedef struct _STACK_NODE_ {
	int item;
	struct _STACK_NODE_* link;
}STACK_NODE;

typedef struct _STACK_HEAD_ {
	STACK_NODE* top;
}STACK_HEAD;

STACK_HEAD* MakeStack() {
	STACK_HEAD* head = (STACK_HEAD*)calloc(1, sizeof(STACK_HEAD));
	assert(head != NULL);

	return head;
}

void push(STACK_HEAD* H, char item) {
	STACK_NODE* newNode = (STACK_NODE*)calloc(1, sizeof(STACK_NODE));
	assert(newNode != NULL);
	newNode->item = item;
	newNode->link = NULL;

	if (H->top == NULL) {
		H->top = newNode;
	}
	else {
		newNode->link = H->top;
		H->top = newNode;
	}
}

int IsEmpty(STACK_HEAD* H) {
	return H->top == NULL;
}

char pop(STACK_HEAD* H) {
	if (IsEmpty(H)) {
		printf("\n공백 스택입니다\n");
		return;
	}
	else {
		char data = H->top->item;

		STACK_NODE* curNode = H->top;
		H->top = H->top->link;
		free(curNode);
		curNode = NULL;
		
		return data;
	}
}


int testPair(char* express) {
	STACK_HEAD* head = MakeStack();

	for (int i = 0; i < strlen(express); i++) {
		if (express[i] == '(' || express[i] == '{' || express[i] == '[') {
			push(head, express[i]);
		}
		else if (express[i] == ')' || express[i] == '}' || express[i] == ']') {
			if (IsEmpty(head)) {
				return false;
			}
			char data = pop(head);
			switch (express[i]) {
			case ')':
				if (data != '(') {
					return false;
				}break;
			case ']':
				if (data != '[') {
					return false;
				}break;
			case '}':
				if (data != '{') {
					return false;
				}break;
			}
		}
	}
	if (!IsEmpty(head)) {
		return false;
	}
	else {
		return true;
	}
}


void infix_postfix(char* express, char * res) {
	//괄호 필수인 경우
	//1. 왼쪽 괄호인 경우 무시 
	//2. 피연산자인 경우 출력
	//3. 연산자인 경우 스택에 push 
	//4. 오른쪽 괄호인 경우 pop하여 출력 
	//5. 반복문 모두 끝나면 공백스택이 될 때까지 pop
	STACK_HEAD* head = MakeStack();
	int j = 0;
	for (int i = 0; i < strlen(express); i++) {
		if (express[i] == '(') {
			continue;
		}
		else if (express[i] >= 'A' &&express[i] <= 'Z') {
			res[j++] = express[i];
		}
		else if(express[i]=='+'||express[i]=='-'||express[i]=='/'||express[i]=='*'){
			push(head, express[i]);
		}
		else if (express[i] == ')') {
			res[j++] = pop(head);
		}
	}
	while (!IsEmpty(head)) {
		res[j++] = pop(head);
	}

	res[j] = '\0';
}

int main() {

	char* express = "((A*B)-(C/D))";
	if (testPair(express) == 1) {
		printf("수식의 괄호가 맞게 사용되었습니다!\n");

		char* res = (char*)calloc(strlen(express) + 1, sizeof(char));
		assert(res != NULL);

		infix_postfix(express, res);
		printf("중위표기 : %s => 후위표기 : %s ", express, res);
	}
	else {
		printf("수식의 괄호가 틀렸습니다!\n");
	}


	getchar();
	return 0;
}

(2) 소괄호 생략하는 경우(generic method)

  • 피연산자를 만나면 그대로 출력(이전과 동일)
  • 연산자를 만나면

ⓐ 우선순위(현재 연산자) > 우선순위(top에 저장된 연산자) : 스택에 push

ⓑ 우선순위(현재 연산자) <= 우선순위(top에 저장된 연산자) : 자신보다 더 높은 우선순위의 연산자 만날때까지 기존 연산자들 스택에서 pop하고 자기자신 push

ex) a*b-c/d인 경우 *이 -보다 더 먼저 수행되어야 하기 때문에 top에 있어야함 이 경우는 ⓐ

  • 왼쪽 괄호는 우선순위가 가장 낮은 연산자 취급 ( 왼쪽 괄호가 나오면 그냥 스택에 push) 
  • 오른쪽 괄호가 나오면 스택에서 왼쪽 괄호 나올때까지 스택에 쌓인 연산자 pop하여 출력
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <stdbool.h>

typedef struct _STACK_NODE_ {
	int item;
	struct _STACK_NODE_* link;
}STACK_NODE;

typedef struct _STACK_HEAD_ {
	STACK_NODE* top;
}STACK_HEAD;

STACK_HEAD* MakeStack() {
	STACK_HEAD* head = (STACK_HEAD*)calloc(1, sizeof(STACK_HEAD));
	assert(head != NULL);

	return head;
}

void push(STACK_HEAD* H, char item) {
	STACK_NODE* newNode = (STACK_NODE*)calloc(1, sizeof(STACK_NODE));
	assert(newNode != NULL);
	newNode->item = item;
	newNode->link = NULL;

	if (H->top == NULL) {
		H->top = newNode;
	}
	else {
		newNode->link = H->top;
		H->top = newNode;
	}
}

int IsEmpty(STACK_HEAD* H) {
	return H->top == NULL;
}

char pop(STACK_HEAD* H) {
	if (IsEmpty(H)) {
		printf("\n공백 스택입니다\n");
		return;
	}
	else {
		char data = H->top->item;

		STACK_NODE* curNode = H->top;
		H->top = H->top->link;
		free(curNode);
		curNode = NULL;
		
		return data;
	}
}

char peek(STACK_HEAD* H) {
	if (IsEmpty(H)) {
		printf("\n공백 스택입니다\n");
		return;
	}
	else {
		return H->top->item;
	}
}


int testPair(char* express) {
	STACK_HEAD* head = MakeStack();

	for (int i = 0; i < strlen(express); i++) {
		if (express[i] == '(' || express[i] == '{' || express[i] == '[') {
			push(head, express[i]);
		}
		else if (express[i] == ')' || express[i] == '}' || express[i] == ']') {
			if (IsEmpty(head)) {
				return false;
			}
			char data = pop(head);
			switch (express[i]) {
			case ')':
				if (data != '(') {
					return false;
				}break;
			case ']':
				if (data != '[') {
					return false;
				}break;
			case '}':
				if (data != '{') {
					return false;
				}break;
			}
		}
	}
	if (!IsEmpty(head)) {
		return false;
	}
	else {
		return true;
	}
}

int precedence(char item) {
	switch (item) {
	case '(':
	case ')':
		return 0;
	case '+':
	case '-':
		return 1;
	case '%':
	case '/':
	case '*':
		return 2;
	}
}


void infix_postfix(char* express, char * res) {
	//generic한 경우
	//1. 피연산자를 만나는 경우 그대로 출력
	//2. 연산자를 만나는 경우 현재 연산자의 우선순위가 top에 있는 연산자의 우선순위보다 높다면 push
	//2-1. 현재 연산자의 우선순위가 top에 있는 연산자의 우선순위보다 낮거나 같다면 높은 애 나올 때까지 pop하고 push
	//3. 왼쪽 괄호는 우선순위가 가장 낮음
	//4. 오른쪽 괄호를 만나는 경우 왼쪽 괄호를 만날 때까지 pop하여 출력
	int j = 0;
	STACK_HEAD* head = MakeStack();
	
	for (int i = 0; i < strlen(express); i++) {
		if (express[i] >= 'A' && express[i] <= 'Z') {
			res[j++] = express[i];
		}
		else if (express[i] == '+' || express[i] == '-' || express[i] == '*' || express[i] == '/' || express[i] == '%') {
			while (!IsEmpty(head)) {
				int data = peek(head);
				if (precedence(data) >= precedence(express[i])) {
					res[j++] = pop(head);
				}
				else {
					break;
				}
			}
			push(head, express[i]); //공백 스택인 경우와 push하는 경우 포함 
		}
		else if (express[i] == '(') {
			//왼쪽 괄호는 우선순위를 고려할 필요 없음 (연산자가 아니기때문에 우선순위 비교 필요 x) 
			push(head, express[i]);
		}
		else if (express[i] == ')') {
			//왼쪽 소괄호 만날 때까지 pop하여 출력
			while (!IsEmpty(head)) {
				char data = pop(head);
				if (data == '(') {
					break;
				}
				else {
					res[j++] = data;
				}
			}
		}
	}

	while (!IsEmpty(head)) {
		res[j++] = pop(head);
	}
	res[j] = '\0';
}

int main() {

	char* express = "A*B-C/D";
	if (testPair(express) == 1) {
		printf("수식의 괄호가 맞게 사용되었습니다!\n");

		char* res = (char*)calloc(strlen(express) + 1, sizeof(char));
		assert(res != NULL);

		infix_postfix(express, res);
		printf("중위표기 : %s => 후위표기 : %s ", express, res);
	}
	else {
		printf("수식의 괄호가 틀렸습니다!\n");
	}


	getchar();
	return 0;
}

1-3. 후위표기식 수식 계산

  • 피연산자가 나오면 그대로 stack에 push
  • 연산자가 나오면 필요한 만큼의 피연산자를 스택에서 pop하여 연산하고 연산 결과를 다시 스택에 push
  • 수식이 끝나면 마지막으로 스택을 pop하여 출력 
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include <string.h>

#define MAX_SIZE 80

typedef struct _STACK_NODE_ {
	int item;
	struct _STACK_NODE_* link;
}STACK_NODE;

typedef struct _STACK_HEAD_ {
	STACK_NODE* head;
}STACK_HEAD;

STACK_HEAD* MakeStack() {
	STACK_HEAD* H = (STACK_HEAD*)calloc(1, sizeof(STACK_HEAD));
	assert(H != NULL);
	H->head = NULL;

	return H;
}

int IsEmpty(STACK_HEAD* H) {
	return H->head == NULL;
}

void push(STACK_HEAD* H, int item) {
	STACK_NODE* newNode = (STACK_NODE*)calloc(1, sizeof(STACK_NODE));
	assert(newNode != NULL);

	newNode->item = item;
	newNode->link = NULL;
	if (H->head == NULL) {
		H->head = newNode;
	}
	else {
		newNode->link = H->head;
		H->head = newNode;
	}
}

int pop(STACK_HEAD* H) {
	if (IsEmpty(H)) {
		fprintf(stderr, "공백노드이기 때문에 pop할 수 없습니다\n");
		return;
	}
	else {
		int data = H->head->item;
		STACK_NODE* curNode = H->head;
		H->head = curNode->link;
		free(curNode);
		curNode = NULL;

		return data;
	}
}

int peek(STACK_HEAD* H) {
	if (IsEmpty(H)) {
		fprintf(stderr, "공백노드이기 때문에 peek할 수 없습니다\n");
		return;
	}
	else {
		return H->head->item;
	}
}


//괄호 검사 

bool testPair(char* express) {
	STACK_HEAD* head = MakeStack();
	for (int i = 0; i < strlen(express); i++) {
		if (express[i] == '(' || express[i]=='{' || express[i]=='[') {
			push(head, express[i]);
		}
		else if (express[i] == ')') {
			if (IsEmpty(head)) {
				return false;
			}
			else {
				char data=pop(head);
				switch (express[i]) {
				case ')':
					if (data != '(') {
						return false;
					}
					break;

				case ']':
					if (data != '[') {
						return false;
					}
					break;
				case '}':
					if (data != '{') {
						return false;
					}
					break;
				}
			}

		}
	}
	if (!IsEmpty(head)) {
		return false;
	}
	else {
		return true;
	}
}

int precedence(char item) {
	switch (item) {
	case '(':
	case ')':
		return 0;
	case '+':
	case '-':
		return 1;
	case '%':
	case '/':
	case '*':
		return 2;
	}
}


void infix_to_postfix(char* express, char* res) {
	STACK_HEAD* head = MakeStack();
	//3*5-6/2
	//일반화된 경우
	//1. 피연산자가 나오는 경우 그대로 출력
	//2. 연산자가 나오는 경우 현재 연산자의 우선순위가 top에 있는 연산자의 우선순위보다 높은 경우 그대로 push
	//2-1. 현재 연산자의 우선순위가 top에  있는 연산자의 우선순위보다 작거나 같은 경우 자기자신보다 높은 우선순위의 연산자가 나올 때까지 pop하고 자기자신 push
	//3. 왼쪽 괄호는 우선순위 가장 낮음
	//4. 오른쪽 괄호가 나오는 경우 왼쪽 괄호가 나올때까지 pop하여 출력 
	int k = 0;
	for (int i = 0; i < strlen(express); i++) {
		if (express[i] >= '0' && express[i] <= '9') {
			//90처럼 두자리 숫자도 고려
			int j = i;
			while (express[j] >= '0' && express[j] <= '9') {
				res[k++] = express[j];
				j++;
			}
			//while문을 빠져나오면 j번째에서 숫자가 더이상 나오지 않는 경우
			i = j-1;
			res[k++] = ' ';
		}
		else if (express[i] == '(') {
			push(head, express[i]);
		}
		else if (express[i] == ')') {
			//왼쪽 괄호가 나올때까지 pop하여 출력 
			while (!IsEmpty(head)) {
				char data = pop(head);
				if (data == '(') {
					break;
				}
				else {
					res[k++] = data;
					res[k++] = ' ';
				}
			}
		}
		else if (express[i] == '+' || express[i] == '-' || express[i] == '*' || express[i] == '/' || express[i] == '%') {
			while (!IsEmpty(head)) {
				char data = peek(head);
				if (precedence(data) < precedence(express[i])) {
					break;
				}
				else {
					res[k++] = pop(head);
					res[k++] = ' ';
				}
			}
			push(head, express[i]);
		}
	}


	while (!IsEmpty(head)) {
		res[k++] = pop(head);
		res[k++] = ' ';
	}
	res[k] = '\0';



	if (head != NULL) {
		free(head);
		head = NULL;
	}
}

int evaluate(char* express) {
	STACK_HEAD* head = MakeStack();
	//1. 피연산자가 나오면 스택에 push
	//2. 연산자가 나오면 스택에서 pop하고 연산한 후에 다시 스택에 push
	//3. 마지막에 스택에서 pop하여 계산 결과 도출


	for (int i = 0; i < strlen(express); i++) {
		if (express[i] >= '0' && express[i] <= '9') {
			//숫자인 경우 두자리 숫자 고려 56인 경우 
			int j = i+1;
			int value = express[i] - '0';
			while (express[j] >= '0' && express[j] <= '9') {
				value *= 10;
				value += (express[j] - '0');
				j++;
			}
			i = j;
			push(head, value);
		}
		else if (express[i] == '+' || express[i] == '-' || express[i] == '%' || express[i] == '/' || express[i] == '*') {
			int data1 = pop(head);
			int data2 = pop(head); 
			int res;
			// 2 1인 경우 data1= 1, data2= 2
			switch (express[i]) {
			case '+':
				res = data1 + data2;
				break;

			case '-':
				res = data2 - data1;
				break;
			case '%':
				res = data2  % data1;
				break;
			case '/':
				res = data2 / data1;
				break;
			case '*':
				res = data2 * data1;
				break;
			}
			push(head, res);
		}
	}

	return pop(head);
}


int main() {

	char infix_expr[13][80] = { "3*5-6/2", "((4+2)/4)-(3+70/(7*5))", "((((5*6)+7)-8)*9)", "((((5*6)+7)-8)*9)+(9+8)*7",
		"((((5*6)+7)-8)*9)+(((9+8)*7)%4)", "(((((((((1*2)*3)*4)*5)*6)*7)*8)*9)*10)","1*2+3*4+6/2+8%3+9-8", "70+80*9-10+(60+70+80*2-10)",
		"(9-(4/2+1))*(5*2-2)", "((80*87)/4)*2-705", "100*((90-80+20*5)-(30*20-10/5))", "(9-(4/2+1+(10*5)+7*6))*(50*20-10%2)", 
		"123+456*(789+(90-80+20*5)-(30*20-10/5))", };

	char postfix_expr[MAX_SIZE];

	for (int i = 0; i < 13; i++) {
		if(testPair(infix_expr[i])) {
			printf("\n=============================================================================================================");
			printf("\n%d번째 수식의 괄호가 맞게 사용되었습니다!\n", i+1);
			memset(postfix_expr, 0, sizeof(postfix_expr));
			infix_to_postfix(infix_expr[i], postfix_expr);
			printf("전위 표기 : %s => 후위 표기 : %s \n", infix_expr[i], postfix_expr);

			printf("\n수식 계산 결과: %d\n", evaluate(postfix_expr));
		}
		else {
			printf("수식의 괄호가 틀렸습니다!\n");
		}

	}







	getchar();
	return 0;
}

'C > 알고리즘' 카테고리의 다른 글

큐 응용 : 미로문제(Maze problem)  (0) 2023.09.19
스택 응용 : 미로문제(Maze problem)  (0) 2023.09.15
강한 결합 요소(Strongly Connected Components)  (0) 2023.08.15
위상정렬(Topology sort)  (0) 2023.08.14
Floyd Washall Algorithm(플로이드 와샬 알고리즘)  (1) 2023.08.14

관련글

티스토리툴바