긴자리 후위 표기법 구현하기

삼성 C형 전체 링크

 

참고

- 후위 표기식

- 중위 표기식

 

BOJ 1918 : 후위 표기식을 참고하면, 

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

 

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

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

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

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

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

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

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

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

 

아래와 같은 중위 표기식 formula가 존재할 때, 후위 표기식으로 나타내보자.

char formula[1100] = "123 - ( 456 - 789 - ( 321 - 654 + ( 987 * 12 - 34 - ( 56 * 78 + 65 ) * 43 * 21 - 1111 * ( 2222 * 3333 ) * 4444 ) ) ) ";

 

BOJ 1918 : 후위 표기식에서 string으로 표현된 숫자를 parsing하는 로직을 추가하면 된다.

#include <stdio.h>

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

typedef struct st
{
	char number[100];
	int length;
	char op;
	bool isNumber;
}NUMBER_INFO;

NUMBER_INFO stack[1100];
int sp;

NUMBER_INFO postfix[1100];
int pcnt;

void makePostfix(char formula[], NUMBER_INFO postfix[])
{
	sp = pcnt = 0;

	char lookup[256 + 1] = { 0 };
	char priority[256 + 1] = { 0 };

	for (int i = '0'; i <= '9'; i++) lookup[i] = NUMBER;

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

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

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

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

	int readNumber, numberLength;
	
	readNumber = numberLength = 0;
	for (int i = 0; i < formularLength; i++)
	{
		if (formula[i] == ' ')
		{
			if (readNumber == 1)
			{
				postfix[pcnt].isNumber = true;
				postfix[pcnt].number[numberLength] = 0;
				postfix[pcnt++].length = numberLength;

				readNumber = numberLength = 0;
			}

			continue;
		}

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

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

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

		}
		else // if (lookup[formula[i]] == NUMBER)
		{
			// 6. 숫자는 그대로 출력(저장)한다.
			readNumber = 1;
			postfix[pcnt].number[numberLength++] = formula[i];
		}
	}

	if (readNumber == 1)
	{
		postfix[pcnt].isNumber = true;
		postfix[pcnt].number[numberLength] = 0;
		postfix[pcnt++].length = numberLength;
	}

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

int main()
{
	char formula[1100] = "123 - ( 456 - 789 - ( 321 - 654 + ( 987 * 12 - 34 - ( 56 * 78 + 65 ) * 43 * 21 - 1111 * ( 2222 * 3333 ) * 4444 ) ) ) ";
	
	makePostfix(formula, postfix);
	
	for (int i = 0; i < pcnt; i++)
	{
		if (postfix[i].isNumber) printf("%s ", postfix[i].number);
		else printf("%c ", postfix[i].op);
	}
	putchar('\n');

	return 0;
}