[Programmers] Lv2. 수식 최대화 | C++

🔗문제 보러가기

프로그래머스

 

👨‍💻풀이 과정

 

자료구조 시간에 전위표기식(Prefix), 중위표기식(Infix), 후위표기식(Postfix)에 대해 배운 적이 있으나, 시간이 오래되어 기억이 잘 안 나더라구요. 그래서 다시 한 번 찾아봤습니다.

 

컴파일러가 연산자 우선순위에 따라 중위표기식을 후위표기식으로 변환한 후에, 계산을 진행한다고 하더라구요. 숲을 보지 못하고 나무만 볼 수 있는 컴퓨터 입장에선 수식을 왼쪽에서 오른쪽으로 차례대로 읽어가며 계산하는 게 편하죠. 그에 반해, 사람은 숲을 볼 수 있습니다. 눈으로 전체 수식을 한 번에 볼 수 있기 때문이죠.

 

따라서, 중위표기식을 후위표기식으로 바꾸는 과정을 진행해야 합니다. 그리고, 연산자 우선순위 순열도 만들어야 하죠.

저는 다음과 같은 순서대로 진행했습니다.

 

 

1. 주어진 수식을 피연산자, 연산자 별로 토큰화

 

예제에서 주어진 입력 "100-200*300-500+20"으로 보자면, ["100", "-", "200", "*", "300", "-", "500", "+", "20"]으로 각각 분리해야 합니다. 또한, 수식에 등장하는 연산자의 종류가 무엇 무엇이 있는지도 알아놔야 하죠. 등장하는 연산자가 최대 3개 뿐이라 3! = 6가지의 연산자 우선순위 경우의 수밖에 안 나오지만, 저는 그 마저도 줄이고 싶었습니다.

 

set을 이용하여 등장하는 연산자 종류 수를 중복없이 저장해놨고, 분리된 수식을 가지고 있는 Expression 클래스를 만들었습니다.

class Expression {
public:
    Expression(const string& expression) {
        string digitBuffer;

        for (const auto element : expression) {
            if (isdigit(element)) {
                digitBuffer.push_back(element);
                continue;
            }

            _operatorTypes.insert(element);
            _splitedExpression.push_back(digitBuffer);

            string _operator;
            _operator.push_back(element);

            _splitedExpression.push_back(_operator);
            digitBuffer.clear();
        }

        _splitedExpression.push_back(digitBuffer);
    }

public:
    vector<string> _splitedExpression;
    set<char> _operatorTypes;
};

 

 

2. 연산자 우선순위 순열 만들기

 

등장하는 연산자 종류 수가 최대 3개이기 때문에 최대 6가지의 경우의 수가 존재합니다. 순열을 사용하기 위해 <algorithm> 헤더의 next_permutation()을 사용했는데, 오름차순으로 정렬된 시퀀스 컨테이너를 넣어야 함수가 올바르게 작동합니다.

 

하지만 BST 기반인 set은 순회를 오름차순으로 시작하죠! 그래서 set을 순회하며 string에 차례대로 담았고, next_permutation()의 결과를 차례대로 결과에 담았습니다.

vector<map<char, int>> GetOperatorsPermutation(set<char> operators) {
    string strOpreators;
    vector<map<char, int>> results;

    for (const auto _operator : operators)
        strOpreators.push_back(_operator);

    do {
        map<char, int> priority;

        for (int i = 0; i < strOpreators.length(); i++)
            priority[strOpreators[i]] = i;

        results.push_back(priority);
    } while (next_permutation(strOpreators.begin(), strOpreators.end()));

    return results;
}

 

 

3. 중위표기식을 후위표기식으로 변환하기

 

이제 주어진 연산자 우선순위와 토큰화 된 중위표기식들을 바탕으로 후위표기식을 만들면 됩니다. 최종 결과를 담을 vector<string> postFix와 연산자를 담아 둘 stack<char> operators가 필요합니다. 후위표기식을 만드는 알고리즘은 다음과 같았습니다. (🔗참고 블로그)

 

1. 숫자는 그대로 postFix에 추가
2. 만약 스택이 비어있다면 연산자를 그냥 스택에 넣는다.
3. (스택의 top에 있는 연산자의 우선순위 < 현재 연산자의 우선순위) 이면 현재 연산자를 그냥 스택에 넣는다.
4. (스택의 top에 있는 연산자의 우선순위 >= 현재 연산자의 우선순위) 이면 2번 혹은 3번 상황이 될 때까지 pop 하여 postFix에 추가한다. 다 끝났다면 현재 연산자를 스택에 넣는다.
5. 모든 수식을 다 사용했다면, 스택이 빌 때까지 pop하여 postFix에 추가한다.

vector<string> ConvertInfixToPostFix(const vector<string>& splitedInfixExpression, const map<char, int>& operatorPriority) {
    vector<string> postFix;
    stack<char> operators;

    for (auto element : splitedInfixExpression) {
        if (isdigit(element[0])) {
            postFix.push_back(element);
            continue;
        }

        if (operators.empty()) {
            operators.push(element[0]);
            continue;
        }

        int currentOpratorPriority = operatorPriority.find(element[0])->second;
        int stackTopOperatorPriority = operatorPriority.find(operators.top())->second;

        if (stackTopOperatorPriority < currentOpratorPriority) {
            operators.push(element[0]);
        }

        else {
            while (true) {
                if (operators.empty())
                    break;

                char targetOperator = operators.top();
                int priority = operatorPriority.find(targetOperator)->second;

                if (priority < currentOpratorPriority)
                    break;

                string strOperator;
                strOperator.push_back(targetOperator);
                postFix.push_back(strOperator);
                operators.pop();
            }

            operators.push(element[0]);
        }
    }

    while (!operators.empty()) {
        char targetOperator = operators.top();
        operators.pop();

        string strOperator;
        strOperator.push_back(targetOperator);
        postFix.push_back(strOperator);
    }

    return postFix;
}

 

 

