[BOJ 1918번/C++] 후위 표기식

미숙한 블로그 주인이 코딩테스트 문제를 풀어가는 과정을 담은 글입니다. 이 풀이가 효율적인 풀이가 아닐 수 있으며, 부정확한 정보가 많이 있을 수 있습니다. 보완해야할 점이 있다면 댓글로 남겨주세요!

 

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

1918번: 후위 표기식

 

풀이

문제 설명에도 잘 나와있듯, 수식은 일반적으로 전위 표기법, 중위 표기법, 후위 표기법으로 나타낼 수 있다.

전위 표기법은 연산자가 먼저, 피연산자가 나중에 나오는 표현법이다.

중위 표기법은 우리가 주로 사용하는 표기법으로, 피연산자 사이에 연산자가 나오는 방식이다.

후위 표기법은 피연산자가 먼저, 연산자가 뒤에 나오는 표현 방식이다.

 

중위 표기법을 후위 표기법으로 바꾸는 방법으로는 주로 스택을 이용한다.

식을 둘러보면서 피연산자는 나열하고, 연산자는 스택에 저장하고 꺼내는 방식으로 식을 구성하게 된다.

 

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

#define endl '\n'

using namespace std;

int priority(char o) {
    if (o == '(' || o == ')') {
        return 0;
    }
    else if (o == '*' || o == '/') {
        return 1;
    }
    else {
        return 2;
    }
}

int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    stack<char> s;

    string e;
    cin >> e;

    string answer;
    for (int i = 0; i < e.size(); i++) {
        if (isalpha(e[i])) {
            answer += e[i];
        }
        else {
            if (s.empty()) {
                s.push(e[i]);
            }
            else {
                if (e[i] == '(') {
                    s.push(e[i]);
                }
                else if (e[i] == ')') {
                    while (s.top() != '(') {
                        answer += s.top();
                        s.pop();
                    }
                    s.pop(); // '(' 와 ')'는 식에 포함 안시킴.
                }
                else if (priority(e[i]) >= priority(s.top()) && s.top() != '(') {
                    while (!s.empty() && (priority(e[i]) >= priority(s.top())) && s.top() != '(') {
                        answer += s.top();
                        s.pop();
                    }
                    s.push(e[i]);
                }
                else {
                    s.push(e[i]);
                }
            }
        } 
    }
    while (!s.empty()) {
        answer += s.top();
        s.pop();
    }

    cout << answer << endl;

    return 0;
}