백준 1918 후위 연산자 풀이 C++

Introduction

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

스택의 대표적인 문제 중에 하나인 후위 연산자 문제입니다. 

문제 설명에 연산자 순서대로 괄호를 쳐서 후위 연산자로 바꾸는 과정이 나와있었지만 저 방식으로 하면 손으로는 쉽지만 프로그래밍으로 접근 할 때는 괄호를 추가해야해서 더 복잡하다는 생각이 들었습니다. 

그래서 다른 분들의 블로그 설명을 보고 해당 규칙대로 풀어보려고 했습니다. 하지만 처음에는 후위 연산자 자체를 제대로 이해를 못해서 코딩할 때 많이 헤매었습니다. 하다 하다 안되서 손으로 계속 중위 연산자를 후위 연산자로 바꾸는 연습을 하고 바꾸는 규칙을 완전히 이해 한 후에 다시 코딩 하니 좀 더 쉽게 코딩할 수 있었습니다.

혹시 저 처럼 잘 안되시는 분들은 손으로 먼저 충분히 풀어보고 이해하는 것을 선행하시는게 큰 도움이 될 것이라고 생각합니다.

중요한 규칙은 크게 3가지 입니다.

1. 문자열이 나오면 result(결과 문자열)에 추가한다.

2. ( 가 나오면 스택에 추가한다.

3. 사칙연산자가 나왔을 때 스택이 비어있거나, stack.top()이 ( 또는 자신보다 더 작은 연산자라면 스택에 push한다.

    (반대로 생각하면 스택이 비어있지 않거나 stack.top()이 ( 가 아니고 크거나 같은 연산자라면 위의 경우가 될 때까지 pop해서 result에 추가한다.)

4. ) 가 나오면 ( 가 나올 때까지 pop해서 result에 추가한다.

포인트는 스택은 항상 작은것부터 큰 순서로 연산자가 들어있어야 합니다!

이 규칙이 깨지면 규칙이 맞을 때까지 스택에 있는 연산자를 쭉 pop해주고 다시 시작한다고 생각하시면 좀 더 이해가 쉽습니다.

(균형 트리에서 균형을 유지하는 것과 느낌은 비슷하네요)

ex) A + (B * C ) - (D / E) 일 때

1번 그림에서 * 를 만났을 때 stack.top()이 ( 이기 때문에 우선 순위 상관없이 * 를 스택에 push합니다.

2번 그림에서 ) 를 만났기 때문에 ( 를 만날 때까지 pop해서 result에 추가해주고 ( 는 pop으로 날려줍니다.

3번 그림에서 - 는 스택에 있는 + 보다 우선순위가 높지 않기 때문에 pop해서 result에 추가해주고 - 를 스택에 push해줍니다.

(스택이 작은것부터 큰 순서로 들어있어야한다는 규칙을 위반 했으므로) 

4번 그림에서 / 역시 stack.top()이 ( 이기 때문에 우선 순위에 상관없이 / 를 스택에 push합니다.

5번 그림에서 ) 를 만났기 때문에 ( 를 만날 때까지 pop해서 result에 추가해주고 ( 는 pop으로 날려줍니다.

6번 그림에서 모든 비교 과정이 끝났으므로 스택에 있는 모든 연산자를 pop해서 result에 추가해줍니다. 

1. Switch문을 이용한 풀이

#include <iostream>
#include <stack>
#include <string>
using namespace std;
 
int main() {
    string str;
    cin >> str;
    stack<char> s;
    string result; // 결과 문자열
 
    for(int i=0; i<str.length(); i++) {
 
        if(str[i] >= 'A' && str[i] <= 'Z') {
            result += str[i];
        }
        else {
            switch(str[i]) {
                case '(':
                    s.push(str[i]);
                    break;
                // 사칙연산자를 만난 경우 스택에 현재 연산자보다 우선순위가 높거나 같은 기호는 result에 추가
                case '+':
                case '-':
                    // +, - 연산자를 만난 경우, 스택에 뭐가 있던 ( 를 제외하고 전부 우선순위가 높거나 같으니 result에 추가
                    while(!s.empty() && s.top() != '(') {
                        result += s.top();
                        s.pop();
                    }
                    // 스택이 비었거나 ( 이므로 연산자를 스택에 push
                    s.push(str[i]);
                    break;
                case '*':
                case '/':
                    // *, / 연산자를 만난 경우, 스택에 뭐가 있는데 그게 *, /이면 우선 순위가 같으므로 result에 추가
                    while(!s.empty() && (s.top() == '*' || s.top() == '/')) {
                        result += s.top();
                        s.pop();
                    }
                    // 스택이 비었거나 우선순위가 더 낮은 +, - 이므로 연산자를 스택에 push
                    s.push(str[i]);
                    break;
                case ')':
                    // ) 를 만나면 ( 까지 result에 추가
                    while(s.top() != '(') {
                        result += s.top();
                        s.pop();
                    }
                    s.pop(); // 괄호 안의 내용을 다 result에 추가했으면 ( 도 pop해서 날려준다.
                    break;
            }
        }
    }
    while(!s.empty()) {
        result += s.top();
        s.pop();
    }
    cout << result <<"\n";
}

2. if else문을 이용한 풀이

#include <iostream>
#include <stack>
#include <string>
using namespace std;
 
int main() {
 
    string str;
    cin >> str;
    stack<char> stack;
    string result;
 
    for(int i=0; i<str.length(); i++) {
        // +, - 기호를 만난 경우
        if(str[i] == '+' || str[i] == '-') {
            while(!stack.empty() && stack.top() != '(') {
                result += stack.top();
                stack.pop();
            }
            stack.push(str[i]);
        }
        // *, / 기호를 만난 경우
        else if(str[i] == '*' || str[i] == '/') {
            while(!stack.empty() && (stack.top() == '*' || stack.top() == '/')) {
                result += stack.top();
                stack.pop();
            }
            stack.push(str[i]);
        }
        // 여는 괄호를 만난 경우
        else if(str[i] == '(') {
            stack.push(str[i]);
        }
        // 닫는 괄호를 만난 경우
        else if(str[i] == ')') {
            while(stack.top() != '(') {
                result += stack.top();
                stack.pop();
            }
            stack.pop();
        }
        // 피연산자를 만난 경우
        else {
            result += str[i];
        }
    }
    while(!stack.empty()) {
        result += stack.top();
        stack.pop();
    }
    cout << result << "\n";
    return  0;
}

References

https://kks227.blog.me/220777103650

http://jaimemin.tistory.com/828

제 글이 도움이 되셨다면 간단하게 '공감', '댓글' 부탁드립니다!