問題
수식은 보통 두 개의 피연산자 사이에 연산자가 들어가 있는 방식으로 표현한다(이를 infix notation이라고 부른다).
예를 들어, (x+y)*(z-w)와 같은 식들이 infix notation(중위표기법)으로 표현된 것이다.
그렇지만 어떤 경우에는 postfix notation(후위표기법)으로 수식을 쓰는 것이 훨씬 간편한 때가 있다.
이런 경우에는 괄호가 전혀 필요치 않다. xy+zw-*가 위의 식을 postfix notation(후위표기법)으로 표현한 것이다.
postfix notation(후위표기법)으로 표현된 식을 계산하는 방법은 간단하다.
스택을 이용하는 것이다.
스택은 아래의 두 가지 연산을 제공한다.
1) push : 스택의 맨 위에 원소를 집어넣는다. 2) pop : 스택의 맨 위에 있는 원소를 뺀다.
postfix 식을 계산하기 위해서 다음과 같은 알고리즘을 사용할 수 있다.
1) 피연산자를 만나면 push한다. 2) 어떤 연산자 O를 만나면 두 번 pop 한다.
이 때 첫 번째로 pop된 원소를 b, 두 번째로 pop된 원소를 a라 하고,
a O b를 스택에 push한다(연산자는 교환 법칙이나 결합 법칙 등의 연산 법칙이 성립하지 않는다고 가정하자.
따라서 a와 b의 순서는 절대 바꿀 수 없다). 3) 식의 모든 연산자와 피연산자를 처리한 뒤 스택에 남는 원소는 단 하나 뿐이고, 이 원소가 식을 계산한 후의 결과이다.
자, 그럼 이번에는 스택이 아니라 큐를 이용한 연산 방법을 생각해 보자.
큐 역시 push와 pop이 가능하지만 스택과는 약간 차이가 있다.
1) push : 큐의 맨 뒤에 원소를 집어넣는다. 2) pop : 큐의 맨 앞에 있는 원소를 뺀다.
식을 계산하는 알고리즘은 스택을 사용하는 알고리즘이랑 같다고 하자.
여러분은 postfix notation(후위표기법)으로 표현된 식을 입력으로 받아서,
이 식이 스택이 아닌 큐에서 동작하도록 식을 수정해야 한다.
輸入
첫 번째 줄부터 열 번째 줄까지 각 줄에 postfix notation으로 표현된 식이 입력된다. 각 식은 공백이 없는 10,000자 이하의 문자열이다. 문제를 간단하게 하기 위해 영어 소문자는 숫자로, 영어 대문자는 연산자로 가정한다.
輸出
첫 번째 줄부터 열 번째 줄까지 각 줄에 식을 변환한 결과를 출력한다. 각 식의 길이는 원래 식의 길이와 정확히 일치해야 한다. 앞서 우리가 연산자의 교환 법칙 결합 법칙이 성립하지 않는다고 했기 때문에 답은 반드시 단 하나이다.
範例
xyPzwIM
abcABdefgCDEF
...(이후 8줄)
wzyxIPM
gfCecbDdAaEBF
...(이후 8줄)
需要登入才能撰寫程式碼。