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

 

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

 

 

수식 표기법의 종류

 

 

* 연산자: +, -, *, ...

  피연산자: 1, 2, 3, ...

 

 

1. 전위 표기법 (ex. +AB)

 

연산자를 먼저 표시하고 연산에 필요한 피연산자를 나중에 표기하는 방법.

 

 

2. 중위 표기법 (ex. A+B)

 

연산자를 두 피연산자 사이에 표기하는 방법으로 가장 일반적으로 사용되는 표현 방법.

이항 연산자 표현이 적합하다.

 

 

3. 후위 표기법 (ex. AB+)

 

피연산자를 먼저 표시하고 연산자를 나중에 표시하는 방법.

컴파일러가 사용하는 것으로 스택을 사용하는 예들 중 가장 빈번하게 등장.

 

 

---

 

수식 표기법의 변환

 

 

1. 중위 -> 전위

 

 

중위 표기법으로 표기된

3+2+4*5+3/1

를 전위 표기법으로 바꿔본다.

 

우선 연산자 우선순위에 맞게 괄호를 쳐준다.

((3+(2+(4*5)))+(3/1))

 

이 괄호 안에 있는 연산자들을 앞으로 빼준다.

+((+3(+2*(45)))/(31))

 

괄호를 모두 없애준다.

++3+2*45/31

 

해당 식이 전위 표기법으로 나타낸 식이다.

 

 

 

2. 중위 -> 후위

 

 

중위 표기법으로 표기된

3+2+4*5+3/1

를 후위 표기법으로 바꿔본다.

 

우선 연산자 우선순위에 맞게 괄호를 쳐준다.

((3+2)+(4*5))+(3/1)

 

이 괄호 안에 있는 연산자들을 뒤로 빼준다.

(((32)+(45)*)+(31)/)+

 

괄호를 모두 없애준다.

32+45*+31/+

 

해당 식이 후위 표기법으로 나타낸 식이다.

 

 

이때 스택을 이용하는 방법.

 

 

1. 숫자가 나오면 그대로 출력한다.

2. (나오면 스택에 push한다.

3. * / 나오면 스택에 push한다.

4. + - 연산이 나오면 여는 괄호('('), 여는 괄호가 없다면 스택의 끝까지 출력하고 그 연산자를 스택에 push한다.

5. 닫는 괄호(')')가 나오면 여는 괄호('(')가 나올때까지 pop하여 출력한다.

 

https://reakwon.tistory.com/62 참고

 

 

 

3. 후위 -> 중위

 

 

같은 방식을 반대로 사용해주면 된다.

 

 

후위 표기법으로 표기된

3245*++31/+

를 중위 표기법으로 바꿔본다.

 

우선 후위 표기법의 순서인 '피연산자, 피연산자, 연산자'를 괄호로 묶어준다.

((3(2(45)*)+)+(31)/)+

 

연산자를 피연산자 사이로 옮겨준다.

(3+(2+(4*5)))+(3/1))

 

가장 밖에 있는 괄호만 제거해준다.

3+(2+(4*5)))+(3/1)

 

해당 식이 후위 표기법으로 나타낸 식이다.

 

 

---

 

수식 표기법의 계산

 

1. 후위 표기법의 계산

 

 

스택을 이용

 

- 숫자를 만나면 전부 스택에 집어 넣는다.

- 연산자가 나오면 스택에서 두 수를 꺼내 계산하고 다시 스택에 집어 넣는다.

 

 

참고

 

https://engineershelp.tistory.com/478

https://reakwon.tistory.com/62