BOJ 1918 : 후위 표기식

알고리즘 문제 전체 링크

삼성 C형 전체 링크

 

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

 

참고

- 스택

- 괄호 

- 후위 표기식2 (후위 표기식 연산하기)

- 중위 표기식 

 

 

중위 표기법(infix)으로 주어진 식을 후위 표기법(postfix)으로 바꿔보자.

아래의 규칙대로 구현하면 중위 표기식을 후위 표기식으로 바꿀 수 있다.

 

1. stack이 비어있거나 열린 괄호 "(" 는 stack에 넣는다.

2. 열린 괄호 "(" 다음의 연산자는 stack에 넣는다.

3. 현재 stack의 가장 위에 있는 연산자보다 우선순위가 큰 연산자는 넣는다. ( * = / > + = - )

4. 현재 stack의 가장 위에 있는 연산자보다 우선순위가 낮은 연산자가 들어오려고 한다면,

  스택이 비거나, 열린 괄호 "(" 가 나오거나 해당 우선순위가 더 커질 때까지 스택을 비우고, 연산자를 넣는다.

5. 닫힌 괄호 ")" 가 나오면  열린 괄호 "(" 가 나올 때까지 스택을 비운다. 이때, 여는 괄호 "(" 는 버린다.

6. 숫자는 그대로 출력(저장)한다.

7. 위 과정을 모두 마친 후, 남은 스택을 모두 비운다.

 

스택을 비우는 것은 그대로 출력하거나 특정 배열에 순서대로 저장하는 것을 의미한다.

---

구현

 

table 배열을 선언하여 알파벳, 괄호, 연산자를 쉽게 체크하도록 한다.

	for (int i = 'A'; i <= 'Z'; i++) table[i] = ALPHABET;

	table['('] = BRACKET;
	table[')'] = BRACKET;

	table['+'] = OPERATOR;
	table['-'] = OPERATOR;
	table['*'] = OPERATOR;
	table['/'] = OPERATOR;

 

연산자에 대해서도 우선순위를 저장한다. * / 가 + - 보다 크기만 하면 된다.

	priority['+'] = 10;
	priority['-'] = 10;
	priority['*'] = 11;
	priority['/'] = 11; // 더 높은 우선 순위 마킹

 

위의 규칙대로 구현한 코드는 아래와 같다.

그대로 출력해도 되지만 여기에서는 postfix 배열에 순서대로 저장하였다.

#include <stdio.h>

#define ALPHABET (1)
#define OPERATOR (2)
#define BRACKET (3)

char formula[110];
char operators[110];
char stack[110];
int sp;
char postfix[110];
int pcnt;

int main()
{
	scanf("%s", formula);

	char table[300] = { 0 };
	char priority[300] = { 0 };

	int len;
	for (len = 0; formula[len]; len++);

	for (int i = 'A'; i <= 'Z'; i++) table[i] = ALPHABET;

	table['('] = BRACKET;
	table[')'] = BRACKET;

	table['+'] = OPERATOR;
	table['-'] = OPERATOR;
	table['*'] = OPERATOR;
	table['/'] = OPERATOR;

	priority['+'] = 10;
	priority['-'] = 10;
	priority['*'] = 11;
	priority['/'] = 11; // 더 높은 우선 순위 마킹

	for (int i = 0; i < len; i++)
	{
		if (table[formula[i]] == OPERATOR)
		{
			// 1. stack이 비어있다면 stack에 넣는다.
			// 2. 열린 괄호 "(" 다음의 연산자는 stack에 넣는다.
			if (sp == 0 || stack[sp - 1] == '(') stack[sp++] = formula[i];
			else
			{
				// 3. 현재 stack의 가장 위에 있는 연산자보다 우선순위가 큰 연산자는 넣는다. ( * = / > + = - )
				if (priority[stack[sp - 1]] < priority[formula[i]]) stack[sp++] = formula[i];
				else //4. 현재 stack의 가장 위에 있는 연산자보다 우선순위가 낮은 연산자가 들어오려고 한다면,
				{    // 스택이 비거나, 열린 괄호 "(" 가 나오거나 해당 우선순위가 더 커질 때까지 스택을 비운다.		
					while (sp != 0
						&& stack[sp - 1] != '('
						&& priority[stack[sp - 1]] >= priority[formula[i]])
					{
						char ch = stack[--sp];
						if (table[ch] != BRACKET) postfix[pcnt++] = ch;
					}

					stack[sp++] = formula[i]; // 4. 그리고 현재 연산자를 넣는다.
				}
			}
		}
		else if (table[formula[i]] == BRACKET)
		{
			if (formula[i] == '(') stack[sp++] = formula[i]; // 1. 열린 괄호 "(" 는 stack에 넣는다.
			else 
			{ // 5. 닫힌 괄호 ")" 가 나오면  열린 괄호 "(" 가 나올 때까지 스택을 비운다. 
				while (stack[sp - 1] != '(') 
				{
					char ch = stack[--sp];
					if (table[ch] != BRACKET)  postfix[pcnt++] = ch; // 5. 이때, 여는 괄호 "(" 는 
				}

				--sp; // 5. 버린다.
			}

		}
		else // if (table[formula[i]] == ALPHABET)
			postfix[pcnt++] = formula[i]; // 6. 숫자는 그대로 출력(저장)한다..

	}

	// 7. 위 과정을 모두 마친 후, 남은 스택을 모두 비운다.
	while (sp) postfix[pcnt++] = stack[--sp]; 

	printf("%s\n", postfix);

	return 0;
}