[백준/C++] 19591번 독특한 계산기

문제

 

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

---

Algorithm

1. 문자열을 파싱해 수와 연산자를 분리한다.
수는 vector에 push하고
연산할 수의 위치를 나타내는 변수left , right도 선언한다.
연산자는 맨 앞 혹은 맨 뒤의 것이 수행되므로, deque에 push한다.

2. 문제의 조건에 따라 연산을 진행한다.
앞의 연산자가 수행될 경우 vector[left]와 vector[left+1]를 연산하고, 뒤의 연산자가 수행될 경우 vector[right-1]와 vector[right] 연산한다.
연산 결과는 각각 vector[left+1]과 vector[right-1]에 담긴다.


- 문자열은 어떻게 파싱하는가?
1. 문자열을 순회하며 첫 번째 연산자를 제외하고, 연산자가 나올 때까지 문자열 token에 붙인다.
  - 첫 번째 수가 음수일 수 있으므로 첫 번째 연산자는 제외한다.
2. 연산자를 만났다면, token은 수이므로 vector에 넣고, 연산자는 deque에 push한다.
3. 문자열 끝까지 1 2를 반복한다.
4. 아직 vector에 삽입되지 않은 마지막 수, 즉 token을 삽입한다.

 

---

Code

#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

string str;

typedef long long ll;
vector<ll> num;
deque<char> oper;

void INPUT()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> str;
}

bool oper1(char c)
{//mult or div
    return c=='*'||c=='/';
}
bool oper2(char c)
{//plus or minus
    return c=='+'||c=='-';
}

void Parsing()
{//수와 연산자 분리

    string token = "";
    for(int i = 0; i < str.length(); i++)
    {
        //연산자라면
        if(i && (oper1(str[i]) || oper2(str[i])))
            num.push_back(stoll(token)),
                    token = "",
                    oper.push_back(str[i]);
            //수라면
        else token += str[i];
    }num.push_back(stoll(token));
}

ll calc(ll a, ll b, char c)
{
    switch(c)
    {
        case '*' : return a*b;
        case '/' : return a/b;
        case '+' : return a+b;
        case '-' : return a-b;
    }
}

void SOLVE()
{
    Parsing();

    //연산자가 없는 경우
    if(oper.empty()) cout << num[0];

    ll left = 0 , right = num.size()-1;
    while(!oper.empty())
    {
        //마지막 연산
        if(oper.size() == 1)
        {
            ll ans = calc(num[left],num[left+1],oper.front());
            cout << ans;
            return;
        }

        //왼쪽의 우선순위가 높은 경우
        if(oper1(oper.front()) && oper2(oper.back()))
        {
            num[left+1] = calc(num[left],num[left+1],oper.front());
            left++;
            oper.pop_front();
        }
            //오른쪽의 우선순위가 높은 경우
        else if(oper2(oper.front()) && oper1(oper.back()))
        {
            num[right-1] = calc(num[right-1],num[right],oper.back());
            right--;
            oper.pop_back();
        }
            //우선순위 같은 경우
        else
        {
            ll tempL = calc(num[left],num[left+1],oper.front());
            ll tempR = calc(num[right-1],num[right],oper.back());

            //앞의 연산값이 크거나 같은 경우 앞에 먼저
            if(tempL >= tempR)
                num[left+1] = tempL , left++ , oper.pop_front();
            else num[right-1] = tempR , right-- , oper.pop_back();
        }
    }
}

int main()
{
    INPUT();
    SOLVE();
}