[BOJ 1918] 후위표기식

1918번: 후위 표기식

문제 분석

• 시간 제한 2초: Big-O 기준 2억연산
• 다루는 값들의 수 100
• 문자열로 입력된 값을 우선순위에 맞춰 출력 해줘야 함
• 우선순위 : A~Z > *,/ > +,- 
• '()'에 대한 처리도 해줘야함

주의 사항

• '()'안에 들어 있는 식은 독자적인 하나의 식으로 생각하기
• '(',')'는 출력하지 않는다.

풀이 방식

• 문자 하나씩 stack에 쌓기
• stack.top 이 문자보다 우선순위가 높거나 같으면 출력하고 pop
• '('의 우선순위는 A~Z 보다 낮고 연산자 보다 높다.
• ')'가 나오면 가장 위에 있는 '(' 까지 pop
• 마지막으로 stack에 남아있는 문자 전부 pop

stack<char> opr;
string exp;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> exp;
    for (char &c: exp) {
        if (c >= 'A' && c <= 'Z') { // 가장 우선순위 높음 pop해줄 거 없음
            opr.push(c);
        } else if (c == '(') { // 우선순위 두번째
            while (!opr.empty() && opr.top() != '(') {
            //괄호 안에 있는 식은 독자적인 식으로 생각하기 위해 
            //stack이 비거나 괄호 안에 있는 식일때 까지 반복
                if (opr.top() >= 'A' && opr.top() <= 'Z') {//A~Z 만 pop
                    cout << opr.top();
                    opr.pop();
                } else break;
            }
            opr.push(c);
        } else if (c == '*' || c == '/') {//우선순위 세번째
        	//'('와는 비교하지않음, 괄호안에 있는 식은 독자적인 식
            while (!opr.empty() && opr.top() != '(') {
                if (opr.top() >= 'A' && opr.top() <= 'Z') {
                    cout << opr.top();
                    opr.pop();
                } else if (opr.top() == '*' || opr.top() == '/') {
                    cout << opr.top();
                    opr.pop();
                } else {
                    break;
                }
            }
            opr.push(c);
        } else if (c == '+' || c == '-') {
            while (!opr.empty() && opr.top() != '(') {
            //우선순위가 가장 낮으므로 비교없이 전부 pop
                cout << opr.top();
                opr.pop();
            }
            opr.push(c);
        } else if (c == ')' && !opr.empty()) {
        //')' 가 나오면 '('까지 pop
            while (!opr.empty() && opr.top() != '(') {
                cout << opr.top();
                opr.pop();
            }
            opr.pop();
        }
    }
    //stack에 남은거 pop
    while (!opr.empty()) {
        cout << opr.top();
        opr.pop();
    }
    return 0;
}

느낀 점

• 괄호연산이 없는 후위표기식 문제는 풀어봤기에 어렵지 않게 풀 수 있을 거라 생각했다.
• 괄호를 처리해 주기 위해 연산과정을 그림을 그려가며 스스로 후위 표기식으로 식을 바꿔 봤다.
• stack 그림을 그려가며 푸니까 스스로 어떤 사고방식으로 후위 표기식으로 바꾸는지 파악하고, 이 사고방식을 코드로 옮겨 봤다.
• 그럼에도 구현이 쉽지는 않았지만 큰 어려움 없이 해결했다.