문제
당신은 수식을 독특한 방식으로 계산해야 한다. 수식을 계산하는 방식은 다음과 같다.
수식에서 맨 앞의 연산자, 또는 맨 뒤의 연산자 먼저 계산한다. 단, 음수의 부호는 연산자로 취급하지 않는다.
곱셈, 나눗셈을 덧셈, 뺄셈보다 더 먼저 계산한다.
연산자의 우선순위가 같다면 해당 연산자를 계산했을 때 결과가 큰 것부터 계산한다.
계산했을 때 결과 값 또한 같다면 앞에 것을 먼저 계산한다.
예를 들어서 수식이 3 × 2 + 5 − 5 + 7으로 주어진다고 하면 다음과 같이 계산된다.3 × 2와 5 + 7 중에서 계산 우선순위가 더 높은 ×를 먼저 계산한다. 이후 계산식은 6 + 5 − 5 + 7이다.
앞뒤의 연산자가 같으므로 6 + 5와 5 + 7을 비교했을 때, 5 + 7이 더 크기 때문에 뒤에 있는 +를 먼저 계산한다. 이후 계산식은 6 + 5 − 12이다.
뺄셈과 덧셈의 우선순위가 같으므로 6 + 5와 5 − 12를 비교했을 때, 6 + 5가 더 크기 때문에 +를 먼저 계산한다. 이후 계산식은 11 − 12가 된다.
11 − 12를 계산하면 최종 결과 값은 −1이 된다.
수식은 반드시 수와 연산자가 번갈아 가면서 나온다. 마지막에 연산자가 있는 경우는 존재하지 않으며, 맨 앞을 제외하고 음수가 들어오는 경우도 존재하지 않는다. 즉, −1 − 1 같은 경우는 나올 수 있으나, 2 + −3 같은 경우는 존재하지 않는다고 가정해도 된다. 그리고 불필요한 0이 앞에 있을 수 있다. 즉, 001 + 0002 같은 수식이 나올 수 있다.또한, 이 문제에서의 나눗셈은 C++에서 정수 간에 정의된 나눗셈으로 생각한다. 즉, 나누어지는 수가 양수면 나머지가 0 이상, 음수면 나머지가 0 이하로 처리가 되는 식으로 진행했을 때 나오는 몫을 계산하는 방식으로 이루어진다. 예를 들어, 3 / 2 = 1, (−3) / 2 = −1, 3 / (−2) = −1, (−3) / (−2) = 1로 계산된다.
이와 같은 계산 과정에 따라 주어진 식을 계산하시오.
입력
숫자, '+', '*', '-', '/'로만 이루어진 길이가 106 이하인 수식이 주어진다. 계산 과정 중의 모든 수는 −263 이상 263 미만이며, 0으로 나누는 경우는 없다. 숫자 앞에 불필요한 0이 있을 수 있다.
출력
주어진 식을 계산한 결과 값을 출력한다. 불필요한 0은 제거해야 한다.
풀이
빡구현문제이다.
앞뒤로 체크해야되므로 덱을 사용하면 편리하다.
굳이 신경써야할 점이라면
- 숫자 앞에 쓸데없는 0이 붙을 수 있다
-> string to int function을 사용하면 자동으로 지워준다. - 숫자의 범위
-> int의 범위가 넘으므로 stoll, longlong을 사용해 주면 된다.
정답 코드
#include <iostream>
#include <algorithm>
#include <string>
#include <deque>
using namespace std;
string s, n;
int cf;
deque<long long>num;
deque<char>oper;
int main(){
cin>>s;
for(int i=0; i<s.size(); i++){
if(i == 0 && s[i] == '-'){
cf = 1;
continue;
}
if(s[i] <='9' && s[i] >='0'){
n.push_back(s[i]);
}else{
if(cf == 1){
num.push_back(-1 *stoll(n));
cf = 0;
}else
num.push_back(stoll(n));
n.clear();
oper.push_back(s[i]);
}
}
if(!n.empty() && cf == 1)
num.push_back( -1 *stoll(n));
else if(!n.empty())
num.push_back(stoll(n));
while(!oper.empty()){
// for(auto e : num){
// cout<<e<<' ';
// }
// cout<<endl;
// for(auto o : oper){
// cout<<o<<' ';
// }
//cout<<endl;
if(oper.size() == 1){
long long ln1 = *num.begin(), ln2 = *(num.begin()+1), r1;
if(oper.front()=='*')
r1 = ln1*ln2;
else if(oper.front()=='/')
r1 = ln1/ln2;
else if(oper.front()=='+')
r1 = ln1+ln2;
else
r1 = ln1-ln2;
num.push_front(r1);
break;
}
int c1 =0, c2 = 0;
if(oper.front()=='*'||oper.front()=='/') c1 = 1;
if(oper.back()=='*'||oper.back()=='/') c2 = 1;
if(c1 == c2){
long long ln1 = *num.begin(), ln2 = *(num.begin()+1);
long long rn1 = *(num.end()-1), rn2 = *(num.end()-2);
long long r1, r2;
if(oper.front()=='*')
r1 = ln1*ln2;
else if(oper.front()=='/')
r1 = ln1/ln2;
else if(oper.front()=='+')
r1 = ln1+ln2;
else
r1 = ln1-ln2;
if(oper.back()=='*')
r2 = rn2*rn1;
else if(oper.back()=='/')
r2 = rn2/rn1;
else if(oper.back()=='+')
r2 = rn2+rn1;
else
r2 = rn2-rn1;
//cout<<r1<<' '<<r2<<endl<<endl;
if(r1 >= r2){
num.pop_front();
num.pop_front();
num.push_front(r1);
oper.pop_front();
}else if(r1 < r2){
num.pop_back();
num.pop_back();
num.push_back(r2);
oper.pop_back();
}
}else if(c1 > c2){
long long n1 = num.front();
num.pop_front();
long long n2 = num.front();
num.pop_front();
if(oper.front() == '*')
num.push_front(n1*n2);
else
num.push_front(n1/n2);
oper.pop_front();
}else if(c1 < c2){
long long n1 = num.back();
num.pop_back();
long long n2 = num.back();
num.pop_back();
if(oper.back() == '*')
num.push_back(n2*n1);
else
num.push_back(n2/n1);
oper.pop_back();
}
}
cout<<num[0];
}