수식은 보통 두 개의 피연산자 사이에 연산자가 들어가 있는 방식으로 표현한다(이를 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(후위표기법)으로 표현된 식을 입력으로 받아서,

이 식이 스택이 아닌 큐에서 동작하도록 식을 수정해야 한다.

표현식 timer 1s memory 256MB

표현식 1s 256MB