20936번 - 우선순위 계산기

국렬이는 두 번씩이나 계산기 문제를 내놓고 또 계산기 문제를 냈다. 이대로라면 죽을 때까지 계산기를 우려먹을 생각이고, 당신은 귀찮지만 상금을 얻기 위해서 주어진 수식을 규칙에 맞게 계산해야 한다.

입력으로 주어지는 수식은 띄어쓰기 없이 수와 연산자가 번갈아 가면서 나온다. 수식의 $i$번째 수를 $X_i$, $i$번째 연산자를 $Op_i$로 표시하면 수가 $n$개인 식을 $X_1$ $Op_1$ $X_2$ $Op_2$ ... $Op_{n-1}$ $X_n$로 표기할 수 있다. 연산자의 종류는 +, -, *, /가 있다. 마지막에 연산자가 있는 경우와 $X_i$가 음수인 경우는 입력으로 주어지지 않는다. 즉, $-1-1$, $2+-3$ 같은 경우는 입력으로 주어지지 않는다. 그리고 불필요한 $0$이 수의 앞에 있을 수 있다. 즉, $001+0002$ 같은 수식이 입력으로 주어질 수 있다.

주어진 수식을 다음 규칙에 맞게 계산할 것이다.

1. $X_i$ $Op_i$ $X_{i+1}$ 중 가장 큰 값을 갖는 $i$를 선택한다. ($1 \le i \le n-1$)
2. $X_i$ $Op_i$ $X_{i+1}$가 가장 큰 값을 갖는 $i$가 $2$개 이상인 경우, 연산자 우선순위가 높은 $Op_i$인 $i$를 먼저 선택한다. 연산자의 우선순위는 곱셈과 나눗셈이 덧셈과 뺄셈보다 앞선다.
3. $X_i$ $Op_i$ $X_{i+1}$가 가장 큰 값을 갖고 연산자 $Op_i$의 우선순위가 같은 $i$가 $2$개 이상인 경우, $i$가 가장 작은 것을 선택한다.
4. $X_i$ $Op_i$ $X_{i+1}$를 먼저 계산하고, 위의 과정을 연산자의 개수만큼 반복한다.

예를 들어서 수식이 $3 \times 2 + 5 - 5 + 7$로 주어진다고 하면 다음과 같이 계산된다.

• $5 + 7 = 12$가 가장 크기에 먼저 계산한다. 이후 계산식은 $3 \times 2 + 5 - 12$이다.
• 그다음으로 $2 + 5 = 7$를 계산한다. 이후 계산식은 $3 \times 7 - 12$이다.
• 그 후 $3 \times 7 = 21$를 계산한다. 이후 계산식은 $21 - 12$이다.
• 마지막에 남은 $21 - 12$를 계산하면 최종 결과 값은 $9$가 된다.

이 문제에서의 나눗셈은 C++에서 정수 간에 정의된 나눗셈으로 생각한다. 즉, 나누어지는 수가 양수면 나머지가 $0$ 이상, 음수면 나머지가 $0$ 이하로 처리가 되는 식으로 진행했을 때 나오는 몫을 계산하는 방식으로 이루어진다. 예를 들어, $3 / 2 = 1$, $(-3) / 2 = -1$, $3 / (-2) = -1$, $(-3) / (-2) = 1$로 계산된다.

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

다음과 같이 입력이 주어진다.

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

• $S$는 계산하고자 하는 수식으로 지문에서 언급된 수와 연산자가 다른 문자 없이 교대로 나오며, 길이는 $200\,000$ 이하이다.
• 계산 과정 중의 모든 수는 $-2^{63}$ 이상 $2^{63}$ 미만이며, $0$으로 나누는 경우는 없다. 수 앞에 불필요한 $0$이 있을 수 있다.
• 주어지는 연산자는 +, -, *, /다.