중위 표기법과 후위 표기법

1. 개념
   1-1. 중위 표기법이란?
   1-2. 후위 표기법이란?
2. 중위 표기식을 후위 표기식으로 바꾸는 법
   2-1. 괄호가 없는 경우
   2-2. 괄호가 있는 경우
3. 계산
   3-1. 후위 표기식을 사칙연산하는 법

 

 

 

---

 

1. 개념

1-1. 중위 표기법이란?

 

1+1 은 귀요미~

 

• 1+1, 2+2, 3+3 ...

흔히 우리는 숫자와 숫자 사이에 더하기 빼기와 같은 연산자를 넣어서 식을 표현하곤 한다.

이렇게 피연산자 사이에 연산자가 위치하는 식을 중위 표기식이라고 하며

이렇게 표기하는 방법을 중위 표기법이라고 한다.

연산자가 '중'간에 위치하기 때문에 '중'위 표기법이라고 기억하면 쉽다.

 

 

1-2. 후위 표기법이란?

• 11+, 22+, 33+ ...

중위 표기식과 다르게 후위 표기식은 연산자가 뒤에 위치한다.

이렇게 표기하는 방법을 후위 표기법이라고 하며

연산자가 '뒤(후)'에 위치하기 때문에 '후'위 표기법이라고 기억하면 쉽다.

 

 

중위 표기법은 사람이 이해하기 쉽게, 사용하기 쉽게 식을 표현하는 방법이라면

후위 표기법은 컴퓨터가 연산을 하기 쉽게 표현하는 방법이다.

 

계산은 컴퓨터가 할 테니 직접 써먹을 일은 없겠지만

쉬운 난이도의 스택 관련 알고리즘 문제에 가끔 출몰하고

또 우리의 학점을 위해 (...) 알아둘 필요가 있다.

 

 

2. 중위 표기식을 후위 표기식으로 바꾸는 법

2-1. 괄호가 없는 경우

 

---

규칙

 

1. 숫자는 그대로 출력한다.

2. 만약 스택이 비어있다면 연산자를 그냥 스택에 넣는다.

3. (스택의 top에 있는 연산자의 우선순위 < 현재 연산자의 우선순위) 이면 현재 연산자를 그냥 스택에 넣는다.

4. (스택의 top에 있는 연산자의 우선순위 >= 현재 연산자의 우선순위) 이면 2번 혹은 3번 상황이 될 때까지 pop 하여 출력하고 연산자를 스택에 넣는다.

5. 모든 수식을 다 사용했다면 스택이 빌 때까지 pop하여 출력한다.

6. 우선순위는 (더하기=빼기) < (곱하기=나누기)이다.

---

 

백날 규칙을 읽어보는 것보다 실제 과정을 보는 게 훨씬 이해하기 좋기 때문에

그림으로 표현한 예시와 설명들을 읽어보자.

 

 

 

• A+B

1+2를 후위 표기식으로 바꾸는 과정

 

① 1+2라는 중위 표기 식이 준비되었다.

② [규칙 1]에 의해 '1'은 숫자니까 그대로 출력한다.

③ [규칙 2]에 의해 스택이 비어있으므로(= 비교할 연산자가 없으므로) '+'를 스택에 추가한다.

④ [규칙 1]에 의해 '2'는 숫자니까 그대로 출력한다.

⑤ [규칙 5]에 의해 스택에 남아있는 '+'를 pop 하여 출력한다.

 

 

 

• A+B*C

1+2*3을 후위 표기식으로 바꾸는 과정

 

① 1+2*3이라는 중위 표기식이 준비되었다.

② [규칙 1]에 의해 '1'은 숫자니까 그대로 출력한다.

③ [규칙 2]에 의해 스택이 비어있으므로(= 비교할 연산자가 없으므로) '+'를 스택에 추가한다.

④ [규칙 1]에 의해 '2'는 숫자니까 그대로 출력한다.

⑤ [규칙 3]에 의해 '+'보다 '*'의 우선순위가 크므로 '*'를 스택에 추가한다.

⑥ [규칙 1]에 의해 '3'은 숫자니까 그대로 출력한다.

⑦ [규칙 5]에 의해 스택의 모든 연산자를 pop 해서 순서대로 출력한다.

 

 

 

• A*B+C

1*2+3을 후위 표기식으로 바꾸는 과정

 

① 1*2+3이라는 중위 표기식이 준비되었다.

② [규칙 1]에 의해 '1'은 숫자니까 그대로 출력한다.

③ [규칙 2]에 의해 스택이 비어있으므로(= 비교할 연산자가 없으므로) '*'를 스택에 추가한다.

④ [규칙 1]에 의해 '2'는 숫자니까 그대로 출력한다.

⑤ [규칙 4]에 의해 '*'가 '+'보다 우선순위가 크므로 '*'를 pop 하여 출력한다.

