자료구조_스택_후위표기식변환

중위표기식을 후위 표기식으로 변환하기

#include <stdio.h>
#include <stdlib.h>
#include <string.h> //식별자 strlen을 사용하기 위함

#define MAX_STACK_SIZE 10

//중위표기식을 후위표기식으로 바꾸기

typedef int element;
typedef struct {
	element data[MAX_STACK_SIZE];
	int top;
} StackType;

// 스택 초기화 함수
void init_stack(StackType* s) {
	s->top = -1;
}

// 공백 상태 검출 함수
int is_empty(StackType* s) {
	return (s->top == -1);
}
// 포화 상태 검출 함수
int is_full(StackType* s) {
	return (s->top == (MAX_STACK_SIZE - 1));
}
// 삽입함수
void push(StackType* s, element item) {
	if (is_full(s)) {
		fprintf(stderr, "스택 포화 에러\n");
		return;
	}
	else s->data[++(s->top)] = item; //s->top에 먼저 1을 증가 후 사용
}
// 삭제함수
element pop(StackType* s) {
	if (is_empty(s)) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else return s->data[(s->top)--]; //s->top을 먼저 사용하고 1을 감소
}
//peek stack의 top에 있는 연산자를 return
element peek(StackType* s) {
	if (is_empty(s)) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else return s->data[(s->top)];
}
//연산자의 우선순위를 결정하기위한 함수
int prec(char op) {
	switch (op)
	{
	case '(': case ')': return 0;
	case '+': case '-': return 1;
	case '*': case '/': return 2;
	}
	return -1;
}
// 중위표기식을 후위표기식으로 변환하는 함수
void infix_to_postfix(const char exp[]) {
	char ch, top_op; //ch: 내가 push하려고 하는 연산자, top_op: 스택에서 꺼낸 연산자
	int len = strlen(exp);

	StackType s;
	init_stack(&s);

	for (int i = 0; i < len; i++) {
		ch = exp[i]; //내가 push하려고하는 연산자
		switch (ch)
		{
			case '+': case '-': case '*': case '/':
				//우선순위를 판단해서 push
				while (!is_empty(&s) && prec(ch) <=prec(peek(&s))) {
					printf("%c", pop(&s));
				}
				push(&s, ch);
				break;
			case '(':
				push(&s, ch);
				break;
			case ')':
				top_op = pop(&s);
				while (top_op != '(') {
					printf("%c", top_op);
					top_op = pop(&s);
				}
				break;
			default: //피연산자
				printf("%c", ch);
				break;
		}
	} // end for
	while (!is_empty(&s)) {
		printf("%c", pop(&s));
	}
}
int main() {
	const char* s = "(2+3)*4+9"; //문자열을 변경할 필요가 없기 때문에 const 사용
	infix_to_postfix(s);
}

활용된 변수

ch : 내가 push하려고하는 연산자를 저장하는 변수
top_op : 스택에서 꺼낸 연산자를 저장하는 변수

printf와 fprintf의 차이

printf
표준 출력(stdout)에 출력하는 함수

즉, 우리가 일반적으로 화면에서 보는 출력은 printf를 통해 이루어진다.

fprintf
특정한 출력 스트림을 지정할 수 있는 함수

즉, 출력할 대상을 지정할 수 있고, stderr, stdout, 파일 등 여러 곳에 출력할 수 있다.

stderr
표준 에러 스트림(Standard Error Stream)

일반적으로 printf는 stdout(표준 출력)에 출력되지만,
fprintf(stderr, "에러 메시지")처럼 사용하면 에러 메시지를 stderr(표준 에러)로 출력할 수 있다.

전위 증가 vs 후위 증가

s->data[++(s->top)] = item; 이 코드의 의미

스택에 새로운 데이터를 푸시(push) 하는 역할

++(s->top)은 전위 증가 연산자(prefix increment)로,
top 값을 먼저 증가시킨 후 사용

새 데이터는 data[top+1] 위치에 저장

전위 증가(++s->top) vs 후위 증가(s->top++) 차이

++s->top : top을 먼저 증가시키고 사용
s->top++ : top을 먼저 사용하고 증가

const char* s의 의미

s : 문자열을 가리키는 포인터

"(2+3)*4+9"은 문자열 리터럴이라서
변경할 수 없는 메모리 영역(읽기 전용 메모리)에 저장

const 키워드를 붙이면,
s가 가리키는 문자열을 변경하지 못하게 보호하는 역할

이 코드에서 문자열을 변경할 필요가 없기 때문에 사용