[C++] 백준 1918번: 후위 표기식 (스택)

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

---

문제 이해하기

 문제의 요구사항은 다음과 같습니다.

주어진 중위 표기식을 후위 표기식으로 바꾸어라.

---

시간복잡도 어림하기

 자료 구조를 활용한 구현 문제이므로 생략하도록 하겠습니다.

---

알고리즘 설계하기

 컴퓨터 전공 또는 개인적으로 공부하면서 전위, 중위, 후위 표기식에 대해 공부해 보셨다면 아시겠지만, 후위 표기식을 구현하기 위해서는 스택 자료구조를 사용합니다.

 후위 표기식의 성질 상, 우선 순위가 가장 높은 연산자가 가장 앞에오고, 중위 표기식에서는 가장 우선순위가 높은 연산자가 가장 먼저 나온다는 보장이 없습니다. 따라서 중위 표기식에서 후위 표기식으로 변환할 때 나중에 들어온 연산자가 우선순위가 높다면 가장 먼저 꺼내야 하기 때문에 스택 자료구조를 사용합니다.

 또한, 후위 표기식의 특징은 중위 표기식과 비교했을 때 연산자의 순서는 바뀔 수 있지만, 피연산자의 순서는 바뀌지 않는다는 특징을 가지고 있습니다. 따라서 중위 표기식을 탐색하다 피연산자를 만난다면 바로 출력을 하면 됩니다.

 간단히 코드를 설계해 봅시다. 기본 구조는 다음과 같습니다.

1. 현재 문자가 피연산자라면, 바로 출력
2. 현재 문자가 연산자라면
 2.1 스택의 가장 위 연산자가 현재 현산자보다 우선순위가 높다면
    - 스택의 가장 위 연산자 출력, 스택 pop
 2.2. 2.1 조건을 만족하지 않을 때까지 반복
 2.3 현재 연산자 스택에 push

 이와 같은 로직으로 중위 표기식을 후위 표기식으로 변환할 수 있습니다.

 하지만 아직 완전한 코드는 아닙니다. 중위 표기식에 괄호가 포함된 경우를 고려하지 않았기 때문입니다.

 괄호 연산의 특징은 괄호 안의 연산이 가장 우선순위가 높다는 점입니다. 그리고 괄호 안의 연산자들은 기본 연산 우선순위를 따릅니다. 괄호를 고려한 로직은 다음과 같습니다.

1. 현재 문자가 여는 괄호( '(' )라면 스택에 push
2. 현재 문자가 닫는 괄호( ')' )라면
  - '('을 만날때까지 스택의 가장 위 연산자를 출력한다.
3. 현재 문자가 피연산자라면, 바로 출력
4. 현재 문자가 연산자라면
 4.1 스택의 가장 위 연산자가 현재 현산자보다 우선순위가 높다면
    - 스택의 가장 위 연산자 출력, 스택 pop
 4.2. 4.1 조건을 만족하지 않을 때까지 반복
 4.3 현재 연산자 스택에 push 

 이렇게 현재 문자가 여는 괄호일 때와 닫는 괄호일 때의 로직만 추가하면 문제를 해결할 수 있습니다.

---

알고리즘 구현하기

 최종 코드는 다음과 같습니다.

#include<iostream>
#include<string>
#include<stack>
using namespace std;

string str, ret = "";
stack<char> stk;
//연산자 판단 로직
bool isOperater(char c){
    if(c == '+' || c == '-' || c == '*' || c == '/') return true;
    return false;
}
//연산자 우선순위 반환 로직; a가 b보다 우선순위가 높으면 true 반환
bool getPriority(char a, char b){
    if(a == '(') return false;
    if(b == '+' || b == '-'){
        return true;   
    }
    else{
        if(a != '+' && a != '-') return true;
        return false;
    }
}
int main() {
    cin >> str;
    for(char c : str){
        if(c == '('){
            stk.push(c); continue;
        }
        if(c == ')'){
            while(!stk.empty()){
                if(stk.top() == '('){ //'('까지 pop
                    stk.pop(); //'(' 제거
                    break;
                }
                ret += stk.top();
                stk.pop();
            }
            continue;
        }
        if(isOperater(c)){ //현재 문자가 연산자인 경우
            //c보다 우선도가 크지 않은 연산자가 나올때까지 pop
            while(!stk.empty() && getPriority(stk.top(), c)){
                ret += stk.top();
                stk.pop();
            }
            stk.push(c); //현재 연산자 push
            continue;
        }
        ret += c; //현재 문자가 피연산자인 경우
    }
    while(!stk.empty()){ //스택에 남은 연산자 처리
        ret += stk.top();
        stk.pop();
    }
    cout << ret;
    return 0;
}

 마지막 부분에 스택을 비우는 로직을 넣은 이유는 이전 로직에서 출력되지 못하고 남은 연산자들을 비워주기 위해서 입니다. 마지막까지 남아있는 연산자는 우선순위가 높지 않은 연산자이므로 pop 순서대로 출력하면 됩니다.

 또한, getPriority(a, b) 함수는 a가 b보다 연산자 우선도가 높은지 판별하는 함수입니다. 이때, a가 '(' 인 경우 항상 우선도가 낮다는 false를 반환해야 합니다. 괄호 연산의 경우 우선도가 높다고 생각하여 true라고 생각하실 수 있지만, '('의 우선도가 가장 낮아야지 ')'가 나올때까지 스택 안에 있게되므로 반드시 '('의 우선도를 가장 낮게 설정해야 합니다.

---