📘 문제

문제링크 : https://www.acmicpc.net/problem/1918 (solved.ac class4)

📝 문제 풀이

해당 문제는 수업 자료구조 시간에 과제로 풀어본 기억이 있어서 스택으로 푸는 문제인지 바로 알 수 있었다.
❗️중위표시법을 후위표시법으로 변경할 때 주의할 점은 연산자(operator)를 스택에 넣을 때 연산순위를 비교해서 행동을 취해주는 것이다.
일단 주어진 문제에서 연산자는 +, -, *, / 의 사칙연산인데, 모두가 아시다시피 (+, -) < (*, /) 로 연산순위가 높다.
앞에서부터 문자열을 읽으면서 영대문자일 경우는 출력하고 연산자일 경우는 스택의 top의 연산자와 비교했을 때 스택의 top의 연산자보다 연산순위가 높으면 push하고, 같거나 낮으면 pop을 해서 출력한다. 이 때 한번만 비교하는 것이 아니라 stack이 비거나 stack의 top의 연산자보다 높을 때까지 비교를 해주는 것이 중요하다.
필자의 코드에서는 +,- 일 경우는 +,- 보다 낮은 연산자가 없으므로 stack이 빌때까지 pop하였고, *, / 일 경우는 top이 +,- 이거나 stack이 비어있을 때까지 확인하여 출력하였다.
그리고 해당 문제에서는 '(', ')' 도 있으므로 이것도 해결해야한다. 괄호의 경우는 연산순위가 가장 높으므로 ')' 닫히는 괄호가 나오면 괄호안에 모든 연산을 끝내는 것이 중요하다고 생각했다. 그래서 필자는 코드에서 '(' 여는 괄호가 나오면 재귀로 함수를 다시 불러 새로운 stack을 사용해서 ')' 닫히는 괄호가 나오면 stack을 비워주게 작성했다. 즉 괄호가 나올 경우는 큰 문제안에 똑같은 작은 문제가 있는 것으로 생각했다.

처음 보면 당황할 수 있지만 비슷한 문제를 알고 있다면 문제에 추가된 부분만 신경쓴다면 쉽게 풀 수 있는 문제인 것 같다.

✏️ 알고리즘 스케치

💻 소스코드

#include <iostream>
#include <stack>
#include <string>
#include <queue>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

void makePostfix(queue<char>& infix);

int main()
{
    fastio;
    
    string infix;
    cin >> infix;
    
    queue<char> q;
    for(int i=0; i<infix.size(); i++)
        q.push(infix[i]);

    makePostfix(q);
    
    return 0;
}

void makePostfix(queue<char>& infix)
{
    stack<char> s;
    
    while(infix.size()){
        char c = infix.front();

        if('A' <= c && c <= 'Z'){
            cout << infix.front();
            infix.pop();
        }
        else if(c =='('){
            infix.pop();
            makePostfix(infix);
        }
        else if(c == ')'){
            infix.pop();
            while(s.size()!=0){
                cout << s.top();
                s.pop();
            }
            return;
        }
        else if(c == '+' || c == '-'){
            while(s.size()!=0){
                cout << s.top();
                s.pop();
            }
            s.push(c);
            infix.pop();
        }
        else{ // *,/
            while(s.size()!=0 && (s.top()=='*' || s.top()=='/')){
                cout << s.top();
                s.pop();
            }
            s.push(c);
            infix.pop();
        }
    }

    while(s.size()!=0){
        cout << s.top();
        s.pop();
    }
        
}