Boj 1918) 후위 표기식

문제

백준 1918

설명

방법 떠올리는거 자체는 맨날 헷갈림

우선 변수는 순서가 바뀌지 않음

• 바뀌는건 연산자의 순서 뿐임
• 언제 연산자의 순서가 바뀔까 생각하면 아래 두 경우 뿐임.
  1. 연산자 우선순위
  2. 괄호

연산자 순서가 바뀌지 않는 경우에는

• A-B+C+D => AB-C+D+
• 연산자들이 한칸 건너서 들어가는 걸 확인가능함.
• 그러니까 한번 저장했다가 다음 연산자 자리에서 꺼내면 됨

연산자 우선순위만 적용되는 경우

• A+B*C+D*E => ABC*+DE*+
• 이전의 연산자 가 지금의 연산자보다 우선되는 경우 결합법칙을 수행해야함 ( BC*)
  • stack.top() < cur_op 을 의미함
  • 왜 역방향은 상관없냐면 무조건 -> 방향으로만 계산할 것이기 때문
• 이때 연산자는 앞에서 봤듯 한칸 건너서 적용이 됨.
  • 그러니 우선 값을 저장하고
  • 다음 연산자의 위치에서 저장된 연산자를 역순으로 꺼내주면 됨 => Stack
  • 이는 곧 stack.top() > cur_op 일때 적용이 됨.
• 연산자의 우선순위가 같은경우 똑같이 이전의 연산자 하나만 주면 됨

괄호까지 적용되는 경우

• (A + (B * (C + D))) => ABCD+*+
• (((A+B)*C)+D) => AB+C*D+
• 괄호 이전의 연산자는 괄호 묶음에 대해서 연산을 하게 됨.
• 즉 괄호 이전의 연산자는 괄호가 끝날 때 까지 쓸 수 없음
• 그러므로 괄호 시작시 괄호를 스택에 저장하고
• 괄호가 끝날 시, 저장된 괄호가 나올때까지 Stack 에 있는 operand 를 꺼내면 됨.

시간복잡도

O(\(N\))

코드

inline bool IsOp(char in)
{
	return in == '+' || in == '-' || in == '*' || in == '/';
}

inline bool NotLessPrior(char top, char cur)
{
	return (top == '*' || top == '/') || (cur == '+' || cur == '-');
}

int main()
{
	char c, op; 
	stack<char> st; st.push('\0');
	while (1)
	{
		cin >> c;
		if (cin.eof()) break;

		if (c >= 'A' && c <= 'Z') cout << c;
		else if (c == '(') st.push(c);
		else if (c == ')') {
			while (IsOp(st.top())) {
				cout << st.top();
				st.pop();
			}
			st.pop();
		}
		else { // operand
			while (NotLessPrior(st.top(), c) && IsOp(st.top()))
			{
				cout << st.top();
				st.pop();
			}
			st.push(c);		
		}
	}
	
	while (st.top() != '\0')
	{
		if(IsOp(st.top()))
			cout << st.top();
		st.pop();
	}
}

아래 코드는 if 문을 압축한 위 코드를 이해하기 쉽게 펼친 것임.

else {   // operand case
	if ((st.top() == '+' || st.top() == '-') && (c == '*' || c == '/'));
	else if((st.top() == '*' || st.top() == '/') && (c == '+' || c == '-'))
	{
		while (IsOp(st.top()))
		{
			cout << st.top();
			st.pop();
		}
	}
	else if (IsOp(st.top()))
	{
		cout << st.top();
		st.pop();
	}
	st.push(c);
}