[Stack] 후위 표기법

2024.01.16 화요일

연산자의 위치에 따라
전위, 중위, 후위 표기법

전위 표기법 = 연산자가 앞에 있다.
중위 표기법 = 연산자가 중간에 있다.
후위 표기법 = 연산자가 뒤에 있다.

우리가 일반적으로 사용하는 중위 표기법
연산자가 가운데 위치

2+2

후위 표기법으로 변경

22+

---

<예제1> (1+2)*3 을 후위 표기법으로 나타내기

• 사칙연산과 계산 우선순위는 동일하다
• 변환할 때 헷갈리니까 괄호 표시해주기
• 연산자를 가장 가까운 괄호의 우측으로 옮겨주기

((1+2)*3) 괄호 순서대로 후위 표기법으로 작성
12+3*

1+2를 먼저 계산 : 숫자 쓰고 12, 우측으로 연산자 + (12+) 그리고, 남은 *3도 숫자 쓰고, 우측으로 연산자 (3*) 결과적으로 12+3*

<예제2> 1+2*3 을 후위 표기법으로 나타내기

(1+(2*3))
23* 먼저 풀고 남은 1+는 가까운 괄호 우측으로
123*+

예제2번을 풀고 혼란스러워서 후위 표기법에 대해 찾아보았다.
Stack을 이용하면 쉽게 이해가 된다!

---

Stack을 사용한 후위연산자로 변환 규칙

1. 숫자는 그대로 출력한다.
2. 만약 스택이 비어있다면 연산자를 그냥 스택에 넣는다.
3. (스택의 top에 있는 연산자의 우선순위 < 현재 연산자의 우선순위)
   이면 현재 연산자를 그냥 스택에 넣는다.
4. (스택의 top에 있는 연산자의 우선순위 >= 현재 연산자의 우선순위) 이면 2번 혹은 3번 상황이 될 때까지 pop 하여 출력하고 연산자를 스택에 넣는다.
5. 모든 수식을 다 사용했다면 스택이 빌 때까지 pop하여 출력한다.
6. 우선순위는 (더하기=빼기) < (곱하기=나누기)이다.
   
   

수식에 괄호가 존재한다면 추가 할 규칙

7. 여는 괄호는 스택에 그냥 추가한다.

8. 여는 괄호 다음에 오는 연산자는 그냥 스택에 추가한다.

9. 닫는 괄호는 여는 괄호가 나올 때까지 스택을 pop 하여 출력한다. 다 출력하고 난 뒤 괄호들은 버린다.
   
   

   ⭐ ①②③④⑤⑥⑦⑧⑨ 규칙에 따라 풀이하기 ⭐
   

<예제3> 1+2*3+4/5를 후위 표기법으로 나타내기

123*+45/+

<예제4> (3+5*(4-6)/2)를 후위 표기법으로 나타내기

3546-*2/+

---

표기법 뿐만 아니라 연산도 가능!

Stack으로 후위연산자 계산 규칙

1. 숫자는 스택에 그냥 추가한다.
2. 연산자가 나오면 숫자 2개를 pop 해서 계산한다.
3. 이때 먼저 pop 되는 숫자가 두 번째 값, 나중에 pop되는 숫자가 첫 번째 값으로 하여 계산해야 한다. 계산한 값은 다시 스택에 넣는다.

<예제5> 3546-*2/+를 계산하기

결과 : -2

---

느낀점

• 자료구조를 배우는 이유를 깨달았다.
• 후위 연산자에 대해서 확실히 이해했다.

---

참고 자료
https://todaycode.tistory.com/73