[HUFS/자료구조] #4 스택

스택(Stack)

후입선출의 자료구조

제일 나중에 들어온 것을 제일 먼저 쓰는 구조이다

스택 ADT(추상자료형)

리스트의 배열 구조 / 위치가 밀리기 때문에 후단을 사용하는 것이 용이함

스택의 함수 구현

스택의 클래스 구현 (생성자)

클래스 스택의 출력을 수정

괄호 검사

같은 종류, 맞는 쌍의 괄호를 순서를 지켜 잘 넣었는지 검사하는 것이다 [ ] { } ( )

스택을 활용해 괄호 규칙을 검사하는 알고리즘을 작성해보자!

 

대략적인 방법

알고리즘 작성

소스파일을 불러와서 검사할 수 있다

수식의 계산

전위/중위/후위 표기 방식이 있다 (컴퓨터는 사람이 입력한 중위에서 후위로 변환해 계산한다)

후위 표기 계산 알고리즘

이런 방식으로 처리된다

다음으로는 입력된 중위 표기를 후위 표기로 변환해주는 알고리즘을 짜보자

 

연산자만 우선순위에 맞게 스택으로 저장했다가 꺼내는 구조

먼저 우선순위를 설정하고

알고리즘 작성

변환되는 구조