[Algorithm][Postfix Notation]후위표기법

계산기를 만들어라는 교수의 과제가 들어온적이 있었다.

사실 그 때는 수업이라면 질색이라 출튀를 밥먹듯하는 시절이였기에 필자는 수업을 째버렸다.

그리고 필자 식대로 과제를 제출해 내갔는데 이게 생각보다 만만치 않았다. 난이도는 헬 그 자체였다.

일단 필자가 어떠한 방식으로 풀었는지 말해주겠다.

조건

1. 연산자 우선순위 적용

2. 괄호 사용가능

3. 들어오는 값은 한줄짜리 문자열로 각각의 기호는 스페이스로 나눠져서 받는다.

풀이 과정

1.먼저 문자열을 토크나이징 해서 배열에 담는다.

2.배열 처음부터 시작해서 원소 셋을 비교해서 1번째가 숫자, 2번째가 곱하기나 나누기, 3번째가 숫자인지 확인한다. 맞다면 1번째에 연산한 결과를 넣고 2번째와 3번째를 배열에서 지운다.

3.배열 처음부터 시작해서 원소 넷을 비교해서 1번째가 곱하기 나누기, 2번째가 숫자, 3번째가 더하기나 빼기, 4번째가 숫자인지 확인한다. 맞다면 2번째에 연산한 결과를 넣고 3번쨰와 4번쨰를 배열에서 지운다.

4.배열 처음부터 시작해서 원소 둘을 비교해서 1번째가 빼기, 2번째가 숫자인지 확인한다. 맞다면 1번째에 둘을 연산한 결과를 넣고 2번쨰를 배열에서 지운다.

5.배열 처음부터 시작해서 원소 셋을 비교해서 1번째가 여는괄호, 2번째가 숫자, 3번째가 닫는 괄호인지 확인한다. 맞다면 1번째에 2번쨰 숫자를 넣고 2번째, 3번째를 배열에서 지운다.

6.2~4번을 배열의 원소가 5개 이하가 될때까지 반복한다.(계속 반복하면 배열) 보통 특수 케이스에 걸려서 5개 혹은 3개가 남는다. 운좋으면 한방에 끝난다.

애당초 원소를 4개연산한 더하기 케이스는 원소가 3개 된 케이스를 연산할 수 없다. 그래서 3개됬을때 특별히 연산을 실행해준다.

7.위의 과정이 배열의 크기가 한개가 될때까지 반복한다.

8.루프종료후 배열의 1번째 원소가 계산결과.

실제로 해보면 예외가 좀더 있어서 조금 더 토악질 나오는 난이도가 된다. 어쩃든 시간만 많이 들이면 구현은 되고 정상 작동은 한다.

시간 복잡도가 개 똥 쓰레기가 될뿐,

이를 해결하기 위해서 등장한게 있다. 바로 후위 표기법 이다.

void tokenize_input(string str) {
    char *sep = " ";
    char *tok;

    char temp_str[MAXSIZE];

    strcpy(temp_str, str.c_str());
    tok = strtok(temp_str, sep);

    while (tok != nullptr) {
        input.push_back(string(tok));
        tok = strtok(nullptr, sep);
    }

}

일단 받은 문자열을 잘라내보자.

bool is_digit(string str) {
    return atoi(str.c_str()) != 0 || str.compare("0") == 0;
}

bool is_add_sub(string str) {
    return str.compare("+") == 0 || str.compare("-") == 0;
}

bool is_mul_div(string str) {
    return str.compare("*") == 0 || str.compare("/") == 0;
}

그리고 함수 세개를 만든다. 굳이 안만들어도 되는데 결론은 숫자를 판단하는 함수, 덧셈뺄셈을 판단하는 함수, 곱셈나눗셈을 판단하는 함수를 만든다.

그리고 아래와 같은 자료구조를 만들자. 각각은 배열로 만드는게 적당한데 그 이유는 stack으로 만드나 배열로 만드나 똑같기 때문이다.

output - 출력할 배열, 후위표기법을 모아둔 배열이다.

stack - 기호를 임시 저장할 배열

if (is_digit(atom)) {
    output.push_back(atom);
} else {
    if (stack.empty()) {
        stack.push_back(atom);
    } else {
        if(is_mul_div(atom)){
            while(!stack.empty() && is_mul_div(stack.back())){
                output.push_back(stack.back());
                stack.pop_back();
            }
            stack.push_back(atom);
        }else if(is_add_sub(atom)){
            while(!stack.empty() && (is_mul_div(stack.back()) or is_add_sub(stack.back()))){
                output.push_back(stack.back());
                stack.pop_back();
            }
            stack.push_back(atom);
        }else if(atom.compare("(")==0){
            stack.push_back(atom);

        }else{
            while(!stack.empty() && stack.back().compare("(")!=0){
                output.push_back(stack.back());
                stack.pop_back();
            }
            stack.pop_back();
        }
    }
}

그리고 이제 후위표기법으로 바꿔보자. 코드는 길어보이지만 판단하는 로직은 위와 같다.

atom은 쪼개진 각각의 숫자 혹은 기호 혹은 괄호이다.

1.현재 배열에 들은 원소(atom)가 숫자면 일단 output에 넣는다.

일단 숫자인지를 먼저 판단해야한다.

