C로 만든 후위표기법 (Postfix Notation)

후위표기법 (Postfix Notation)

 

 

후위표기법이 필요한 이유

<중위표기법>

* 우리가 사용하는 사칙연산 공식이 중위표기법이다.

  (2+6/2)+10*3

* 딱 보면 컴퓨터가 이해하기 힘들어 보인다.

  컴퓨터가 이해하기 쉽게 도와주는 방법이 후위표기법을 쓰는 것!

 

 

어떻게 바꾸는데?

* 다른 곳에서 보세여 ㅎㅎ (설명 잘한 곳이 너무 많아서 의욕을 잃음..)

 

 

필요 개념

* 기본적인 C문법 + 스택만 알면 만들 수 있다.

 

 

스택 만들기

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

#define STACK_SIZE 256

char stack[STACK_SIZE];
int top = -1;

void push(char num) {
	if (top >= STACK_SIZE) {
		printf("\nstack overflow");
		return;
	}
	stack[++top] = num;
}

char pop() {
	if (top <= -1) {
		printf("\nno stack");
		return -1;
	}
	return stack[top--];
}

char return_top() {
	if (top <= -1)
		return -1;

	return stack[top];
}

void init_stack() { top = -1; }

int is_stack_empty() { return (top <= -1); }

* Stack은 배열로 만들었다. 배열은 언제나 top변수를 사용해 맨 위에만 참조한다.

 

void push (char num) = num을 스택 맨 위에 넣는다. top 변수가 증가한다.

char pop() = 스택 맨 위를 빼낸다. top 변수가 감소한다.

char return_top() = 맨 위에 있는 값이 무엇인지 반환한다.

void init_stack() = 스택을 초기화한다. 값을 없애지는 않고 top 변수를 -1로 옮기기만 한다.

int is_stack_empty() = 스택이 비어있는지 확인한다.

 

 

추가로 만든 함수

int is_operator(char num) { return (num == '+' || num == '-' || num == '*' || num == '/'); }

int is_num(char num) { return (num >= '0' && num <= '9'); }

int operator_priority(char num) {
	if (num == '(')
		return 0;
	if (num == '+' || num == '-')
		return 1;
	if (num == '*' || num == '/')
		return 2;
	if (num == ')')
		return 3;
	return -1;
}

int is_operator(char num) = num이 연산자인지 확인한다.

int is_num(char num) = num이 (문자인 숫자)인지 확인한다. (char이니까)

int operator_priority(char num) = 연산자 우선순위를 반환한다.

 

 

진짜로 시작하는 postfix 함수

int postfix(char* dest, char* src) {
	char* p = src;

	//스택 초기화
	init_stack();

	while (*p != '\0') {
		//숫자라면
		if (is_num(*p)) {
			*dest++ = *p++;
		}
		//'('라면
		else if (*p == '(') {
			push(*p);
			p++;
		}
		else if (*p == ')') {
			while (return_top() != '(') {
				*dest++ = pop();
			}
			pop();
			p++;
		}
		//연산자라면
		else if (is_operator(*p)) {
			//스택이 비어있다면
			if (is_stack_empty()) {
				push(*p);
				p++;
			}
			// 스택에 무언가 있다면
			else {
				//스택보다 연산자 우선순위가 높다면
				if (operator_priority(*p) > operator_priority(return_top())) {
					push(*p);
					p++;
				}
				//스택보다 연산자 우선순위가 같거나 낮다면
				else {
					*dest++ = pop();
					push(*p);
					p++;
				}
			}
		}
		//이상한 문자인 경우
		else {
			printf("\n연산하지 못하는 문자를 입력받았습니다.");
			return 0;
		}
	}
	// 스택에 남아있는거 전부 빼내고 널문자 추가
	while (!is_stack_empty()) {
		*dest++ = pop();
	}
	*dest = '\0';
	return 1;
}

int postfix(char* dest, char* src)

매개변수 char* dest = 비어있어도 됨. 함수가 끝나면 후위표기법으로 완성된 문자열이 들어감.

매개변수 char* src = 중위표기법 문자열이 들어감.

반환 = 1(정상적으로 실행 완료), 0(이상한 문자가 들어온 경우)

 

 

주의!

* 여러 번 정상작동이 되는지 확인했지만 (만든 게 저니까 믿을 수가 없습니다!)

  혹시 잘못된 점이 있다면 부디 댓글 부탁드리겠습니다. (꾸벅)

 

 

결과

int main()
{
	char src[100];
	char dest[100];

	printf("사칙연산을 입력하시오: ");
	scanf("%s", src);

	int result = postfix(dest, src);

	if (result) {
		printf("\n후위 표기법: ");
		printf("%s\n", dest);
	}
}

 

 

 

 

귀여운 그림은 낡은 창고님이 그리셨습니다.