[C] 중위수식을 후위수식으로 변환하는 문제에서 단항연산자 처리

1. 문제상황

 

백준 1918번 후위표기식 문제 https://www.acmicpc.net/problem/1918 ( 중위수식이 주어지면 후위수식으로 변환하는 문제 ) 를 풀었는데, 문제에서 고려하지 않아도 되는 케이스였던 " -A+B와 같이 -가 가장 앞에 오는 경우 " 를 해결하고 싶었다. 

 

문제에서 생략된 케이스는 단항연산자 였는데,

단항연산자는 피연산자 (연산에 필요한 값)이 하나인 연산자를 말한다.

예를 들어, +3 , 3++ , !3 과 같은 경우에서의 연산자가 단항 연산자이다. 이중에서도 (-3), (+7)과 같이 부호를 나타내는 케이스를 풀 수 있게 만들고자 했다.

 

이와 반대되는 개념은 이항연산자로, 피연산자가 2개인 연산자를 말한다.

2+3, 4-7, 10*5와 같이 일반적으로 사용하는 연산자는 대부분 이항 연산자이다. 

C언어를 공부할때 종종 배우는 삼항연산자는 피연산자가 3개인 경우다. (A>5) ? B : C 와 같이 피연산자 3개를 요구한다.

 

 

문제를 해결하기 위해, 단항연산자로 쓰이는 +, -의 우선순위를 더 높이려고 했다. 예를 들어, A+-B는 A+(-B)이므로, 여기에서는 -가 더 우선순위가 높다. 하지만 기존의 이항연산자로 쓰인 +,-와 단항연산자로 쓰인 +,-는 같은 기호를 사용하기 때문에 그 둘을 구분해 줄 필요가 있었다.

 

단항연산자로 쓰이는 경우는 크게 2가지다.

 

1. 식의 맨 앞에 나오는 경우 : -A+B-C

2. 식의 중간에 나오는 경우 : A+-B

 

1의 경우는 간단하게, +,-가 식의 맨 앞에 나오는 경우는 단항연산자로 처리했다. 두번째인 식의 중간에 나오는 경우가 조금 복잡한데, 해당 +,- 앞에 어떤 기호가 나오는지를 살펴봐야 한다. A+-B와 같이 앞에 다른 기호가 나오는 경우는 단항연산자가 된다. 단, 이경우에는 (A+B)+C와 같이 앞의 기호가 ')'인 경우는 제외해야 한다. A+B와 같이 앞에 일반 문자가 나오는 경우는 이항연산자로 쓰이는 것이므로 당연히 제외해야 한다. 

 

따라서, 해당 연산자가 단항연산자인 경우, 그 연산자의 우선순위를 가장 높게 만드는 식으로 문제를 해결하려고 했다.

하지만, 정작 원하는 결과물이 나오지 않았다. 예를들어, -A+-B+-C를 넣어주는 경우 결과물은 A-B-+C-+가 나와야하지만 전혀 다른 값이 나왔다.

 

<소스코드>

#pragma warning(disable:4996)
#include <stdio.h>

typedef struct stack {
	char s[101];
	int t;
	int n;
}stack;

void push(stack* stack, char c);
char pop(stack* stack);
int operandTest(char s, char beforeoperend);
void convert(stack* stack, char* str);

int main() {

	stack stack1;
	stack1.n = 100;
	stack1.t = -1;
	
	char str[101] = { 0 };
	scanf("%s", str);
	convert(&stack1, str);

	return 0;
}

void push(stack* stack, char c) {
	if (stack->t != stack->n - 1) {
		stack->t = stack->t + 1;
		stack->s[stack->t] = c;
	}
}

char pop(stack* stack) {
	if (stack->t != -1) {
		stack->t = stack->t - 1;
		return stack->s[stack->t + 1];
	}
}


int operandTest(char s, char beforeoperend) {
	if (s == '(' || s == ')')
		return 1;
	else if (s == '+' || s == '-') {
		if (beforeoperend == ')' || ('A' <= beforeoperend && beforeoperend <= 'Z'))
			return 2;
		else
			return 4;
	}
	else if (s == '*' || s == '/')
		return 3;
	else
		return -1;
}

