[PS] 후위 표기식 / C++ (백준 1918번)

 

stack, vector를 사용해서 문제를 적절히 구현하면 되는 자료구조 문제

(((A+B)))같은 식은 안 나올 줄 알고 처리를 안 해놨다가 런타임 에러 받자마자 직감하고 처리해 줬다.

1. 중위 표기식에 괄호 씌우기
   • *, / 먼저 찾아서 수식의 위치를 make_pen 함수에 매개변수로 보낸다.
   • +, - 도 찾아서 똑같이 make_pen 함수를 돌려준다.
   • make_pen()은 찾은 수식의 위치를 매개변수로 받아 좌, 우로 식을 찾는다. 식은 알파벳 하나 또는 괄호로 이루어진 식으로 좌, 우의 식에 양 옆에 괄호가 이미 있다면 return, 한쪽이라도 괄호가 없다면 괄호를 삽입한다.
2. 수식과 대응되는 괄호 찾아 후위 표기식으로 만들기
   • '('는 st_op 스택에 위치를 저장
   • 알파벳은 pass
   • 수식은 st_cal에 마찬가지로 위치 저장
   • ')'가 나오면 st_cal.top()에 저장된 수식의 위치가 괄호 안에 있는지 확인 ( '(A+B+(C))'같은 식도 나올 수 있음 )
     • 괄호 안에 수식이 없는 ')' 삭제, '(' 삭제 (꼭 뒤에서부터 순서로 해야 함. >> erase 하면 위치가 바뀌기 때문)
       • st_op.pop()
     • 수식이 있다면 ')' 위치에 수식 삽입, 수식 삭제, '(' 삭제 (꼭 뒤에서부터 순서로 해야함. >> erase하면 위치가 바뀌기 때문)
       • st_op.pop()
       • st_cal.pop()
     • i값 조정

 

#include<iostream>
#include<algorithm>
#include<stack>
#include<vector>
#include<cstring>
using namespace std;

char input[101];
vector<char> vec;

int make_pen(int mid) {
	int left, right, l_op = 0, r_op = 0;
	for (left = mid; left >= 0; left--) {
		if (vec[left] >= 'A' && vec[left] <= 'Z') {
			if (l_op == 0)break;
		}
		else if (vec[left] == ')')l_op--;
		else if (vec[left] == '(') {
			l_op++;
			if (l_op == 0)break;
		}
	}
	for (right = mid; right < vec.size(); right++) {
		if (vec[right] >= 'A' && vec[right] <= 'Z') {
			if (r_op == 0)break;
		}
		else if (vec[right] == '(')r_op--;
		else if (vec[right] == ')') {
			r_op++;
			if (r_op == 0)break;
		}
	}
	if ((left != 0 && vec[left - 1] == '(') && (right != vec.size() - 1 && vec[right + 1] == ')')) {
		return 0;
	}
	else {
		vec.insert(vec.begin() + right + 1, ')');
		vec.insert(vec.begin() + left, '(');
		return 1;
	}
}

int main()
{
	scanf("%s", input);
	for (int i = 0; i < strlen(input); i++) {
		vec.push_back(input[i]);
	}

	for (int i = 0; i < vec.size(); i++) {
		if (vec[i] == '*' || vec[i] == '/') {
			make_pen(i);
		}
	}
	for (int i = 0; i < vec.size(); i++) {
		if (vec[i] == '+' || vec[i] == '-') {
			make_pen(i);
		}
	}
	int i = 0;
	stack<int> st_op, st_cal;
	while (1) {
		if (i == vec.size())break;
		if (vec[i] == '(') {
			st_op.push(i);
			i++;
			continue;
		}
		else if (vec[i] == ')') {
			if (st_cal.size() == 0 || st_cal.top() < st_op.top()) {
				vec.erase(vec.begin() + i);
				vec.erase(vec.begin() + st_op.top());
				st_op.pop();
				i--;
				continue;
			}
			vec[i] = vec[st_cal.top()];
			vec.erase(vec.begin() + st_cal.top());
			vec.erase(vec.begin() + st_op.top());
		}
		else if (vec[i] < 'A') {
			st_cal.push(i);
			i++;
			continue;
		}
		else {
			i++;
			continue;
		}
		i -= 2;
		st_cal.pop();
		st_op.pop();
		i++;
	}
	for (int i = 0; i < vec.size(); i++)printf("%c", vec[i]);
	return 0;
}