c언어 1918번 후위 표기식 (백준)

#include <stdio.h>
#define M 100 

typedef struct Stack { //stack을 배열과 구조체를 이용하여 구현했다.
	char arr[M];
	int cnt;
}Stack;

void init(Stack *s) {
	s->cnt = 0;
	return;
}

int empty(Stack *s) {
	return s->cnt == 0;
}

void push(Stack *s, char data) {
	s->arr[s->cnt] = data;
	s->cnt++;
	return;
}

char pop(Stack *s) {
	if(empty(s)) printf("ERROR\n"); 
	s->cnt--;
	return s->arr[s->cnt];
}

char peak(Stack *s) { //스택의 가장 마지막에 push 된 것을 반환만 해준다 (stack에서 제거하지는 않는다)
	return s->arr[s->cnt - 1];
}

int high(char s) {
	if(s == '+' || s=='-') return 1;
	else if(s == '*' || s=='/') return 2;
	return 0;
}

int main(void) {
	char s[100] = {};
	scanf("%s", s);
	
	Stack stack; //스택 생성
	init(&stack); //스택 초기화
	
	int i = 0;
	while(s[i] != '\0') { 
		if(s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/' || s[i] == '(' || s[i] == ')') {
			if(empty(&stack)) push(&stack, s[i]); //스택에 아무것도 없는 경우
			else {
				if(s[i] == '(') push(&stack, s[i]);  //( 인 경우
				else if(s[i] == ')') { // ) 인 경우
					while(1) {
						if(peak(&stack) == '(') { //(가 stack에서 나올때까지 pop
							pop(&stack); //(도 pop 한다.
							break;
						}
						printf("%c", pop(&stack));
					}	
				}
				else if(high(s[i]) > high(peak(&stack))) push(&stack, s[i]); //우선순위가 스택의 마지막에 들어온것보다 높은경우
				else { //스택에 마지막에 들어온 것보다 우선순위가 낮거나 같은 경우
					while(1) {
						printf("%c", pop(&stack)); //스택에 있는 것을 먼저 하나씩 pop하여 출력한다.
						if(high(s[i]) > high(peak(&stack)) || !stack.cnt) break;
                        //만약 자신보다 우선순위가 낮거나 스택에 더이상 아무것도 없으면 반복문을 멈춘다.
					}
					push(&stack, s[i]); //자신을 stack에 push 한다.
				}
			}
		} else printf("%c", s[i]); //문자열은 바로 출력 
		i++;
	}
	
	while(stack.cnt) { //stack에 남은 것들을 다 pop하여 출력한다.
		printf("%c", pop(&stack));
	}
}

 

풀이

 

0. 중위 표기식에서 후위 표기식으로의 변환

A+B*C-D/E  -->  ABC*+DE/-

 

위를 보면 중위 표기식과 후위 표기식에서의 문자의 순서는 같음을 알 수 있으며,

연산자의 순서가 다름을 알 수 있는데

후위 표기식에서는 연산순서가 빠를수록 문자의 오른쪽에 가까이 위치한다.

 

(ex ABC*+ 에선 *이 먼저 실행되며 그다음 오른쪽에 있는  + 가 실행된다)

 

즉 연산자들을 문자들을 출력한 다음 출력하기 위해선 특정한 곳에 저장해 두었다가 다시 빼내야 하며,

A+B*C 처럼 +을 먼저 저장했으나 *보다 나중에 나올수 있는 곳, 이런 곳은 스택이나 덱 등이 있다.

 

여기서 나는 스택을 사용하였다. (덱으로도 가능한지는 모르겠다 : 가능하다 해도 스택으로 되는 이상 pop하는 곳을 한 쪽만 쓸 것 같다.)

 

또한 괄호가 있는 식도 있다.

 

A*(B+C*D) 이와 같은 경우에는

A*(BCD*+) 괄호 내에서 후위 표기식으로 바꿔준다음

ABCD*+* 괄호를 제거하면 된다.

 

1. 스택 구현

구조체와 배열을 이용하여 구현했으며

스택 관련 함수로는

void init : 초기화

int empty : 비어있으면 참

void push : 넣기

int pop : 가장 늦게 들어온 것을 빼면서 반환

int peak : 가장 늦게 들어온 것을 반환만 함

 을 만들었다.

 

2. 연산자 우선 순위

+ - 보다 * / 의 우선순위가 높다.

그러기에

A+B*C => ABC*+

A*B+C => AB*C+

