중위표기식을 후위표기식으로 바꾸는 알고리즘(stack 이용)

• 중위표기법(infix notation)
  • 연산자를 피연산자의 가운데 표기하는 방법
  • ex) A+B
• 후위표기법(postfix notation)
  • 연산자를 피연산자 뒤에 표기하는 방법
  • ex) AB+

Why 후위표기법을 쓰는가?

-> 컴퓨터 입장에서 생각해보자. 중위표기법으로 연산할 때는 연산의 우선순위를 찾기 쉽지 않고, 어디까지 연산을 가해야하는지를 다 찾아야 하기 때문에 연산속도가 느리다. 즉, 후위표기법이 중위표기법보다 연산속도가 더 빠르다.

(명확한 설명은 아니지만, 대략적인 이유)

---

• 중위표기법을 후위표기법으로 바꾸는 알고리즘(stack 이용)

1. 입력 받은 중위표기식을 하나씩 읽는다.
2. 읽힌 값이 피연산자(0,1,2~9)이면 바로 출력한다.
3. 읽힌 값이 연산자 or 괄호라면, 스택의 top에 저장되어 있는 연산자보다 우선순위가 높으면 스택에 push.
4. 우선순위가 낮다면 스택 top의 연산자의 우선순위가 읽힌 값의 우선순위보다 작을 때까지 스택에서 pop한 후 읽힌 값을 push. (만약 top에 연산자가 없다면, 즉 스택이 공란이라면 바로 연산자를 push)
5. 읽힌 값이 닫는 괄호 ')'이면 스택에 pop 연산을 수행하고 pop한 연산자를 출력. 왼쪽괄호를 만나면 pop시키고 출력x
6. 중위 표기식이 끝나면, 중지하고, 스택에 남아있는 연산자를 모두 pop하여 출력

토큰	isp	icp
)	-	-
*, /	2	2
+, -	1	1
(	0	3

• 코드 베이스(with python)

• 예제 입력

3
2+3*4/5
(6+5*(2-8)/2)
3-2*5+4/2-2

• 예제 출력

#1 234*5/+
#2 6528-*2/+
#3 325*-42/+2-