(2024-11-06) 1 문제 : 백준 - 1918 (후위 표기식)

 

스택을 사용하는 문제이다. 연산자 간의 우선순위를 따져서 출력하는 로직을 짜면 된다.

 

본인이 출력한 로직은 아래와 같다. 먼저, 모든 연산 기호는 stack에 삽입해주었다. 

 

1. 알파벳이라면 그대로 정답 문자열의 맨 뒤에 문자를 삽입해준다.

 

2. 현재 문자가 ')' 이라면 연산 기호 스택의 top이 '(' 이 될 때까지 계속 기호를 pop하며 문자의 맨 뒤에 삽입해준다.

 

3. 현재 기호가 ')'이 아니고 우선순위가 stack의 top의 우선순위와 같다면 정답 문자열의 맨 뒤에 이전 문자를 삽입한 뒤 stack을 pop한다. 현재 문자는 stack에 삽입해준다.

 

4. 현재 기호가 ')'이 아니고 우선순위가 이전 문자보다 낮다면 정답 문자열의 맨 뒤에 이전 문 문자를 삽입한 뒤 stack을 pop한다. 현재 문자는 stack에 삽입해준다.

 

5. 이외의 경우엔 stack에 기호를 삽입해준다.

 

#include <iostream>
#include <vector>

#include <queue>
#include <stack>

void Init()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
}

int main()
{
    Init();

    std::string Input;
    std::cin >> Input;

    std::stack<char> Sign;

    std::string Answer = "";

    for (int i = 0; i < Input.size(); i++)
    {
        char CurChar = Input[i];

        if (CurChar >= 'A' && CurChar <= 'Z')
        {
            Answer.push_back(CurChar);
        }
        else
        {
            if (CurChar == ')')
            {
                while (Sign.size() > 0 && Sign.top() != '(')
                {
                    Answer.push_back(Sign.top());
                    Sign.pop();
                }

                if (Sign.size() > 0 && Sign.top() == '(')
                {
                    Sign.pop();
                }
                
            else if (Sign.size() > 0 && (Sign.top() == '+' || Sign.top() == '-') && (CurChar == '+' || CurChar == '-'))
            {
                Answer.push_back(Sign.top());
                Sign.pop();
                Sign.push(CurChar);
            }
            else if (Sign.size() > 0 && (Sign.top() == '*' || Sign.top() == '/') && (CurChar == '*' || CurChar == '/'))
            {
                Answer.push_back(Sign.top());
                Sign.pop();
                Sign.push(CurChar);
            }
            else if (Sign.size() > 0 && (Sign.top() == '*' || Sign.top() == '/') && (CurChar == '+' || CurChar == '-'))
            {
                while (Sign.size() > 0 && Sign.top() != '(')
                {
                    Answer.push_back(Sign.top());
                    Sign.pop();
                }

                Sign.push(CurChar);
            }
            else
            {
                Sign.push(CurChar);
            }
        }
    }

    while(Sign.size() > 0)
    {
        Answer.push_back(Sign.top());
        Sign.pop();
    }

    std::cout << Answer;

    return 0;
}