[BOJ 1918] 후위 표기식 (C++)

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

1918번: 후위 표기식

후위 표기식 문제

 

 

구현 방법

후위 표기법, 중위 표기법, 전위 표기법 간의 변환은 대표적으로 스택으로 해결할 수 있는 문제들입니다.

 

중위 표기식으로 주어진 입력을 후위 표기식으로 변환해주는 코드를 자료구조 시간에 구현해봤는데, 이 문제를 보니 막상 기억이 안 나서 다시 공부해 포스팅해보려 합니다.

 

일단 중위 표기식을 후위 표기식으로 바꾸는 알고리즘은 다음과 같습니다.

• 문자의 경우 바로 출력해준다.
• 연산자 + 와 - 의 경우 스택의 top부터 + 와 - 보다 우선순위가 높거나 같은 연산자가 있으면 계속 출력해준다. 즉, 모든 연산자를 출력해주면 된다. 그리고 해당 연산자를 push 해준다.
• 연산자 * 와 / 의 경우 스택의 top부터 * 와 / 보다 우선순위가 높은 연산자가 없으니, 우선순위가 같은 연산자가 있으면 계속 출력해준다. 그리고 해당 연산자를 push 해준다.
• 여는 괄호 ( 는 그냥 push 해준다
• 닫는 괄호 ) 는, 스택에 여는 괄호 ( 를 만날 때까지 연산자를 모두 출력해준다.
• 마지막에 연산자 스택이 비어있지 않으면 모두 마지막에 출력

이 알고리즘을 적용해 하나의 예시를 들어보겠습니다.

 

중위 표기식 입력 :  A+(B+C*D)/(E+F)

 

입력받은 중위 표기식을 앞에서부터 하나하나 확인해주면 됩니다.

A는 문자니 바로 문자열에 추가해줍니다.

+ 는 ( 를 만나거나 스택이 빌 때까지 모든 연산자를 출력해 주고 스택에 push 합니다.

현재 스택이 비어있으니 출력은 안 해주고 push만 합니다.

여는 괄호 ( 는 그냥 push 해줍니다.

B는 문자니 바로 문자열에 추가해줍니다.

+ 는 ( 를 만나거나 스택이 빌 때까지 모든 연산자를 출력해 주고 스택에 push 합니다.

현재 스택에 여는 괄호 ( 까지 출력할 게 없으니 출력은 안 해주고 push만 합니다.

C는 문자니 바로 문자열에 추가해줍니다.

* 는 스택의 top에 우선순위가 같은 연산자를 출력해주고 push 해주면 됩니다.

스택의 top은 + 로 우선순위가 * 보다 낮으니 출력해줄 것은 없고 push만 해줍니다.

D는 문자니 바로 문자열에 추가해줍니다.

닫는 괄호 ) 는, 여는 괄호 ( 를 만날 때까지 연산자를 출력해줍니다.

/ 는 스택의 top에 우선순위가 같은 연산자를 출력해주고 push 해주면 됩니다.

스택의 top은 + 로 우선순위가 / 보다 낮으니 출력해줄 것은 없고 push만 해줍니다.

여는 괄호 ( 는 그냥 push 해줍니다.

E는 문자니 바로 문자열에 추가해줍니다.

+ 는 ( 를 만나거나 스택이 빌 때까지 모든 연산자를 출력해 주고 스택에 push 합니다.

현재 스택에 여는 괄호 ( 까지 출력할 게 없으니 출력은 안 해주고 push만 합니다.

F는 문자니 바로 문자열에 추가해줍니다.

닫는 괄호 ) 는, 여는 괄호 ( 를 만날 때까지 연산자를 출력해줍니다.

마지막으로 스택이 빌 때까지 모든 연산자를 출력해줍니다.

 

정답: ABCD*+EF+/+ 가 나왔습니다.

 

위 내용을 아래와 같이 구현했습니다.

소스코드

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    stack<char> s;
    string op;
    cin >> op;
    string answer = "";

    for(int i=0;i<op.size();i++) {
    	//문자면 그냥 출력
        if(isalpha(op[i])) {
            answer += op[i];
        }//여는 괄호는 그냥 push
        else if(op[i] == '(') {
            s.push(op[i]);
        }//* , / 는 스택의 top에 우선순위가 같은 연산자가 있으면 계속 pop
        else if(op[i] == '*' || op[i] == '/') {
            while(!s.empty() && (s.top() == '*' || s.top() == '/')) {
                answer += s.top(); s.pop();
            }
            //마지막에 push
            s.push(op[i]);
        }//+ , - 는 스택이 비거나 ( 를 만날때까지 연산자 계속 pop
        else if(op[i] == '+' || op[i] == '-') {
            while(!s.empty() && s.top() != '(') {
                answer += s.top(); s.pop();
            }
            //마지막에 push
            s.push(op[i]);
        }//닫는 괄호는 여는 괄호를 만날때까지 모두 pop
        else if(op[i] == ')') {
            while(!s.empty() && s.top() != '(') {
                answer += s.top(); s.pop();
            }
            //여는 괄호 pop
            s.pop();
        }
    }
    
    //위 과정을 거쳐도 남아있는 연산자들 pop
    while(!s.empty()) {
        answer += s.top(); s.pop();
    }
    cout << answer;
}