16133번 - 공학용 계산기 (Calculator) 서브태스크

문제

현석이는 기말고사 대비를 위해 화학 문제를 풀고 있다. 화학 문제를 풀던 도중 공학용 계산기를 홈베에 두고 온 것이 기억났다. 홈베에 너무 내려가기 귀찮은 현석이는 그냥 코딩을 해서 계산기를 만들기로 했다.

현석이의 계산기는 +, -, *, /, ^, (, ), # 연산자를 지원한다. 각각 덧셈, 뺄셈, 곱셈, 나눗셈, 거듭제곱, 여는 괄호와 닫는 괄호, 제곱근을 의미하며, 제곱근 연산자는 #5 또는 #(1+2) 와 같이 제곱근을 구하고자 하는 식의 앞에 붙는다. 그리고 식을 계산하기 위해서는 식을 전부 입력하고 난 뒤 마지막에 = 버튼을 눌러야 한다. 계산기가 처리할 수 있는 입력을 엄밀하게 표현하면 다음과 같다.

<input> ::= <expr> "="
<expr> ::= <term> | <term> ("+" | "-") <expr>
<term> ::= <factor> | <factor> ("*" | "/") <term>
<factor> ::= <power> | <power> "^" <factor>
<power> ::= "#" <power> | <root>
<root> ::= <num> | "(" <expr> ")"
<num> ::= "0" | <non-zero> <digit>*
<digit> ::= "0" | <non-zero>
<non-zero> ::= "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

연산자의 우선순위는 괄호 > 제곱근 > 거듭제곱 > 곱셈과 나눗셈 > 덧셈과 뺄셈 순이며, 우선순위가 같은 연산자가 여럿 있는 경우 제곱근과 거듭제곱을 제외한 연산자는 왼쪽부터 오른쪽으로, 제곱근과 거듭제곱은 오른쪽부터 왼쪽으로 계산된다. 즉 2^3^2은 2^(3^2)로 계산되고, ##32는 #(#32)로 계산된다.

현석이의 계산기는 정수 연산밖에 하지 못한다. 제곱근이나 나눗셈 연산의 결과가 정수로 맞아떨어지지 않는 경우는 대신 0 방향으로 가장 가까운 정수를 결괏값으로 취한다. 예를 들어 #17의 결과는 4이고, (2-9)/3의 결과는 -2이다.

현석이는 잠깐 코딩을 해 보다가 차라리 손으로 계산하는 게 더 빠르겠다는 생각이 들었다. 코딩을 못하는 현석이를 위해 계산기를 만들어 주자!

입력

계산해야 할 식이 주어진다. 식의 길이는 100을 넘지 않으며, 문제에 주어진 문법을 만족한다. 또한 다음과 같은 조건을 만족하는 수식만 입력으로 주어짐이 보장된다.

• 계산 과정에서 등장하는 모든 수는 부호 있는 64비트 정수형으로 나타낼 수 있다.
• 계산 과정에서 음수의 제곱근을 구하거나 어떤 수를 음수 번 거듭제곱하는 연산은 등장하지 않는다.
• 계산 과정에서 0을 0번 거듭제곱하거나 어떤 수를 0으로 나누는 연산은 등장하지 않는다.

출력

계산 결과를 출력한다.

제한

서브태스크 1 (20점)

• 괄호 없음

서브태스크 2 (30점)

• 괄호는 최대 1중으로 존재한다.

서브태스크 3 (50점)

• 추가 제한 없음

힌트