[C++] 2020 카카오 인턴십 - 수식 최대화

https://school.programmers.co.kr/learn/courses/30/lessons/67257

프로그래머스

 

 

 

#include <bits/stdc++.h>

int value[3];
bool used[3];
std::unordered_map<std::string, int> prior;


std::string toPostfix(std::string expression) {
    std::string postfix;
    std::stack<std::string> st;
    std::string num;
    
    /*
    1. 숫자는 그대로 출력한다.
    2. 만약 스택이 비어있다면 연산자를 그냥 스택에 넣는다.
    3. (스택의 top에 있는 연산자의 우선순위 < 현재 연산자의 우선순위) 이면 현재 연산자를 그냥 스택에 넣는다.
    4. (스택의 top에 있는 연산자의 우선순위 >= 현재 연산자의 우선순위) 이면 2번 혹은 3번 상황이 될 때까지 pop 하여 출력하고 연산자를 스택        에 넣는다.
    5. 모든 수식을 다 사용했다면 스택이 빌 때까지 pop하여 출력한다.
    6. 우선순위는 (더하기=빼기) < (곱하기=나누기)이다.
    */

    for (char ch : expression){
        if (ch >= '0' && ch <= '9'){
            num += ch;
        }
        else {
            postfix += num;
            postfix += " ";
            num.clear();
            std::string oper;
            oper.push_back(ch);
            
            if (st.empty()) {
                st.push(oper);
            }
            else {
                if (prior[oper] > prior[st.top()]) {
                    st.push(oper);
                }
                else {
                    while(!st.empty() && prior[oper] <= prior[st.top()]) {
                        postfix += st.top();
                        postfix += " ";
                        st.pop();
                    }
                    st.push(oper);
                }
            }
        }
    }
    
    if (num.size() != 0) {
        postfix += num;
        postfix += " ";
    }
    
    while(!st.empty()) {
        postfix += st.top();
        postfix += " ";
        st.pop();
    }
    return postfix;
}

long long solve(std::string expression) {
    expression = toPostfix(expression);
    /*
    1. 숫자는 스택에 그냥 추가한다.
    2. 연산자가 나오면 숫자 2개를 pop 해서 계산한다.
    3. 이때 먼저 pop 되는 숫자가 두 번째 값, 나중에 pop되는 숫자가 첫 번째 값으로 하여 계산해야 한다. 계산한 값은 다시 스택에 넣는다.
    */
    std::stack<long long> st;
    std::stringstream ss;
    ss.str(expression);
    std::string token;
    
    while(ss >> token) {
        if (token == "+"){
            long long num1 = st.top(); st.pop();
            long long num2 = st.top(); st.pop();
            st.push(num2 + num1);
        }
        else if(token == "-"){
            long long num1 = st.top(); st.pop();
            long long num2 = st.top(); st.pop();
            st.push(num2 - num1);
        }
        else if (token == "*"){
            long long num1 = st.top(); st.pop();
            long long num2 = st.top(); st.pop();
            st.push(num2 * num1);
        }
        else {
            st.push(std::stoll(token));
        }
    }
    
    // std::cout << std::abs(st.top()) << "\n";
    return std::abs(st.top());
}


void BT(int depth, std::string expression, long long & answer) {
    if (depth == 3) {
        prior["+"] = value[0];
        prior["-"] = value[1];
        prior["*"] = value[2];
        answer = std::max(answer, solve(expression));
        return;
    }
    
    for (int i = 0; i < 3; ++i) {
        if (!used[i]) {
            used[i] = true;
            value[depth] = i;
            BT(depth + 1, expression, answer);
            used[i] = false;
        }
    }
}


long long solution(std::string expression) {
    
    long long answer = 0;
    
    BT(0, expression, answer);
  
    return answer;
}

 

 

 

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

1. 숫자는 그대로 출력한다.

2. 만약 스택이 비어있다면 연산자를 그냥 스택에 넣는다.
3. (스택의 top에 있는 연산자의 우선순위 < 현재 연산자의 우선순위) 이면 현재 연산자를 그냥 스택에 넣는다.
4. (스택의 top에 있는 연산자의 우선순위 >= 현재 연산자의 우선순위) 이면 2번 혹은 3번 상황이 될 때까지 pop 하여

     출력하고 연산자를 스택에 넣는다.

5. 모든 수식을 다 사용했다면 스택이 빌 때까지 pop하여 출력한다.

6. 우선순위는 (더하기=빼기) < (곱하기=나누기)이다.

 

 

 

후위표기식 계산

 

1. 숫자는 스택에 그냥 추가한다.

2. 연산자가 나오면 숫자 2개를 pop 해서 계산한다.

3. 이때 먼저 pop 되는 숫자가 두 번째 값, 나중에 pop되는 숫자가 첫 번째 값으로 하여 계산해야 한다. 계산한 값은 다시 스택에 넣는다.