19591번 - 독특한 계산기

당신은 수식을 독특한 방식으로 계산해야 한다. 수식을 계산하는 방식은 다음과 같다.

1. 수식에서 맨 앞의 연산자, 또는 맨 뒤의 연산자 먼저 계산한다. 단, 음수의 부호는 연산자로 취급하지 않는다.
2. 곱셈, 나눗셈을 덧셈, 뺄셈보다 더 먼저 계산한다.
3. 연산자의 우선순위가 같다면 해당 연산자를 계산했을 때 결과가 큰 것부터 계산한다.
4. 계산했을 때 결과 값 또한 같다면 앞에 것을 먼저 계산한다.

예를 들어서 수식이 3 × 2 + 5 − 5 + 7으로 주어진다고 하면 다음과 같이 계산된다.

1. 3 × 2와 5 + 7 중에서 계산 우선순위가 더 높은 ×를 먼저 계산한다. 이후 계산식은 6 + 5 − 5 + 7이다.
2. 앞뒤의 연산자가 같으므로 6 + 5와 5 + 7을 비교했을 때, 5 + 7이 더 크기 때문에 뒤에 있는 +를 먼저 계산한다. 이후 계산식은 6 + 5 − 12이다.
3. 뺄셈과 덧셈의 우선순위가 같으므로 6 + 5와 5 − 12를 비교했을 때, 6 + 5가 더 크기 때문에 +를 먼저 계산한다. 이후 계산식은 11 − 12가 된다.
4. 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로 계산된다.

이와 같은 계산 과정에 따라 주어진 식을 계산하시오.

숫자, '+', '*', '-', '/'로만 이루어진 길이가 10⁶ 이하인 수식이 주어진다. 계산 과정 중의 모든 수는 −2⁶³ 이상 2⁶³ 미만이며, 0으로 나누는 경우는 없다. 숫자 앞에 불필요한 0이 있을 수 있다. 

주어진 식을 계산한 결과 값을 출력한다. 불필요한 0은 제거해야 한다.