[백준-1918] 후위 표기식

1918번: 후위 표기식

경우의 수 나눠서 처리하면 된다.

입력받은 string 을 돌면서

1. 숫자인 경우 answer 에 push

2. 연산자인 경우
   1. +, - 인 경우
      1. 이미 들어있는게 *, / 인 경우: 우선 순위가 높은 *, / 를 stack 에서 뺀 후 answer 에 push → 그리고 기존 거 stack 에 push
      2. 이미 들어있는게 +, - 인 경우: 먼저 들어있는 +, - 를 stack 에서 뺀 후 answer 에 push → 그리고 기존 거 stack 에 push
   2. *, / 인 경우
      1. 이미 들어있는게 *, / 인 경우: 먼저 들어있는 *, / 를 stack 에서 뺀 후 answer 에 push → 그리고 기존 거 stack 에 push
      2. 이미 들어있는게 +, - 인 경우: 기존의 *, / 가 우선순위 높으니 stack 에 바로 push
   3. (, ) 인 경우
      1. ( 인 경우 : answer 에 일단 push
      2. ) 인 경우 : ( 가 나올때까지 "pop → answer 에 push" 반복

 

이 로직을 직접 구현하면 처리 된다.

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstdio>
#include <tuple>
#include <string>
#include <string.h>
#include <stack>
#include <set>
#include <map>


using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef tuple<int, int, string> tii;
int root[500001];

bool check_oper(char c) {
	return (c == '*' || c == '+' || c == '-' || c == '/' || c == '(' || c == ')');
}
bool div_mul(char c) {
	return c == '*' || c == '/';
}
bool plu_min(char c) {
	return c == '+' || c == '-';
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	string n;
	cin >> n;

	stack<char> st;
	string answer;
	for (int i = 0; i < n.size(); i++) {
		if (check_oper(n.at(i))) {
			if (st.empty()) 
				st.push(n.at(i));
			else {
				if (div_mul(st.top())){
					if (plu_min(n.at(i))) {
						while (1) {
							answer.push_back(st.top());
							st.pop();
							if (st.empty()) break;
							if (plu_min(st.top())) continue;
							else break;
						}
						st.push(n.at(i));
					}
					else if (div_mul(n.at(i))) {
						answer.push_back(st.top());
						st.pop();
						st.push(n.at(i));
					}
					else {
						if (n.at(i) == '(') st.push(n.at(i));
						else if (n.at(i) == ')') {
							while (st.top() != '(') {
								answer.push_back(st.top());
								st.pop();
							}
							st.pop(); // ( 제거
						}
					}
				}
				else if (plu_min(st.top())) {
					if (n.at(i) == ')') {
						while (st.top() != '(') {
							answer.push_back(st.top());
							st.pop();
						}
						if (st.top() == '(') st.pop(); // ( 제거
					}
					else if (plu_min(n.at(i))) {
						answer.push_back(st.top());
						st.pop();
						st.push(n.at(i));
					}
					else {
						st.push(n.at(i));
					}
				}
				else if(st.top() == '(' || st.top() == ')'){
					if (n.at(i) == ')') {
						while (st.top() != '(') {
							answer.push_back(st.top());
							st.pop();
						}
						if(st.top() == '(') st.pop(); // ( 제거
					}
					else st.push(n.at(i));
				}
			}
		}
		// 숫자인 경우
		else {
			answer.push_back(n.at(i));
		}
	}
	while (!st.empty()) {
		answer.push_back(st.top());
		st.pop();
	}
	cout << answer;

	return 0;
}