[자료구조] 스택 응용 후위 표기(POSTFIX)

🎯 들어가기 전에

1. 전위 표기법(PREFIX)
   1. 연산자를 먼저 표시하고 연산에 필요한 피연산자를 나중에 표기하는 방법.
2. 중위 표기법(INFIX)
   1. 연산자를 두 피연산자 사이에 표기하는 방법으로 일반적으로 사용하는 표기법.
3. 후위 표기법(POSTFIX)
   1. 피연산자를 먼저 표시하고 연산자를 나중에 표기하는 방법
   2. 컴파일러가 사용하는 것으로 스택을 사용하는 예들 중 가장 빈번하게 등장한다.

---

🤷 후위 표기를 사용하는 이유

• 일반적으로 중위 표기가 익숙한 식임에도 불구하고 후위 표기법(POSTFIX)을 사용하는 이유란 우리가 계산하는 방식과 컴퓨터가 계산하는 방식이 다르기 때문이다.
  • 연산자를 두 피연산자 사이에 표기하는 방식은 사람들에게는 금방 인지할 수 있는 쉬운 표기법이지만 컴퓨터는 차례차례 연산자를 보고 결정 해야 하기 때문에 계산이 어려워진다. 그 때문에 전위 표기법(PREFIX) 혹은 후위 표기법(POSTFIX)을 사용한다.

---

💱 중위 → 후위 변경법

• Ex. 3+2+4*5+3/1

1. 우선 연산자 우선순위에 맞게 괄호를 쳐줌.
   • ((3+2)+(4*5)+(3/1)
2. 이 괄호 안에 있는 연산자들을 뒤로 빼줌.
   • (((32)+(45)*)+(31)/)+
3. 괄호를 모두 없애줌.
   • 32+45+31/+*

---

🌕 스택을 이용한 식 표현하기

1. 숫자가 나오면 그대로 출력한다.
2. ( 가 나오면 스택에 Push한다.
3. • / 가 나오면 스택에 Push한다.
4. • • 연산이 나오면 여는 괄호, 여는 괄호가 없다면 스택의 끝까지 출력하고 그 연산자를 스택에 Push한다.
5. 닫는 괄호가 나오면 여는 괄호가 나올 때까지 Pop하여 출력한다.

 

🧮 스택을 이용한 후위 표기법 계산법

• Ex. 123+42+2/+*

1. 우선 연산자가 나오기 전까지 피연산자를 스택에 넣어준다.
   • Stack : 123
   • 식 : *+42+2/+
2. 피연산자가 나오면 스택에서 두 수를 꺼내 계산하고 다시 스택에 넣어준다.
   • Stack : 16
   • 식 : +42+2/+
3. 피연잔사가 나오면 스택에서 두 수를 꺼내 계산하고 다시 스택에 넣어준다.
   • Stack : 7
   • 식 : 42+2/+
4. 연산자가 나오기 전까지 피연산자를 스택에 넣어준다.
   • Stack : 742
   • 식 : +2/+
5. 피연잔사가 나오면 스택에서 두 수를 꺼내 계산하고 다시 스택에 넣어준다.
   • Stack : 76
   • 식 : 2/+
6. 연산자가 나오기 전까지 피연산자를 스택에 넣어준다.
   • Stack : 762
   • 식 : /+
7. 연잔사가 나오면 스택에서 두 수를 꺼내 계산하고 다시 스택에 넣어준다.
   • Stack : 73
   • 식 : +
8. 연잔사가 나오면 스택에서 두 수를 꺼내 계산하고 다시 스택에 넣어준다.
   • Stack : 10
   • 식 :

---

📒 참고문서

[Algorithm] 전위/중위/후위 표기법(prefix/infix/postfix)

[자료구조] 스택 응용 전위표기(prefix), 후위표기(postfix), 중위표기(infix)