중위표기식, 후위표기식(Infix, Postfix)

우리가 알고있는 식, 즉 (A+B)*C 와같은 식들은 Infix notation, 즉 중위표기법이라 부른다.

후위표기식은 위의 식을 AB+C* 와 같이 표현한다. 

후위표기식으로 바꾸는 법은 모든 항에 괄호를 씌우고 큰괄호부터 지워나가며 연산자를 그의 오른쪽 괄호와 바꿔주면 된다.

 

ex) ((A+B)*C) --> (A+B)C* --> AB+C*

왜 이런식이 존재할까.

 

 

후위표기식은 계산을 할때 괄호가 없어도 계산 순서가 일정하여 중위표기법 계산보다 후위표기법이 빠르다.

계산기나 컴퓨터 내부에서도 스택을 활용하여 중위표기법을 후위표기법으로 변환하여 연산한다.

 

아래는 컴퓨터 내부의 후위표기식을 중위표기식으로 계산하는 원리이다.

 

typedef enum 이라는 열거형 자료형으로 멋들어지게(?) 표현해놓았다.

간단히 말해 피연산자(즉,숫자)는 스택에 들어가게되며, 연산자의 경우 앞선 두개의 숫자를 POP 하여 계산을 하면된다.

 

 

 

 

 

 

 

이번에는 중위표현식을 입력받아 후위표기식으로 바꾸는 프로그램을 만들어보자.

중위 표기식에는 후위표기식과 다르게 우선순위라는것이 존재한다.

가령 4*2+3 이란 식이 들어왔을때

operand 라면 바로 출력하고, operator 라면 스택에 넣는데

 

4출력 ->2출력 ->3출력

스택 : * +

이렇게 하면 423*+ 가 된다. 따라서 이식의 결과는 4+2*3이다. 처음 들어온 식과 다르다.

결론적으로 스택에 우선순위가 더 높은 operator 가 있다면 pop해서 출력해야한다.

 

또 lparen, 즉 개괄호의 경우 우선순위가 스택안(isp)에서와 밖(icp)에서가 다른데, 개괄호는 스택에 들어올때는 우선순위를 가장 높게 만들어 무조건 스택에 들어갈수있게하고, 스택안에서는 오히려 우선순위를 낮게해 폐괄호가 나오기 전까지는 스택에서 나가지 못하게해 다시말해 괄호연산자의 우선순위를 보장하는 것이다.