백준 1918번 후위 표기식

🔒[문제 url]

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

🔑알고리즘

괄호와 연산자에 따른 연산 우선순위를 놓치는 경우없이 따지며,
STACK을 이용해 식을 순회하며 알맞은 때에 출력해야한다.

• 연산자를 만난 경우
  • stack empty의 경우, 무조건 push한다.
  • stack top이 여는 괄호인 경우, 무조건 push한다.
  • *, / 일 때 stack top이 +, -인 경우, 우선순위를 고려하여 무조건 push한다.
  • 이외의 경우, 아래의 세 조건중 하나를 충족할때까지 출력과 pop을 반복한 후 연산자를 push한다.
    • stack empty
    • 여는 괄호를 만난 경우
    • 연산자 우선순위가 앞설 경우
      
      
• 피연산자 혹은 괄호를 만난 경우
  - 피연산자(대문자 알파벳)은 무조건 출력한다.
  - 여는 괄호 '('를 만난 경우, stack에 무조건 push 한다.
  - 닫는 괄호 ')' 를 만난 경우, 여는 괄호를 만날 때까지 stack의 연산자를 출력하고 pop한다.
  
  식을 순회한 후, stack에 남은 모든 연산자를 pop한다.

🐾부분 코드

// 연산자 우선순위 구별
bool isOp1(char c)
{
	if (c == '*' || c == '/') return true;
	else return false;
}
bool isOp2(char c)
{
	if (c == '+' || c == '-') return true;
	else return false;
}

<연산자 판별 함수>
연산자 간의 우선순위를 따지기 위해, * / 과 + - 를 따로 만들어준다.
연산자가 맞을 경우 true를 반환한다.

/* 연산자 만난 경우 */
if (isOp1(ex) || isOp2(ex))
{

	// 스택이 빈 경우
	if (op.empty()) op.push(ex);
	// top이 ( 인 경우 stack push
	else if (op.top() == '(') op.push(ex);
	// top의 우선순위가 낮은 경우 push
	else if (isOp1(ex) && isOp2(op.top())) op.push(ex);
	// 나머지는 조건 따지며 출력.pop 반복후 push
	else
    {
    	while (true)
    	{
    		// stack empty or ( 만나면 종료
    		if (op.empty() || op.top() == '(') break;
    		// 연산자 우선순위 따지기
    		if (isOp1(ex) && (!op.empty() && isOp2(op.top()))) break;

			cout << op.top();
			op.pop();
       	 }
         op.push(ex); // 연산자 push
     }
}

<연산자 만난 경우>
위에서 설명한 알고리즘에 따라 구현해준다.
else문에서는 무한루프를 돌다가 언급한 세가지 조건중 하나를 충족할 때까지 출력과 pop을 반복한다.

/* 피연산자 or 괄호 만난 경우 */
else
{
	// 피연산자 만나면 출력
    if (ex >= 'A' && ex <= 'Z') cout << ex;
    // 여는 괄호 ( 만나면 stack push
    else if (ex == '(') op.push(ex);

	// 닫는 괄호 ) 만나면 ( 만날 때까지 출력 pop
    else if (ex == ')')
    {
    	while (op.top() != '(')
        {
        	cout << op.top();
            op.pop();
        }
        op.pop(); // ( pop
    }
}

<피연산자 or 괄호 만난 경우>
마찬가지로 위에서 언급한 알고리즘에 따라 구현한다.

// 남은 연산자 출력
while (!op.empty())
{
	cout << op.top();
	op.pop();
}

<남은 연산자 출력>

🪄전체 코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <stdio.h>
#include <ctime>
#include <memory.h> // memset
#include <numeric>
#include <stack>
#include <sstream>
using namespace std;
/* –2,147,483,648 ~ 2,147,483,647 */

string expression;
stack<char> op;

void INPUT()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> expression;
}

// 연산자 우선순위 구별
bool isOp1(char c)
{
	if (c == '*' || c == '/') return true;
	else return false;
}
bool isOp2(char c)
{
	if (c == '+' || c == '-') return true;
	else return false;
}

void SOLVE()
{
	for (int i = 0; i < expression.length(); i++)
	{
		char ex = expression[i];

		/* 연산자 만난 경우 */
		if (isOp1(ex) || isOp2(ex))
		{
			// 스택이 빈 경우
			if (op.empty()) op.push(ex);
			// top이 ( 인 경우 stack push
			else if (op.top() == '(') op.push(ex);
			// top의 우선순위가 낮은 경우 push
			else if (isOp1(ex) && isOp2(op.top())) op.push(ex);
			// 나머지는 조건 따지며 출력.pop 반복후 push
			else
			{
				while (true)
				{
					// stack empty or ( 만나면 종료
					if (op.empty() || op.top() == '(') break;
					// 연산자 우선순위 따지기
					if (isOp1(ex) && (!op.empty() && isOp2(op.top()))) break;

					cout << op.top();
					op.pop();
				}
				op.push(ex);
			}
		}

		/* 피연산자 or 괄호 만난 경우 */
		else
		{
			// 피연산자 만나면 출력
			if (ex >= 'A' && ex <= 'Z') cout << ex;
			// 여는 괄호 ( 만나면 stack push
			else if (ex == '(') op.push(ex);

			// 닫는 괄호 ) 만나면 stack pop : top은 무조건 ( 이기때문
			else if (ex == ')')
			{
				while (op.top() != '(')
				{
					cout << op.top();
					op.pop();
				}
				op.pop();
			}
		}

	}
	
	// 남은 연산자 출력
	while (!op.empty())
	{
		cout << op.top();
		op.pop();
	}
}

int main()
{
	INPUT();

	SOLVE();
}

🥇문제 후기

풀이도, 포스팅도 참 오래 걸린 문제...
스택은 배경일뿐 모든 경우를 고려하는게 핵심이었고, 이를 풀이하는 것은 쉬울 때가 없다.
'시험장에서 경우의 수 못 찾으면 상당히 초조해질것같은데, 그때는 어떡하지?'라는 생각이 드나, 연습 많이 하는거 말고 방법이 있을까싶다. 오랜만에 자료구조 문제 풀고싶어서 무작정 시작해놓고 지친 문제..ㅋㅋㅋㅋㅋ