[백준] 1918_후위 표기식 C++

18 Jun 2023 in Study on Coding Test

스택 이용해보는 문제

정답제출코드

#include <iostream>
#include <stack>
#include <string>

using namespace std;

int main()
{
    string s;
    cin >> s;

    stack<char> st;

    for (size_t i = 0; i < s.length(); ++i)
    {
        if (s[i] == '(')
            st.push(s[i]);
        
        else if (s[i] == '+' || s[i] == '-')
        {
            while (!st.empty() && st.top() != '(')
            {
                cout << st.top();
                st.pop();
            }
            st.push(s[i]);
        }
        else if (s[i] == '*' || s[i] == '/')
        {
            while (!st.empty() && st.top() != '(' && (st.top() == '*' || st.top() == '/'))
            {
                cout << st.top();
                st.pop();
            }
            st.push(s[i]);
        }
        else if (s[i] == ')')
        {
            while (!st.empty() && st.top() != '(')
            {
                cout << st.top();
                st.pop();
            }
            st.pop();
        }
        else if ('A' <= s[i] && s[i] <= 'Z')
            cout << s[i];
    }

    while (!st.empty())
    {
        cout << st.top();
        st.pop();
    }

    return 0;
}

스택을 이용해서 식을 출력해보는 문제였다.

하지만 곱하기와 나누기는 더하기와 빼기에 비해서 우선 순위가 높고,

괄호가 나왔을 때에도 우선 순위를 부여하는 데 어려움을 겪었다.

솔직히.. 도저히 우선순위를 부여할 방법이 떠오르지 않아서

참고링크를 참고해서 풀었다.

• A~Z일 경우 바로 출력
• 왼쪽 괄호라면 stack에 push
• 연산자라면 우선순위 고려

stack top: + or -, 현재 연산자: * or /
stack에 현재 연산자 push

stack top: + or -, 현재 연산자: + or -
stack이 빌 때까지, 현재 연산자 우선순위와 같거나 낮을 동안 출력후 현재 연산자 push

stack top: or /, 현재 연산자: or /
stack이 빌 때까지, 현재 연산자 우선순위와 같거나 낮을 동안 출력후 현재 연산자 push

stack top: * or /, 현재 연산자: + or -
stack이 빌 때까지, 현재 연산자 우선순위와 같거나 낮을 동안 출력후 현재 연산자 push

이를 그대로 구현하면 위의 코드와 같아진다.