[백준] 1918번 - 후위 표기식 (C언어) [Gold2]

input1	output1	input1	output1
A*(B+C)	ABC+*	A+B*C-D/E	ABC*+DE/-

해당 문제는 자료구조 중에서 스택을 이용하여 해결가능 한 문제이다. 문제 해결 과정은 아래와 같다.

1. 피연산자를 만나면 바로 출력한다.
2. 연산자가 들어오면 자신보다 우선순위가 높거나 같은것들을 제외하고 스택에 넣는다.
3. 여는 괄호 '('를 만나면 스택에 넣는다.
4. 닫힘 괄호 ')'를 만나면 여는 괄호 '('를 만날때 까지 스택에서 꺼내 출력한다. 

 

우선순위 처리는 다음과 같다.

• 현재 처리 중인 연산자의 우선순위가 스택에 있는 우선순위보다 낮은 경우
  • 스택에 있는 연산자를 꺼내 출력하고 처리 중인 연산자는 스택에 넣는다.
• 현재 처리 중인 연산자의 우선순위가 스택에 있는 우선순위보다 큰 경우
  • 처리 중인 연산자를 스택에 넣는다.
• 현재 처리 중인 연산자의 우선순위가 스택에 있는 우선순위보다 같은 경우
  • 스택에 있는 연산자를 꺼내 출력하고 처리 중인 연산자는 스택에 넣는다.

 

전체 소스 코드는 아래와 같다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
#pragma warning(disable:4996)
#define MAX_TERM 100
typedef struct {
	int data[MAX_TERM];
	int top;
}StackType;
void init_stack(StackType* s) {
	s->top = -1;
}
int is_full(StackType* s) {
	if (s->top > MAX_TERM) {
		return 1;
	}
	else
		return 0;
}

int is_empty(StackType* s) {
	if (s->top == -1) {
		return 1;
	}
	else
		return 0;
}

void push(StackType* s, int value) {
	if (is_full(s)) {
		fprintf(stderr, "Push Error\n");
		exit(1);
	}
	else {
		s->top++;
		s->data[s->top] = value;
	}
}

int pop(StackType* s) {
	if (is_empty(s)) {
		fprintf(stderr, "Pop Error\n");
		exit(1);
	}
	return s->data[(s->top)--];
}

int peek(StackType* s) { // 데이터가 무슨값을 가지고 있는지만 확인한다.
	if (is_empty(s)) {
		fprintf(stderr, "Peek Error\n");
		exit(1);
	}
	return s->data[(s->top)];
}
int prec(char op) { // 연산자 우선순위 반환
	// 우선순위 0이 가장 낮고 2가 가장 높다.
	switch (op)
	{
	case '(':
	case ')':
		return 0;
	case '+':
	case '-':
		return 1;
	case '*':
	case '/':
	case '%':
		return 2;
	}
	return -1;
}

void infix_to_postfix(char exp[]) {
	StackType s;
	char ch, top_op;
	int len = strlen(exp);
	init_stack(&s); // 스택 초기화 까먹지 말것!
	for (int i = 0; i < len; i++) {
		ch = exp[i];
		switch (ch) {
		case '+':
		case '-':
		case '*':
		case '/':
		case '%':
			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); // 괄호 안에있는 연산자 pop
			while (top_op != '(') { // 열린 괄호를 만나면 종료
				printf("%c", top_op);
				top_op = pop(&s);
			}
			break;
		default: // 피연산자

			printf("%c", ch);

			break;

		} // end of switch

	} // end of for
	// 스택에 남은 연산자 처리
	while (!is_empty(&s))
		printf("%c", pop(&s));
}

int main() {
	char buf[1024] = { 0 , };
	
	gets(buf);

	infix_to_postfix(buf);

	return 0;
}

 

[1918번]

https://www.acmicpc.net/problem/1918

1918번: 후위 표기식

 

[github]

https://github.com/MinWook6457

MinWook6457 - Overview