데이터 구조 4 (Constructor , Stack 응용 - @fix들)

• Constructor - 생성자

→ Class 의 Object가 생성될 때 자동으로 실행됨

→ Class 안에서 / Class name과 같은 / Return type이 없는 형태로 구현됨

    정의는 Class 밖에서 my class :: my class(){} 로 구현...

 

→ 주로 Class 기초, 초기에 실행해야하는 것들을 Constructor 에서 함 (초기값 설정, 변수 설정)

ex) Stack에서 Top의 초기값 =0으로 설정하는 것

 

 

• Stack 응용 (할 줄 알아야함 시험에 나온다고 함)

Expression (수식) 표현법 

1 ) infix      → a+b      →부호가 숫자 2개 안(in)에  

2 ) prefix   → +ab      →부호가 숫자 2개 앞(pre)에  

3 ) post     → ab+      →부호가 숫자 2개 뒤(post)에  

 

 

## infix  → prefix 하는 법   [ *문자가 나오는 순서는 식과 같음 ]

   1) 식의 순서에 맞게 괄호를 친다.

   2) 해당 괄호가 *열리는* = "("가 오는 곳에 괄호 안에 있는 부호를 넣는다.

 

   ex) a+b*c = (a+(b*c)) = +a*bc   / 데구4 종이 뒤에 있음

 

 

## infix  → postfix 하는 법   [ *문자가 나오는 순서는 식과 같음 ]

   1) 식의 순서에 맞게 괄호를 친다.

   2) 해당 괄호가 *닫히는*   = " ( "가 오는 곳에 괄호 안에 있는 부호를 넣는다.

 

    ex) a+b*c = (a+(b*c)) =abc*+

 

  

→ 알고리즘

1. 스택 생성 후 문자 초기화(초기값 넣어주기)  → 스택에 '$' 를 넣어준다  (끝났다는 사인 EOS)

2. 입력 (expression) 으로부터 token 을 한 개씩 취하면서 다음을 반복한다.

  해당 토큰이

  1) operand를 꺼내면 → 그대로 출력

  2 )  ' ( ' → 스택에 그냥 넣음

  3 )  ' ) '  (괄호가 끝났다는 뜻이니까) →  스택에서 "(" 가 나올 때까지 Pop하여 출력

  ex) (부호들~~) 인데 이 사이에 있는 부호들 순서대로 다 빼기

  4 ) operator면, stack top 원소가 자신보다 우선순위가 낮아질 때가지 pop하여 출력 후에 자기 자신을 stack에 넣는다.

( 3. 현재 스택을 순서대로 출력 )

 

 

(F-E*D)/C*B^A  식   /    Post-fix 알고리즘을 단계별로 볼 수 있는 표

 

 

출처 : 한동대학교 김호준교수님 - 데이터구조 PPT

마지막 표: https://www.codewithengineer.in/2021/06/program-in-c-to-convert-infix-to-prefix.html