void convert(stack* stack, char* str) {
	int i = 0;
	while (str[i] != '\0') {
		char beforeoperend = '?';
		if (i > 0) {
			beforeoperend = str[i - 1];
		}

		if (operandTest(str[i], beforeoperend) == -1) {
			printf("%c", str[i]);
		}
		else if (str[i] == '(') {
			push(stack, str[i]);
		}
		else if (str[i] == ')') {
			while (stack->s[stack->t] != '(') {
				printf("%c", pop(stack));
			}
			pop(stack);
		}
		else {
			while (stack->t != -1 && operandTest(str[i], beforeoperend) <= operandTest(stack->s[stack->t], beforeoperend)) {
				printf("%c", pop(stack));
			}
			push(stack, str[i]);
		}
		i++;
	}
	while (stack->t != -1) {
		printf("%c", pop(stack));
	}
	printf("\n");
}

 

<결과물>

잘못된 값이 출력됨

2. 문제원인

 

원인은 간단했는데, 해당 연산자를 스택에 push할때는 문제가 없었지만 이미 저장된 연산자를 pop시키기 위해 비교하는 과정에서 문제가 생겼다.

 

'해당 연산자 바로 앞의 값'을 불러와서 우선순위를 판별하는 방식이 여기서 문제가 되었다. stack에 저장되어버리는 순간 stack에 저장된 +,-는 단항연산자인지 다항연산자인지 알 수 없게 되어버린 것이다.

 

3. 문제해결

 

연산자의 우선순위를 판단하기 전에, 그 연산자가 단항연산자인지 미리 판단하여 단항연산자이면 다른 기호로 바꿔버리는 방법으로 해결했다. 그렇게 하면 stack안에 들어가도 단항연산자라는 것을 알 수 있게 된다. 출력시에만 원래 기호로 바꾸어 출력하면 된다.

 

어떤 조건으로 판별된 값을 여러번 사용하는 경우, 판별된 내용을 저장하는 방식으로 문제를 해결하는 식으로 코딩하는 방법은 앞으로도 사용해 봐야겠다.

 

<소스코드>

#pragma warning(disable:4996)
#include <stdio.h>

typedef struct stack {
	char s[101];
	int t;
	int n;
}stack;

void push(stack* stack, char c);
char pop(stack* stack);
int operandTest(char s);
void convert(stack* stack, char* str);

int main() {

	stack stack1;
	stack1.n = 100;
	stack1.t = -1;
	
	char str[101] = { 0 };
	scanf("%s", str);
	convert(&stack1, str);

	return 0;
}

void push(stack* stack, char c) {
	if (stack->t != stack->n - 1) {
		stack->t = stack->t + 1;
		stack->s[stack->t] = c;
	}
}

char pop(stack* stack) {
	if (stack->t != -1) {
		stack->t = stack->t - 1;
		return stack->s[stack->t + 1];
	}
}


int operandTest(char s) {
	if (s == '(' || s == ')')
		return 1;
	else if (s == '+' || s == '-') {
		return 2;
	}
	else if (s == '*' || s == '/')
		return 3;
	else if (s == 'p' || s == 'm')
		return 4;
	else
		return -1;
}

void convert(stack* stack, char* str) {
	int i = 0;
	while (str[i] != '\0') {

		// 단항연산자 +,-는 p, m으로 변환 
		if (str[i] == '+' || str[i] == '-') {
			if (i == 0) {
				str[i] = (str[i] == '+') ? 'p' : 'm';
			}
			else if (str[i - 1] != ')' && !('A' <= str[i - 1] && str[i - 1] <= 'Z')) {
				str[i] = (str[i] == '+') ? 'p' : 'm';
			}
		}

		if (operandTest(str[i]) == -1) {
			printf("%c", str[i]);
		}
		else if (str[i] == '(') {
			push(stack, str[i]);
		}
		else if (str[i] == ')') {
			while (stack->s[stack->t] != '(') {
				char tmp = pop(stack);
				if (tmp == 'p')
					tmp = '+';
				else if (tmp == 'm')
					tmp = '-';
				printf("%c", tmp);
			}
			pop(stack);
		}
		else {
			while (stack->t != -1 && operandTest(str[i]) <= operandTest(stack->s[stack->t])) {
				char tmp = pop(stack);
				if (tmp == 'p')
					tmp = '+';
				else if (tmp == 'm')
					tmp = '-';
				printf("%c", tmp);
			}
			push(stack, str[i]);
		}
		i++;
	}
	while (stack->t != -1) {
		char tmp = pop(stack);
		if (tmp == 'p')
			tmp = '+';
		else if (tmp == 'm')
			tmp = '-';
		printf("%c", tmp);
	}
	printf("\n");
}

<결과물>

정상적으로 출력