중위표기식(법)을 후위표기식(법)으로 변환 1 timer 1s memory 256MB

수학식에서 일반적으로 사용하는 식은 중위표기식으로 연산자를 피연산자의 중간에 사용한다.

예를 들어 1+2*3 또는 (1+2)*3 과 같이 표기하는 것이다.

중위표기식에서는 위 식에서와 같이 '+', '-' 연산을 

'*', '/'보다 우선적으로 처리하는 것이 필요한 경우

괄호를 이용하여 계산의 우선순위를 표현한다.

그런데 같은 의미를 갖지만 연산의 우선순위를 위하여 괄호라는

부가적인 연산자가 필요 없는 후위표기식도 있다.

​후위표기식은 ​컴퓨터가 구문 분석하기에 ​중위표기법보다 수월하다.

예를 들어 중위표기식 1+2*3 의 경우

후위표기식으로 나타내면 123*+ 로 표현된다.

식을 아래 그림과 같이 나타낼 때, 이진트리의 중위순회, 후위순회와 같다.

중위표기식 (1+2)*3의 경우

후위표기식으로 나타내면 1 2 + 3 * 가 된다.

식을 아래 그림과 같이 나타낼 때, 이진트리의 중위순회, 후위순회와 같다.​

중위표기식을 후위표기식으로 변환하는 프로그램을 생각해보자.

입력데이터가 중위표기식이고 출력결과가 후위표기식이라고 할 경우

변환 프로세스는 다음과 같다.

중위표기식을 순회하면서 스택을 이용하여 후위표기식을 출력할 수 있다.

연산자 우선순위는 */가 가장 높고,  +-​가 중간, ()​이 가장 낮다.​

1. 현재 문자가 숫자 문자인 경우 출력한다.

2. 현재 문자가 연산자인 경우 

(1) 현재 문자가 '('라면 스택에 담는다.

(2) 현재 문자가 ')' 라면 '(' 직전 까지 스택에 담긴 모든 연산자를 출력한다.    스택에서 '(' 를 제거한다.

(3) 스택이 비었거나 스택의 top문자가 현재 문자보다 우선순위가 낮은 경우

    현재 문자를 스택에 담는다.​ ​ 

(4) 스택의 top문자가 현재 문자보다 우선순위가 높거나 같은 동안     스택의 top문자를 출력하고 현재 문자를 스택에 담는다. 

3.처리할 중위표기식이 없고 스택에 연산자가 남아 있다면 모두 꺼내어 출력한다.