백준 1918 후위 표기식

1918번: 후위 표기식

문제

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

입력

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

풀이

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

이런 식으로 스택을 사용해서 계산할 수 있다.

 

중위 표기식 -> 후위 표기식

1. 주어진 중위 표기식을 연산자의 우선순위에 따라 괄호로 묶어준다.

2. 괄호 안의 연산자를 괄호의 오른쪽으로 옮겨준다.

예를 들어

A + B / C *D + F

인 경우

1. ( ( A + (( B / C ) * D)) + F )

    ( ( A + ( BC/ * D ) ) + F )

    ( ( A + BC/D* ) + F )

    ( ABC/D*+ ) + F

      ABC/D*+F+

이런 식으로 할 수 있다.

 

만약 입력으로 

(A+B)*C

이렇게 주어진다면 괄호안의 식 먼저 계산해주어야 하므로

AB+C* 이런식으로 답이 나와야 할 것이다.

 

이 방법을 코드로 구현하기 위해서

결과 벡터, 연산자와 괄호를 넣을 스택을 만들어 주었다.

#include <iostream>
#include <vector>
#include <string>
#include <map>
 
using namespace std;
 
map<char, int> op;    // 연산자 우선순위를 저장할 맵
 
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    string str;
    cin >> str;
    
    vector<char> temp;            // 연산자, 괄호 스택
    vector<char> ret;            // 결과
 
    // 연산자 우선순위
    op['*'] = 0;
    op['/'] = 0;
    op['+'] = 1;
    op['-'] = 1;
 
 
    for (int i = 0; i < (int)str.length(); ++i) {
        if (str[i] == '*' || str[i] == '/' || str[i] == '+' || str[i] == '-') {    // 연산자
            if (temp.empty()) {    // temp가 비어있다면
                temp.push_back(str[i]);
            }
            else {
                // 연산자 우선순위 정리
                char c = temp.back();
                while (c != '(' && op[c] <= op[str[i]]) {
                    ret.push_back(c);
                    temp.pop_back();
                    if (temp.empty()) break;
                    c = temp.back();
                }
                temp.push_back(str[i]);
            }
        }
        else if (str[i] == '(') {    // 괄호 라면
            temp.push_back(str[i]);    // '('일 경우 스택에 넣어준다.
        }
        else if (str[i] == ')') {    // ')'일 경우 '('가 나올때까지 스택에서 연산자를 꺼내서 결과 벡터에 넣는다.
            char top = temp.back();
            while (top!='(') {
                ret.push_back(top);
                temp.pop_back();
                top = temp.back();
            }
            temp.pop_back();
        }
        else {
            // 괄호도, 연산자가 아니라면
            ret.push_back(str[i]);
        }
    }
 
    while (!temp.empty()) {    // 스택에 남은 나머지 연산자들을 결과 벡터로 넣는다.
        char a = temp.back();
        ret.push_back(a);
        temp.pop_back();
    }
 
    for (int i = 0; i < (int)ret.size(); ++i) {
        cout << ret[i];
    }
    cout << "\n";
    
    return 0;
}

1. 괄호나 연산자가 아닌 문자는 바로 결과에 넣는다.

2. 괄호 ( 는 temp에 넣는다.

3. 연산자는 우선순위를 따져줘야한다.

temp의 top이 ( 거나 temp가 비어있을 때는 그냥 push 한다.

top의 연산자 우선순위가 현재 연산자의 순위보다 낮으면

현재 연산자는 결과 벡터에 바로 넣어준다.

그렇지 않을 경우, top에 있는 연산자 우선순위가 현재 연산자의 우선순위보다 낮을때까지 pop하고 결과 벡터에 넣어준 뒤, 현재 연산자를 temp에넣는다.

(temp스택에서 무조건 연산자 우선순위가 높은게 위에 있어야한다!)

4. 괄호 ) 를 만나면 괄호 ( 가 나올때까지 temp에서 pop하고 결과 벡터에 넣어준다.

5. 마지막에는 temp에 남은 연산자들을 모두 결과 벡터에 넣어준다.

---

예제)

입력

( A * B + C ) *D + F

 

 

temp의 top인 *이 +보다 우선순위가 높으므로 pop한 뒤, 결과 벡터에 넣어준다.

) 일 경우 ( 를 만날때까지 연산자를 다 pop해서 결과 벡터에 넣어준다.

이제 temp에 남은 연산자를 결과 벡터으로 모두 옮겨준다.

출력

AB*C+D*F+

 

+ ) 오늘 드디어 300문제 PS했다 !! 400문제도 빨리 풀어야지 !