⑥ ⑤번 작업이 끝났으니 이제 '+' 추가한다.

⑦ [규칙 1]에 의해 '3'은 숫자니까 그대로 출력한다.

⑧ [규칙 5]에 의해 스택의 모든 연산자를 pop 해서 순서대로 출력한다.

 

연습문제. 1+2*3+4/5는 후위 표기법으로 나타내면 어떻게 될까요?

정답: 123*+45/+ (왼쪽 공백 부분을 드래그해서 긁으세요)

 

 

2-2. 괄호가 있는 경우

 

---

규칙

 

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

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

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

---

 

괄호가 있는 경우라고 해서 규칙이 완전 새로 바뀌는 게 아니다.

한 번에 너무 많은 것을 설명하면 헷갈릴까 봐 구분해놓았을 뿐...

이전에 사용한 규칙에 위 세 규칙만 추가하면 된다.

 

 

 

• A*(B+C)

1*(2+3)을 후위 표기식으로 바꾸는 과정

 

① 1*(2+3)이라는 중위 표기식이 준비되었다.

② [규칙 1]에 의해 '1'은 숫자니까 그대로 출력한다.

③ [규칙 2]에 의해 스택이 비어있으므로(= 비교할 연산자가 없으므로) '*'를 스택에 추가한다.

④ [규칙 7]에 의해 '('는 그냥 스택에 넣는다.

⑤ [규칙 1]에 의해 '2'는 숫자니까 그대로 출력한다.

⑥ [규칙 8]에 의해 '+'를 스택에 넣는다.

⑦ [규칙 1]에 의해 '3'은 숫자니까 그대로 출력한다.

⑧ 실제로는 닫는 괄호를 스택에 넣지 않지만 시각적인 이해를 위해 추가한 단계이다.

⑨ [규칙 9]에 의해 여는 괄호가 나올 때까지 pop 하여 출력하고 괄호는 버린다. 즉, '+'를 출력한다.

⑩ [규칙 5]에 의해 스택의 모든 연산자를 pop 해서 순서대로 출력한다.

 

 

연습문제. (3+5*(4-6)/2)은 후위 표기법으로 나타내면 어떻게 될까요?

정답: 3546-*2/+ (왼쪽 공백 부분을 드래그해서 긁으세요)

 

 

 

3. 계산

3-1. 후위 표기식을 사칙연산하는 법

 

---

규칙

 

1. 숫자는 스택에 그냥 추가한다.

2. 연산자가 나오면 숫자 2개를 pop 해서 계산한다.

3. 이때 먼저 pop 되는 숫자가 두 번째 값, 나중에 pop되는 숫자가 첫 번째 값으로 하여 계산해야 한다. 계산한 값은 다시 스택에 넣는다.

---

 

다행히도 사칙연산 계산은 규칙이 3개밖에 없다.

다음 예시는 [목차 2-2]의 연습문제의 정답을 가지고 계산한 과정이다.

 

*이 풀이의 8번에 오류가 있습니다.
-10/2를 해야하는데 2/(-10)을 했네요...

혼란을 드려 죄송합니다. 나머지 풀이 방식은 정상입니다.

 

• 3546-*2/+ 

3546-*2/+를 사칙연산 하는 과정

 

① 3546-*2/+이라는 후위 표기식이 준비되었다.

② [규칙 1]에 의해 숫자들을 차례대로 스택에 넣는다.

③ [규칙 2]에 의해 숫자 2개를 pop 한다. 이때 [규칙 3]에 의해 먼저 pop 된 '6'이 두 번째 값으로 나중에 pop된 '4'는 첫 번째 값으로 두어 계산한다. 즉, 4-6을 계산한다.

④ 계산한 값을 다시 스택에 넣는다.

⑤ [규칙 2], [규칙 3]에 의해 계산한다.

⑥ 계산한 값을 다시 스택에 넣는다.

⑦ [규칙 1]에 의해 '2'는 숫자니까 스택에 넣는다.

⑧ [규칙 2], [규칙 3]에 의해 계산한다.

⑨ 계산한 값을 다시 스택에 넣는다.

⑩ [규칙 2], [규칙 3]에 의해 계산한다.

⑪ 모든 수식이 끝나면 스택에 계산 결과만이 남게 된다. 이를 출력하면 끝

 

 

 

 

 

 

---

💡 느낀 점

• 막상 이해하면 어렵지 않은데 과정을 일일이 다 적고 보니 복잡한 거처럼 보이는 것 같다... ㅋㅋㅋ
• 분명 몇 년 전에 배웠던 건데 오랜만에 하려니 기억이 안 나서 당황스러웠다. 이젠 진짜 안 까먹겠지..

📘 참고한 자료

• 자기계발하는 쏭이님 블로그

---