4. 후위표기식을 계산하여 이전 계산 결괏값보다 큰 지 비교한다.

 

이제 후위표기식을 순회하며 계산을 하면 됩니다. 계산하는 과정은 어렵지 않았습니다. 여기서도 숫자와 연산자를 담아 둘 stack<string>이 필요합니다. 계산 과정은 다음과 같습니다.

 

1. 숫자는 스택에 그냥 추가한다.
2. 연산자가 나오면 숫자 2개를 pop 해서 계산한다.
3. 이때 먼저 pop 되는 숫자가 두 번째 값, 나중에 pop되는 숫자가 첫 번째 값으로 하여 계산해야 한다. 계산한 값은 다시 스택에 넣는다.

 

위 과정을 후위표기식이 끝날 때까지 진행하면, 스택에 최종 계산값이 저장되어 있습니다.

long long Calculate(const vector<string>& postFixExpression) {
    stack<string> myStack;

    for (const auto element : postFixExpression) {
        if (isdigit(element[0])) {
            myStack.push(element);
            continue;
        }

        long long num2 = stoll(myStack.top());
        myStack.pop();

        long long num1 = stoll(myStack.top());
        myStack.pop();

        long long result = 0;
        switch (element[0]) {

            case '+':
                result = num1 + num2;
                break;

            case '-':
                result = num1 - num2;
                break;

            case '*':
                result = num1 * num2;
                break;
        }

        myStack.push(to_string(result));
    }

    return abs(stoll(myStack.top()));
}

 

 

✏️ 소스 코드 및 결과

#include <set>
#include <map>
#include <stack>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;


class Expression {
public:
    Expression(const string& expression) {
        string digitBuffer;

        for (const auto element : expression) {
            if (isdigit(element)) {
                digitBuffer.push_back(element);
                continue;
            }

            _operatorTypes.insert(element);
            _splitedExpression.push_back(digitBuffer);

            string _operator;
            _operator.push_back(element);

            _splitedExpression.push_back(_operator);
            digitBuffer.clear();
        }

        _splitedExpression.push_back(digitBuffer);
    }

public:
    vector<string> _splitedExpression;
    set<char> _operatorTypes;
};


vector<map<char, int>> GetOperatorsPermutation(set<char> operators) {
    string strOpreators;
    vector<map<char, int>> results;

    for (const auto _operator : operators)
        strOpreators.push_back(_operator);


    do {
        map<char, int> priority;

        for (int i = 0; i < strOpreators.length(); i++)
            priority[strOpreators[i]] = i;

        results.push_back(priority);
    } while (next_permutation(strOpreators.begin(), strOpreators.end()));

    return results;
}


vector<string> ConvertInfixToPostFix(const vector<string>& splitedInfixExpression, const map<char, int>& operatorPriority) {
    vector<string> postFix;
    stack<char> operators;

    for (auto element : splitedInfixExpression) {
        if (isdigit(element[0])) {
            postFix.push_back(element);
            continue;
        }

        if (operators.empty()) {
            operators.push(element[0]);
            continue;
        }

        int currentOpratorPriority = operatorPriority.find(element[0])->second;
        int stackTopOperatorPriority = operatorPriority.find(operators.top())->second;

        if (stackTopOperatorPriority < currentOpratorPriority) {
            operators.push(element[0]);
        }

        else {
            while (true) {
                if (operators.empty())
                    break;

                char targetOperator = operators.top();
                int priority = operatorPriority.find(targetOperator)->second;

                if (priority < currentOpratorPriority)
                    break;

                string strOperator;
                strOperator.push_back(targetOperator);
                postFix.push_back(strOperator);
                operators.pop();
            }

            operators.push(element[0]);
        }
    }

    while (!operators.empty()) {
        char targetOperator = operators.top();
        operators.pop();

        string strOperator;
        strOperator.push_back(targetOperator);
        postFix.push_back(strOperator);
    }

    return postFix;
}


long long Calculate(const vector<string>& postFixExpression) {

    stack<string> myStack;

    for (const auto element : postFixExpression) {
        if (isdigit(element[0])) {
            myStack.push(element);
            continue;
        }

        long long num2 = stoll(myStack.top());
        myStack.pop();

        long long num1 = stoll(myStack.top());
        myStack.pop();

        long long result = 0;
        switch (element[0]) {

            case '+':
                result = num1 + num2;
                break;

            case '-':
                result = num1 - num2;
                break;

            case '*':
                result = num1 * num2;
                break;
        }

        myStack.push(to_string(result));
    }


    return abs(stoll(myStack.top()));
}

long long solution(string expression) {
    Expression myExpression(expression);
    vector<map<char, int>> operatorPriorities = GetOperatorsPermutation(myExpression._operatorTypes);
    long long answer = 0;

    for (const auto priority : operatorPriorities) {
        vector<string> postFix = ConvertInfixToPostFix(myExpression._splitedExpression, priority);
        long long result = Calculate(postFix);

        if (answer < result)
            answer = result;
    }

    return answer;
}

 

 

 

기능별로 함수를 최대한 빼려고 노력 중인데, 코드 길이가 오히려 더 길어지는 느낌은 뭘까요...