[Algorithm] Baekjoon 1918번 : 후위 표기식

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

1918번: 후위 표기식

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    string input;
    stack<char> s;
    string result;
 
    cin >> input;
 
    for (int i = 0; i < input.size(); ++i)
    {
        char current = input[i];
 
        if (current >= 'A' && current <= 'Z') // 피연산자면 바로 출력.
        {
            result.push_back(current);
        }
 
        else if (current == '+' || current == '-') // 현재 +,-이면 무조건 s.top 출력 후, pop하고  현재꺼 푸쉬.
        {
            while (!s.empty() && s.top() != '(')
            {
                result.push_back(s.top());
                s.pop();
            }
 
            s.push(current);
        }
 
        else if (current == '*' || current == '/')
        {
            while (!s.empty() && (s.top() == '*' || s.top() == '/')) // top이 '*'나 '/' 이외의 것이라면, 실행하지않는다.
            {
                result.push_back(s.top());
                s.pop();
            }
 
            s.push(current);
        }
 
        else if (current == '(') // '(' 이면 스택에 바로푸쉬.
        {
            s.push(current);
        }
 
        else if (current == ')')
        {
            while (s.top() != '(') // '(' 만날 때까지
            {
                result.push_back(s.top());
                s.pop();
            }
 
            s.pop(); // '(' 꺼내기
        }
    }
 
    while (!s.empty())
    {
        result.push_back(s.top());
        s.pop();
    }
 
    cout << result;
}

 

중위 표기식을 후위표기식으로 다르게 표현해야 하는 문제다.

뭔가 문제를 보면 일단 스택을 이용해서 푸는 문제라는건 바로 알수 있었다만, 결국 스스로 정답을 도출하지는 못했다.

 

개인적인 생각으로, 이 문제의 핵심은 stack의 top의 연산순위는 current보다 낮게 유지되어야 한다는 것 같다.

 

1. current가 피연산자면 바로 출력

2. current가 곱하기나 나누기일 때

    -> 스택의 탑도 곱하기나 나누기면 top을 출력 후 pop한다. (스택의 top이 곱하기나 나누기가 아닐 때까지 반복)

    -> 즉, 스택의 top이 current보다 우선순위가 낮아질때까지 반복.

    -> 위의 작업을 마친 후에 current를 스택에 push. 

 

3. current가 더하기나 빼기일 때

    -> current가 더하기나 빼기라면 stack의 top이 '('이 아닌이상 계속 출력 후 pop 해준다.

    -> current가 더하기나 빼기라면 stack에 들어가 있는 연산자들의 우선순위는 무조건 current보다 같거나 높기 때문.

    -> '('이 pop이 되는 순간은, current가 ')'을 만났을 때 말고는 없다.

 

4. current가 '(' 이라면 스택에 바로 push.

5. current가 ')' 이라면

    -> stack의 top이 '('이 될 때까지 스택의 top을 출력하고 pop하는것을 계속 반복한다.

    -> 이후 반복문이 멈추면 한번 더 pop을 해주면 된다.  ( '('을 빼줘야하니까 ) 

 

6. 이후 반복문이 끝나고 스택의 잔여 문자들을 출력해주면 된다.

 

늘 그렇듯이 한문제에 시간을 너무 오래쓴 경향이 없지않아 있지만, 대신 나중에 비슷한 유형 나오면 나름 기억이 잘 나기는 한다.