[백준 19591] 독특한 계산기

문제

www.acmicpc.net/problem/19591

19591번: 독특한 계산기

 

문제 풀이

1. 파싱 : 문자열을 숫자와 연산자로 파싱하는 과정이 까다롭지만 연산자가 나왔을 때, 연산자는 연산자대로 저장하고 그동안의 숫자들을 하나의 숫자로 묶어서 저장하면 쉽게 파싱할 수 있습니다. (첫 수가 음수일때 예외처리)

 

2. 자료구조 : 연산할 때 맨 앞과 뒤에 접근하므로 덱을 사용하여 숫자, 문자들을 관리할 수 있습니다.

 

3. 주어진 조건대로 연산자의 우선순위를 먼저 따지고, 우선순위가 같다면 (맨앞(f),맨뒤(r))의 계산결과를 비교하여 계산하면 해결할 수 있습니다.

코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
string ipt, tmp;
bool sign;
deque<ll> v;
deque<char> op;
 
int calop(char c) {
	if (c == '+' || c == '-') return 1;
	else return 2;
}
 
ll cal(int idx, char c) {
	if (c == '+') return v[idx] + v[idx + 1];
	else if (c == '-') return v[idx] - v[idx + 1];
	else if (c == '*') return v[idx] * v[idx + 1];
	else return v[idx] / v[idx + 1];
}
 
int main() {
	cin.tie(NULL); cout.tie(NULL);
	ios_base::sync_with_stdio(false);
 
	cin >> ipt;
    
	// parsing //
	for (int i = 0; i < ipt.length(); i++) {
		if (i == 0 && ipt[i] == '-') sign = 1;
		else if (ipt[i] == '+' || ipt[i] == '-' || ipt[i] == '*' || ipt[i] == '/') {
			op.push_back(ipt[i]);
			ll n = stoll(tmp);
			if (sign) sign = 0, n *= -1;
			v.push_back(n);
			tmp = "";
		}
		else tmp += ipt[i];
	}
	if (!tmp.empty()) {
		ll n = stoll(tmp);
		if (sign) sign = 0, n *= -1;
		v.push_back(n);
	}
    
	// calculate //
	while (v.size() != 1) {
		char op1 = op.front(), op2 = op.back();
		bool f = 0, r = 0;
		ll a = cal(0, op1), b = cal(v.size() - 2, op2);
		if (calop(op1) > calop(op2)) f = 1;
		else if (calop(op1) < calop(op2)) r = 1;
		else if (a >= b) f = 1;
		else r = 1;
		if (f) {
			for (int i = 0; i < 2; i++) v.pop_front();
			v.push_front(a);
			op.pop_front();
		}
		else {
			for (int i = 0; i < 2; i++) v.pop_back();
			v.push_back(b);
			op.pop_back();
		}
	}
	cout << v[0];
}