A*B*C => AB*C*

 

먼저 A+B*C => ABC*+ 에서 스택을 이용해 보자

후위 표기식을 위해 연산자 +을 스택에 넣는다. 

그 다음 연산자 *은 +보다 우선순위가 높으니 스택에 넣어준다

이러면 스택을 꺼낼 때 *가 먼저 나오게 되니 후의 표기식을 만들 수 있다

-> 스택에 있는 연산자보다 비교하고 있는 연산자의 우선순위가 더 높다면 스택에 넣어준다.

 

그 다음 A*B+C => AB+C* 에서 스택을 이용해 보자

후의 표기식을 위해 연산자 *을 스택에 넣는다.

그 다음 연산자 +을 스택에 넣을지를 보아야 하는데

만약 +을 스택에 넣게 된다면  나중에 스택에서 꺼낼 때 우선순위가 낮은 +가 더 문자와 가까이 있게 된다

이는 불가하므로, 스택에 가장 마지막에 들어온 * 을 꺼내서 출력한다. 그 다음 연산자 +을 스택에 넣어준다

그 후 남은 문자들이 출력된 후 스택에서 +을 꺼내서 출력하면 된다.

-> 스택에 있는 연산자보다 비교하고 있는 연산자의 우선순위가 더 낮다면 스택에 있는 연산자 1개를 꺼내 준다음 비교하고 있는 연산자를 스택에다 넣어준다.

 

마지막으로 A*B*C =>AB*C*에서 스택을 이용해 보자

*을 스택에 넣고

*는 스택에 있는 *와 같으니 스택에 넣지 않고 출력해도 위의 후의 표기식을 만들 수 있다 (물론 나는 같은 연산자지만, 스택에 있는 것을 빼고, 비교하던 걸 넣었다) -> 연산자의 순위가 같아도, 스택에있는 것을 뺀 다음, 연산자를 스택에 넣어줘도 된다.

그다음 stack에 남아있는 것을 모두 출력 했다

 

고로

스택에 아무것도 없으면 연산자를 push

스택의 최근에 들어온 것과 다른 연산자를 비교하여

스택에 있는 것과 같거나 더 낮다면 (순위가), 스택에 있는 것을 제하고, 비교하던걸 스택에 넣는다. (스택에서 한개를 꺼낸후 다음 것과 또 비교해야 한다, 이 순환이 끝날려면, 스택보다 더 크거나, 스택에 더이상 아무런 요소가 없을 때 이다)

더 크다면 그냥 스택에 넣어준다.

 

3. 괄호

( )의 경우,. 계산할 때도 ()내부의 연산을 끝낸다음 괄호를 제거하기에

후위 표기식으로 바꿀때도, ()내부에서 후위 표기식으로 만든다음 괄호를 제거하면 된다.

후위 표기식을 만드는 방법은 2.와 같으나 추가할 점은

'('을 stack에 넣은 후

')'을 비교할 때 stack에서 (가 나올때 까지 stack에서 다 꺼내면 된다.

 

예로서 (A*B+C) 같은 경우

'(' 을 stack에 넣고

'( ' 와 +을 비교해야한다. 후위 표기식에선 괄호를 사용하지 않으므로, + - 보다 더 낮은 연산 순위를 갖는다고 여기도록 만들었다. 만약 순위를 +와 같게 만들면 A*B(C+) 이런 괴상한 것이 생긴다. 괄호를 생략해도 A*BC+ 원래 정확한 표현인 AB*C+하고 많이 달라진다.)

 

4. 코딩

//스택과 스택함수 구현

//문자열로 입력을 받음

//문자는 바로 출력
    //연산자는
    //스택이 비어있는 경우엔, 스택에 push
    //스택이 비어있지 않은 경우엔
    //     만약 '(' 라면 스택에 push
    //     만약 ')' 라면 스택에서 '('가 나올 때 까지 pop한 다음 출력 '('도 스택에서 꺼내나 출력은 하지 않는다.
    //     만약 '(', ')'  도 아니라면 스택에서 가장 마지막에 들어온 연산자와 연산 순위를 비교
    //     스택에 있는 것보다 연산 순위가 높으면 -> push
    //     스택에 있는 것보다 연산 순위가 같거나 낮다면 -> 스택에 있는 모든것을 하나씩 pop 하고 다시 우선순위 비교 (자신이 순위가 더 높거나, 스택이 비어질 경우 반복을 해제한다) -> 자신의 것을 넣는다.