if(is_mul_div(atom)){
    while(!stack.empty() && is_mul_div(stack.back())){
        output.push_back(stack.back());
        stack.pop_back();
    }
    stack.push_back(atom);
}else if(is_add_sub(atom)){
    while(!stack.empty() && (is_mul_div(stack.back()) or is_add_sub(stack.back()))){
        output.push_back(stack.back());
        stack.pop_back();
    }
    stack.push_back(atom);
}else if(atom.compare("(")==0){
    stack.push_back(atom);

}else{
    while(!stack.empty() && stack.back().compare("(")!=0){
        output.push_back(stack.back());
        stack.pop_back();
    }
    stack.pop_back();
}

2.만약 숫자가 아니면서 곱셈과 나눗셈이라면,

스택을 확인해서 스택에 있는 모든 곱셈,나눗셈기호를 빼서 output에 넣는다.

그 후 현재 기호를 stack에 넣는다.

이 부분에서 의아할 수 있는데 현재 원소를 output에 바로 넣지 않는다.

일단 stack에 넣는데 스택에 넣기전에 stack안의 곱셈 나눗셈을 차례로 빼낸다.

중요한건 곱셈 나눗셈만 빼낸다는 것이다. 덧셈,뺄셈이나 괄호는 빼지 않는다.

if(is_mul_div(atom)){
    while(!stack.empty() && is_mul_div(stack.back())){
        output.push_back(stack.back());
        stack.pop_back();
    }
    stack.push_back(atom);
}

3.만약 숫자가 아니면서 덧셈과 뺄셈이라면

스택을 확인해서 스택에 있는 모든 곱셈,나눗셈,덧셈,뺄셈기호를 빼서 output에 넣는다.

그 후 현재 기호를 stack에 넣는다.

덧셈과 뺄셈일 경우에는 모든 연산자를 다 뺀다. 단 괄호는 남겨둔다.

else if(is_add_sub(atom)){
    while(!stack.empty() && (is_mul_div(stack.back()) or is_add_sub(stack.back()))){
        output.push_back(stack.back());
        stack.pop_back();
    }
    stack.push_back(atom);
}

4.만약 숫자가 아니면서 여는괄호라면

그냥 stack에 넣어라

이 땐 걍 스택에 넣으면된다.

else if(atom.compare("(")==0){
    stack.push_back(atom);

}else{
    while(!stack.empty() && stack.back().compare("(")!=0){
        output.push_back(stack.back());
        stack.pop_back();
    }
    stack.pop_back();
}

5.만약 숫자가 아니면서 닫는 기호라면,

여는기호가 나올때까지 모든 기호를 output에 넣어라.

여는 기호는 버린다.

while(!stack.empty()){
    output.push_back(stack.back());
    stack.pop_back();
}

6.모든 루프가 끝났어도 stack은 안비었을 가능성이 있다.

이 때 stack의 값을 output으로 옮긴다.

#include <iostream>
#include <vector>

#define MAXSIZE 2000
using namespace std;

vector<string> input;
vector<string> output;
vector<string> stack;

void print_arr(vector<string> v) {
    for (string atom:v) {
        cout << atom << " ";
    }
    cout << endl;
}

bool is_digit(string str) {
    return atoi(str.c_str()) != 0 || str.compare("0") == 0;
}

bool is_add_sub(string str) {
    return str.compare("+") == 0 || str.compare("-") == 0;
}

bool is_mul_div(string str) {
    return str.compare("*") == 0 || str.compare("/") == 0;
}

void tokenize_input(string str) {
    char *sep = " ";
    char *tok;

    char temp_str[MAXSIZE];

    strcpy(temp_str, str.c_str());
    tok = strtok(temp_str, sep);

    while (tok != nullptr) {
        input.push_back(string(tok));
        tok = strtok(nullptr, sep);
    }

}

int main() {
    string str;
    getline(cin, str);

    tokenize_input(str);

    for (string atom:input) {
        if (is_digit(atom)) {
            output.push_back(atom);
        } else {
            if (stack.empty()) {
                stack.push_back(atom);
            } else {
                if(is_mul_div(atom)){
                    while(!stack.empty() && is_mul_div(stack.back())){
                        output.push_back(stack.back());
                        stack.pop_back();
                    }
                    stack.push_back(atom);
                }else if(is_add_sub(atom)){
                    while(!stack.empty() && (is_mul_div(stack.back()) or is_add_sub(stack.back()))){
                        output.push_back(stack.back());
                        stack.pop_back();
                    }
                    stack.push_back(atom);
                }else if(atom.compare("(")==0){
                    stack.push_back(atom);

                }else{
                    while(!stack.empty() && stack.back().compare("(")!=0){
                        output.push_back(stack.back());
                        stack.pop_back();
                    }
                    stack.pop_back();
                }
            }
        }
    }
    while(!stack.empty()){
        output.push_back(stack.back());
        stack.pop_back();
    }
    print_arr(input);
    print_arr(output);
    return 0;
}
/*
10 - 5 * 7 * ( 10 / 8 + 9 * 5 * ( 14 + 7 * 5 ) ) * 9 + 14 * ( 7 + 12 ) * ( 33 * 6 )
 */

위 코드는 전문이다. 사실 stack을 사용하는게 정석이지만 vector로도 무리없게 코딩가능하기에 범용적으로 설명하고자 배열로 코딩하였다.