제6장. 자료구조 1. 중위 표기(INFIX)를 후위 표기(POSTFIX)로 변환, 트리 생성 후 전위 표기 구하기

1. 중위 표기(INFIX)를 후위 표기(POSTFIX)로 변환

중위 표기를 후위 표기로 변환하는 것을 사람 눈으로 볼 수 있게 표현할 때에는 세가지 과정을 거칩니다.

첫째, 연산자간 우선순위를 가시적으로 보이도록 괄호로 묶는다.

둘째, 왼쪽 괄호를 만나면 무시하고 다음 문자를 읽고 연산자를 만나면 연산자를 스택에 push(저장)한다.

셋째, 오른쪽 괄호를 만날때마다 스택에 저장된 연산자를 pop 및 출력한다.

 

(1) 중위 표기 'A+B*C'를 후위 표기로 변환

 

첫째,

 

(A+(B*C))

 

둘째,

 

(A+(B*C))

 

A

stack

 

A

stack

+

 

AB

stack

+

 

AB

stack

*

+

 

AB

stack

*

+

 

ABC

stack

*

+

 

 

 

 

 

셋째,

 

ABC*

stack

+

 

 

ABC*+

stack

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

(2) 중위 표기 'A*B+C'를 후위 표기로 변환

 

첫째,

 

((A*B)+C)

 

둘째,

 

((A*B)+C)

 

A

stack

 

A

stack

*

 

AB

stack

*

 

AB

stack

+

*

 

ABC

stack

+

*

 

 

 

 

 

 

 

셋째,

 

ABC+

stack

*

 

 

ABC+*

stack

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

(3) 중위 표기 'A*(B+C)'를 후위 표기로 변환

 

첫째,

 

(A*(B+C))

 

둘째,

 

(A*(B+C))

 

A

stack

 

A

stack

*

 

AB

stack

*

 

AB

stack

+

*

 

ABC

stack

+

*

 

 

 

 

 

셋째,

 

ABC+

stack

*

 

 

ABC+*

stack

 

 

 

 

 

 

 

 

 

 

(4) 중위 표기 '(A+(B+C)*(D-E))'를 후위 표기로 변환

 

첫째,

 

(A+((B+C)*(D-E)))

 

둘째,

 

(A+((B+C)*(D-E)))

 

A

stack

 

A

stack

+

 

AB

stack

+

 

AB

stack

+

+

 

ABC

stack

+

+

 

 

 

(A+((B+C)*(D-E))) 오른쪽 괄호를 만났으므로

 

ABC+

stack

+

 

ABC+

stack

*

+

 

ABC+D

stack

*

+

 

ABC+D

stack

-

*

+

 

ABC+DE

stack

-

*

+

 

ABC+DE-

stack

*

+

 

ABC+DE-*

stack

+

ABC+DE-*+

stack

 

 

 

 

 

 

 

 

 

 

 

 

 

2. 트리 생성 후 전위 표기 구하기

 

(1) 1-(4)에서 구한 후위 표기로부터 트리를 생성하는 과정

 

후위연산이 완료된 수식 ABC+DE-*+ 가 들어오면 앞에서부터 읽는다. 연산자가 아닌 데이터가 들어오면 stack에 push한다.

 

ABC+DE-*+

stack

A

 

ABC+DE-*+

stack

B

A

+DE-*+

stack

C

B

A

 

연산자를 만나면 stack에 저장된 피연산자를 꺼내 트리를 구성한다. 아래의 트리를 1번트리라 칭한다.

이렇게 형성된 트리는 스택에 저장한다.

 

DE-*+

stack

E

D

1번트리

A

 

 

이 다음부터는 앞서 풀이했던 방식과 유사하게 진행된다.

 

 

 

 

 

 

 

 

 

 

*+

stack

E

D

1번트리

A

 

-연산자로 E와 D를 이용해 트리를 구성했다. 이 트리를 2번 트리라 칭한다.

*+

stack

2번트리

1번트리

A

*연산자로 2번 트리와 1번트리를 이용해 3번트리를 구성했다.

+

stack

3번트리

A

 

+연산자로 3번 트리와 A를 이용해 최종트리를 구성했다.

 

 

 

 

 

 

 

 

 

 

 

 

(2) 2-(1)에서 생성한 트리로부터 전위 표기를 구할 것(과정은 생략 가능).

 

+A*+BC-DE

 

 

 

 

참고자료

1) 중위표기 후위표기 변환

https://dev-with-precious-dreams.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%A4%91%EC%9C%84%ED%91%9C%EA%B8%B0%EC%8B%9D-%ED%9B%84%EC%9C%84%ED%91%9C%EA%B8%B0%EC%8B%9D-%EB%B3%80%ED%99%98-%EB%B0%A9%EB%B2%95stack%EC%9D%98-%EC%9D%91%EC%9A%A9

https://woongsios.tistory.com/288

2) 트리 생성 후 전위 표기 구하기

https://seongkyun.github.io/data_structure/2019/08/04/data_structure/

https://rudruddl.tistory.com/124