[백준 1918] - 후위 표기식(Stack) C++

문제

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

1918번: 후위 표기식

접근방법

well known중에 well known

infix to postfix 문제다. 

 

연산자들은 따로 모아뒀다가,

낮은 우선순위 연산자가 들어올 때,

한꺼번에 postfix에 넣어준다.

 

여기서는 +, -, *, /가 전부다.

곱하기 나누기가 들어오면 따로 모아놨다가,

더하기 빼기 들어왔을 때, 다 빼서 postfix에 붙이면 된다.

 

그리고 중요한건 '('가 들어왔을 때 어떻게 처리하냐.. 인데

'('없이 ')'만 들어오는 입력은 없으므로

'('가 들어왔을 때, operators에 집어 넣어놨다가,

')'가 들어오면, 그 때, 

 

 

A * (B + C)가 입력으로 들어온 경우,

'('가 없다면 AB*C+가 될 것이다.

 

'('이 있다면,

'('의 우선순위는 여기서 0이기 때문에, +가 들어왔을 때, *가 바로 POP되지 않는다.

따라서 +가 들어왔을 때 operators의 상태는 {'*', '(', '+'}가 될 것이고, postfix의 상태는 AB다.

이 상태에서 C가 들어오면, ABC가 되고

마지막으로 ')'가 들어오면,

'('가 발견될 때까지 POP해서 postfix에 집어넣으므로

postfix는 ABC+가 된다.

이 상태에서 operators에 남은 연산을 모두 집어 넣으면,

ABC+*이다. 

 

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <stack>

using namespace std;

#define FOR(i, n) for (int i=0;i<(n);++i)
#define _FOR(i, s, n) for (int i=s;i<(n);++i)
#define INF 987654321

map<char, int> priority = {
    {'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}
};
string infix;    

bool isOperator(char c) {
    return priority.find(c) != priority.end();
}

string InfixToPostfix(string infix) {
    string postfix;
    stack<char> operators;

    for (auto& c : infix) {
        if (isalpha(c)) postfix += c;
        else if (c == '(') {
            operators.push(c);
        } else if (c == ')') {
            while(!operators.empty() && operators.top() != '(') {
                postfix += operators.top();
                operators.pop();
            }
            operators.pop();
        } else if (isOperator(c)) {
            //operators에 들어있는 친구들 중에 c보다 우선순위 높음 친구들 pop
            //예를 들어서 c가 +인데 그전에 * 들어온 게 있으면 그것들 전부 +앞으로 넣어야함.
            while(!operators.empty() && priority[operators.top()] >= priority[c]) {
                postfix += operators.top();
                operators.pop();
            }
            operators.push(c);
        }
    }
    //남은 연산자 다 뒤로 붙이기
    while (!operators.empty()) {
        postfix += operators.top();
        operators.pop();
    }
    return postfix;
}

int main() {

    cin >> infix;
    cout << InfixToPostfix(infix) << endl;

    return 0;
}

개선할 점

하나씩 받으면서, operator를 따로 저장해놨다가

적절한 타이밍에 하나씩 다시 postfix에 집어넣는 것이 포인트다.