c++ 19591번 독특한 계산기 (백준)

#include <bits/stdc++.h>

using namespace std;

deque<long long> num;
deque<char> oper;

char level(char & op) { //연산자 우선순위
    char ret = 2; //곱하기 나누기
    if(op == '+' || op == '-') ret = 1; //더하기 빼기
    return ret;
}

long long left(char & op) { //처음 그리고 두번째 숫자의 계산
    long long ret = 0;
    if(op == '+') ret = num.front() + (*(num.begin()+1));
    else if(op == '-') ret = num.front() - (*(num.begin()+1));
    else if(op == '*') ret = num.front() * (*(num.begin()+1));
    else if(op == '/') ret = num.front() / (*(num.begin()+1));
    return ret;
}

long long right(char & op) { //마지막-1 숫자와 마지막 숫자의 계산
    long long ret = 0;
    if(op == '+') ret = (*(num.end()-2)) + num.back();
    else if(op == '-') ret = (*(num.end()-2)) - num.back();
    else if(op == '*') ret = (*(num.end()-2)) * num.back();
    else if(op == '/') ret = (*(num.end()-2)) / num.back();
    return ret;
}

void removeL(long long & tmp) { //왼쪽을 제거하는 경우
	//수를 담은 덱에선 2개를 꺼낸 다음
    num.pop_front(); 
    num.pop_front();
    oper.pop_front(); //계산에 이용된 연산자도 제거
    
    //빼낸 두 수를 계산한 값을 넣어줍니다.
    num.emplace_front(tmp);
}

void removeR(long long & tmp2) { //오른쪽을 제거하는 경우
	//수를 담은 덱에선 2개를 꺼낸 다음
    num.pop_back();
    num.pop_back();
    oper.pop_back(); //계산에 이용된 연산자도 제거
    
    //빼낸 두 수를 계산한 값을 넣어줍니다.
    num.emplace_back(tmp2);
}

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    string buf; //문자열
    cin >> buf;

    long long tmp=0, tmp2=0;
    int i=0;
    bool isMinus = false; //처음 문자가 -이면 true로 바뀝니다.
////////////////////////////////////////////////////////////////////////////
//파싱
    
    if(buf[0] == '-') { //처음 문자가 - 인가?
        isMinus = true; 
        i = 1; // - 다음부터 수와 연산자를 분리한다.
    }
    
    for(;buf[i]!=0;i++) { //수와 연산자 분리
        if(buf[i] >= 48) { //숫자가 나오면 tmp에 10을 곱한다음 이번 문자를 수로 변환해서 더해준다.
            tmp *= 10;
            tmp += buf[i]-48;
        }
        else { //연산자가 나오면 그동한 구했던 수(tmp)을 덱에 넣고 0으로 초기화 해준다. 또한 연산자도 따로 덱에 넣어준다.
            num.emplace_back(tmp);
            tmp = 0;
            oper.emplace_back(buf[i]);
        }
    }
    //마지막으로 구해진 수를 덱에 넣어준다.
    num.emplace_back(tmp); 
    tmp = 0;
    
    if(isMinus) num.front() *= -1; //처음이 - 이었다면
 //////////////////////////////////////////////////////////////////
 //왼쪽과, 오른쪽을 봅니다.
 //연산자 우선순위가 높은 쪽을 계산후, 두 수를 덱에 뺀 다음 계산값을 덱에 넣어줍니다.
 //만약 같다면 계산결과가 더 큰 쪽의 두 수를 덱에 뺀 다음 계산값을 덱에 넣어줍니다.
 //또한 계산결과도 같다면 왼쪽의 두스를 덱에 뺀 다음 그 둘의 계산값을 덱에 넣어줍니다.
 
    char op1, op2;
    
    while(!oper.empty()) { //연산자가 남아 있는게 없다면 반복문을 종료합니다.
        op1 = level(oper.front()); //왼쪽 연산자의 우선순위
        op2 = level(oper.back()); //오른쪽 연산자의 우선순위
        
        tmp = left(oper.front()); //왼쪽 계산값
        tmp2 = right(oper.back()); //오른쪽 계산값
     
        if(op1 > op2) removeL(tmp); //왼쪽의 우선순위가 더 높은 경우
        else if(op1 < op2) removeR(tmp2); //오른쪽의 우선순위가 더 높은 경우
        else { //우선순위가 서로 같은 경우
            if(tmp >= tmp2) { //계산값이 왼쪽이 같거나 더 큰 경우
                removeL(tmp); 
            } else { //계산값이 오른쪽이 더 큰 경우
                removeR(tmp2);
            }
        }
    }
    cout << num.front(); //덱에 하나남은 최종값을 출력
}

풀이 : 문자열, 덱

 

1. 수를 담을 덱과 (long long) 연산자를 담을 덱(char)을 준비합니다.

2. 문자열을 입력받으면, 여기서 수와 문자열을 분리해줍니다. 이때 가장 앞에 - 가 나오는 경우, -을 제외 한 다음, 숫자와 연산자들을 덱에 넣은 다음, 다 끝나고 나서, 수를 담은 덱의 가장 처음 노드의 값에 -1을 곱해줍니다.

3. 왼쪽, 오른쪽의 연산자들의 우선순위를 구하고, 왼쪽 오른쪽의 계산값을 구해놓습니다. 그런다음 우선순위가 높은곳을 먼저 해결(덱에서 두개를 뺀 다음, 이들의 계산값을 다시 덱에 넣음, 계산에 사용된 연산자도 덱에서 제거) 합니다. 만약 우선순위가 같다면, 왼쪽의 계산결과가 같거나 더 크다면, 왼쪽을 해결 아니라면 오른쪽을 해결합니다. 이를 덱에 있는 연산자가 남아있지 않을 때 까지 반복합니다.

4. 마지막 남은 수를 출력합니다.

 

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

19591번: 독특한 계산기