백준 1918번 C++ 풀이

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

1918번: 후위 표기식

시간 제한	메모리 제한	solved.ac 티어
2초	128MB	골드 3

문제

수식은 일반적으로 3가지 표기법으로 표현할 수 있다. 연산자가 피연산자 가운데 위치하는 중위 표기법(일반적으로 우리가 쓰는 방법이다), 연산자가 피연산자 앞에 위치하는 전위 표기법(prefix notation), 연산자가 피연산자 뒤에 위치하는 후위 표기법(postfix notation)이 그것이다. 예를 들어 중위 표기법으로 표현된 a+b는 전위 표기법으로는 +ab이고, 후위 표기법으로는 ab+가 된다.

이 문제에서 우리가 다룰 표기법은 후위 표기법이다. 후위 표기법은 위에서 말한 법과 같이 연산자가 피연산자 뒤에 위치하는 방법이다. 이 방법의 장점은 다음과 같다. 우리가 흔히 쓰는 중위 표기식 같은 경우에는 덧셈과 곱셈의 우선순위에 차이가 있어 왼쪽부터 차례로 계산할 수 없지만 후위 표기식을 사용하면 순서를 적절히 조절하여 순서를 정해줄 수 있다. 또한 같은 방법으로 괄호 등도 필요 없게 된다. 예를 들어 a+b*c를 후위 표기식으로 바꾸면 abc*+가 된다.

중위 표기식을 후위 표기식으로 바꾸는 방법을 간단히 설명하면 이렇다. 우선 주어진 중위 표기식을 연산자의 우선순위에 따라 괄호로 묶어준다. 그런 다음에 괄호 안의 연산자를 괄호의 오른쪽으로 옮겨주면 된다.

예를 들어 a+b*c는 (a+(b*c))의 식과 같게 된다. 그 다음에 안에 있는 괄호의 연산자 *를 괄호 밖으로 꺼내게 되면 (a+bc*)가 된다. 마지막으로 또 +를 괄호의 오른쪽으로 고치면 abc*+가 되게 된다.

다른 예를 들어 그림으로 표현하면 A+B*C-D/E를 완전하게 괄호로 묶고 연산자를 이동시킬 장소를 표시하면 다음과 같이 된다.

결과: ABC*+DE/-

이러한 사실을 알고 중위 표기식이 주어졌을 때 후위 표기식으로 고치는 프로그램을 작성하시오

입력

첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식은 주어지지 않는다. 표기식은 알파벳 대문자와 +, -, *, /, (, )로만 이루어져 있으며, 길이는 100을 넘지 않는다. 

출력

첫째 줄에 후위 표기식으로 바뀐 식을 출력하시오

---

스택에 대해 배우다보면 후위표기식에 관한 내용은 단골일 것이다. 이번에는 중위표기식을 후위표기식으로 바꾸는 문제이다. 후위표기식을 계산하는 문제는 피연산자, 즉 숫자를 스택에 넣었지만, 후위표기식으로 변환할 때에는 연산자를 스택에 삽입해야 한다.

 

피연산자는 그냥 두고, 연산자는 스택에 넣으며 다시 꺼내어 피연산자 뒤에 붙이면 된다. 하지만, 이 때 따져야 할 것은 연산자 우선순위이다. a * b + c라는 중위 표기식을 바꾸려고 할 때, 단순히 연산자들을 스택에 push했다가 pop하면 abc+*가 되는데, 이는 잘못된 변환이다. 정확한 변환은 ab*c+이다. 따라서 연산자를 push하기 전에, push하려는 연산자보다 스택의 top에 있는 연산자의 우선순위가 더 큰 경우, 스택에서 먼저 pop해서 후위표기식에 붙이고 다시 비교해야한다. 그러면 a - b + c는 어떨까? +와 -의 연산자 우선순위는 같기 때문에 그냥 붙여도 될까? abc+-가 맞는걸까? 이 역시 틀렸다. abc-+가 맞는 변환이다.

 

이를 통해 알 수 있는 것은 연산자를 스택에 push하려고 할 때, 스택의 top연산자와 비교하여 top의 우선순위가 push하려는 연산자의 우선순위보다 크거나 같은 경우, 스택의 top을 pop해서 후위표기식에 붙인 후에, 다시 top이랑 비교해야한다.

 

괄호는 어떻게 처리할까? 여는 괄호는 무조건 push한다. 이후 닫는 괄호가 등장하는 경우, 여는 괄호가 등장할 때까지 스택에 남아있는 모든 연산자를 pop하면서 후위표기식에 붙인다. 중간에 연산자 우선순위는 닫는 괄호가 등장하기 전까지 알아서 처리가 되있을 것이기 때문이다.

 

#include <bits/stdc++.h>
using namespace std;

int prec(char op) { // 연산자 우선순위
    if (op == ')' || op == '(') return 0;
    else if (op == '+' || op == '-') return 1;
    else if (op == '*' || op == '/') return 2;
    return -1;
}

void solution(string& infix) {
    string postfix = "";
    stack<char> op_stack;
    for(const char& elem : infix) {
        if (elem == '+' || elem == '-' || elem == '*' || elem == '/') {
            while(!op_stack.empty() && prec(elem) <= prec(op_stack.top())) {
                postfix += op_stack.top();
                op_stack.pop();
            }
            op_stack.push(elem);
        }
        else if (elem == '(') {
            op_stack.push(elem);
        }
        else if (elem == ')') {
            while(op_stack.top() != '(') {
                postfix += op_stack.top();
                op_stack.pop();
            }
            op_stack.pop();
        }
        else {
            postfix += elem;
        }
    }
    while (!op_stack.empty()) {
        postfix += op_stack.top();
        op_stack.pop();
    }
    cout << postfix;
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    string infix;
    cin >> infix;
    solution(infix);
}