[자료구조] 수식의 표기법 (Notation)

수식의 표기법

 - 전위 표기법 (prefix notation) : 연산자를 피연산자 앞에 표기하는 방법 (ex +AB)

 - 중위 표기법 (infix notation) : 연산자를 피연산자의 가운데 표기하는 방법 (ex A+B)

 - 후위 표기법 (postfix notation) : 연산자를 피연산자 뒤에 표기하는 방법 (ex AB+)

 

중위 표기식 ㅡ변환ㅡ> 전위 표기식

① 수식의 각 연산자에 대해 우선순위에 따라 괄호를 사용하여 다시 표현
② 각 연산자를 그에 대응하는 왼쪽 괄호의 앞으로 이동
③ 괄호 제거

EX) A * B - C / D

 

1단계 : ((A * B) - (C / D))

2단계 : -(*(A B) / (C D))

3단계 : -*AB/CD

 

중위 표기식 ㅡ변환ㅡ> 후위 표기식

① 수식의 각 연산자에 대해 우선순위에 따라 괄호를 사용하여 다시 표현
② 각 연산자를 그에 대응하는 오른쪽 괄호의 뒤로 이동
③ 괄호 제거

EX) A * B - C / D

 

1단계 : ((A * B) - (C / D))

2단계 : ((A B)* (C D)/)-

3단계 : AB*CD/-

 

스택 사용 Version) 중위 표기식 ㅡ변환ㅡ> 후위 표기식

① 왼쪽 괄호( '(' )를 만나면 무시
② 피연산자를 만나면 출력
③ 연산자를 만나면 스택에 push
④ 오른쪽 괄호( ')' )를 만나면 출력
⑤ 수식이 끝나면, 스택이 공백이 될 때까지 pop 하여 출력

(

(

A

*

B

)

-

(

C

/

D

)

)

스택

출력상태

연산 과정은 다음과 같다

(

(

A

*

B

)

-

(

C

/

D

)

)

A

①

①

②

스택

출력상태

▼

(

(

A

*

B

)

-

(

C

/

D

)

)

AB

①

①

②

③

②

* (push)

스택

출력상태

▼

(

(

A

*

B

)

-

(

C

/

D

)

)

AB*

①

①

②

③

②

④

(pop)

스택

출력상태

▼

(

(

A

*

B

)

-

(

C

/

D

)

)

AB*CD

①

①

②

③

②

③

③

①

②

③

②

/ (push)

- (push)

스택

출력상태

▼

(

(

A

*

B

)

-

(

C

/

D

)

)

AB*CD/-

①

①

②

③

②

④

③

①

②

③

②

④

④

(pop)

(pop)

스택

출력상태

---

위 예시처럼 괄호가 빠지지 않고 모두 입력이 되면 위와 같은 과정으로 후위 수식을 나타내 줄 수 있지만, 괄호가 제대로 되어있지 않은 경우(생략이 가능해서 생략한 경우)는 코드 구현에 난이도가 올라가게 된다. 다음 포스팅에 나와있는 문제가 바로 그러한 문제이다.

<<<백준 1918 후위 표기 식>>> 추후 코드 리뷰 포스팅 예정