폴란드 표기법
면접 대비시간 제한2초메모리 제한1024 MB
정수와 한 글자 변수, +, -, *로 이루어진 전위 표기식을 읽고 변수가 없는 부분식을 계산된 값으로 바꾼 뒤 전위 표기법으로 출력한다.
문제
수학적 수식을 나타내는 방법 중 하나로 폴란드 표기법(또는 전위 표기법)이 있다. 이 표기법은 논리학에서 사용하기 위해 Jan Łukasiewicz(1878-1956)가 처음 개발했다. 이 표기법에서는 연산자가 피연산자 앞에 온다. 예를 들어, 중위 표기법으로
3 + 4 ∗ 7
이라고 쓰는 대신, 폴란드 표기법으로 동등한 식을 다음과 같이 쓸 수 있다.
+ 3 ∗ 4 7
이 예에서 덧셈은 뒤따르는 두 식 '3'과 '* 4 7'의 값에 적용된다. 또한 곱셈은 그 뒤에 오는 두 값 4와 7에 적용된다.
일반적으로 폴란드 표기법으로 식을 작성하는 규칙은 다음과 같다.
- 정수 상수는 식이다(예: 3).
- 소문자 한 글자는 식이다(변수, 예: x).
- E1과 E2가 식이고 OP가 연산자이면, 'OP E1 E2'는 식이다. 이 식의 중위 표기법에서의 의미는 'E1 OP E2'이다.
지원하는 연산자는 모두 이항 연산자로, 덧셈(+), 뺄셈(-), 곱셈(*)이다.
폴란드 표기법은 컴퓨터가 구문 분석하기 쉽다는 장점이 있다. 폴란드 표기법으로 된 식을 읽고, 가능한 한 많이 간소화한 뒤, 폴란드 표기법으로 출력하는 프로그램을 작성하시오. 간소화는 변수를 포함하지 않는 부분식을 가능한 곳마다 그 값으로 바꾸는 것이다.
입력
각 테스트 케이스는 식을 담은 한 줄로 주어진다. 식은 공백으로 구분된 토큰(정수, 연산자, 한 글자 소문자 변수)의 나열이다. 각 식은 폴란드 표기법으로 올바르게 구성되며, 기호(연산자와 피연산자를 합쳐)의 개수는 최대 2048개이다. 정수 상수는 [−10, 10] 범위이다.
출력
각 케이스마다 케이스 번호를 출력한 뒤, 간소화된 식을 폴란드 표기법으로 입력과 같은 형식으로 출력한다. 앞서 설명한 간소화 외에는 식을 수정하지 않는다. 모든 중간 계산 결과는 부호 있는 32비트 정수 범위에 들어간다. 출력 형식은 아래 예시를 따른다.