[스택] 프로그래머스 수식 최대화 C++

 

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

코딩테스트 연습 - 수식 최대화

#include <string>
#include <vector>
#include <stack>
#include <iostream>

using namespace std;

string str;
long long answer; // 자료형
int order[3], visited[3]; // +, -, * 우선순위
stack<long long> s;
stack<char> op;

int getOrder(char ch) { // 우선순위
    if (ch == '+') return order[0];
    if (ch == '-') return order[1];
    if (ch == '*') return order[2];
}

void calc() {
    long long b = s.top(); s.pop();
    long long a = s.top(); s.pop();
    char ch = op.top(); op.pop();

    if (ch == '+') s.push(a + b);
    else if (ch == '-') s.push(a - b); // 순서 조심
    else s.push(a * b);
}

void post() {
    long long temp = 0;
    for (int i = 0; i < str.size(); i++) {
        if ((str[i] >= '0') && (str[i] <= '9'))
            temp = (temp * 10) + (str[i] - '0');
        else {
            s.push(temp);
            temp = 0;
            while (!op.empty() && getOrder(str[i]) <= getOrder(op.top()))
                calc();
            op.push(str[i]);
        }
    }

    s.push(temp); // 마지막 숫자 넣기
    while (!op.empty()) calc(); // 나머지 연산자 계산
}

void dfs(int depth) {
    if (depth == 3) {
        while (!s.empty()) s.pop();
        while (!op.empty()) op.pop();
        post();
        answer = max(answer, abs(s.top())); // 절댓값
        return;
    }

    for (int i = 0; i < 3; i++) {
        if (visited[i]) continue;
        visited[i] = true;
        order[depth] = i + 1;
        dfs(depth + 1);
        visited[i] = false;
    }
}

long long solution(string expression) {
    str = expression;
    dfs(0);
    return answer;
}