Chapter 06. 스택(Stack) Chapter 06-1: 스택의 이해와 ADT 정의.

Presentation on theme: "Chapter 06. 스택(Stack) Chapter 06-1: 스택의 이해와 ADT 정의."— Presentation transcript:

1 Chapter 06. 스택(Stack) Chapter 06-1: 스택의 이해와 ADT 정의

2 스택(Stack)의 이해 ∙ 스택은 ‘먼저 들어간 것이 나중에 나오는 자료구조’로써 초코볼이 담겨있는 통에 비유할 수 있다. ∙ 스택은 ‘LIFO(Last-in, First-out) 구조’의 자료구조이다. ∙ 초코볼 통에 초코볼을 넣는다 push ∙ 초코볼 통에서 초코볼을 꺼낸다 pop ∙ 이번에 꺼낼 초코볼의 색이 무엇인지 통 안을 들여다 본다 peek 스택의 기본 연산 일반적인 자료구조의 학습에서 스택의 이해와 구현은 어렵지 않다. 오히려 활용의 측면에서 생각할 것들이 많다!

3 스택의 ADT 정의 PUSH 연산 POP 연산 PEEK 연산 ADT를 대상으로 배열 기반의 스택
또는 연결 리스트 기반의 스택을 구현할 수 있다. PUSH 연산 POP 연산 PEEK 연산

4 Chapter 06. 스택(Stack) Chapter 06-2: 스택의 배열 기반 구현

5 구현의 논리 두 번의 PUSH 연산 인덱스가 0인 위치를 스택의 바닥으로 정의해야 배열 길이에 상관없이 바닥의 인덱스 값이 동일해진다. ∙ 인덱스 0의 배열 요소가 '스택의 바닥(초코볼 통의 바닥)'으로 정의되었다. ∙ 마지막에 저장된 데이터의 위치를 기억해야 한다. ∙ push Top을 위로 한 칸 올리고, Top이 가리키는 위치에 데이터 저장 ∙ pop Top이 가리키는 데이터를 반환하고, Top을 아래로 한 칸 내림

6 스택의 헤더파일 배열 기반을 고려하여 정의된 스택의 구조체!

7 배열 기반 스택의 구현: 초기화 및 기타 함수 -1은 스택이 비었음을 의미 빈 경우 TRUE를 반환

8 배열 기반 스택의 구현: PUSH, POP, PEEK

9 배열 기반 스택의 활용: main 함수 Arraybasestack.h Arraybasestack. c
Arraybasestackmain.c 실행결과

10 Chapter 06. 스택(Stack) Chapter 06-3: 스택의 연결 리스트 기반 구현

11 연결 리스트 기반 스택의 논리와 헤더파일의 정의
이렇듯 메모리 구조만 보아서는 스택임이 구분되지 않는다! 저장된 순서의 역순으로 데이터(노드)를 참조(삭제)하는 연결 리스트가 바로 연결 기반의 스택이다! 문제 06-1에서는 CLinkedList.h와 CLinkedList.c를 단순히 활용하여 스택의 구현을 요구한다!

12 연결 리스트 기반 스택의 구현 1 새 노드를 머리에 추가하고, 삭제 시 머리부터 삭제하는 단순 연결 리스트의 코드에 지나지 않는다.

13 연결 리스트 기반 스택의 구현 2 연결 리스트 기반 스택을 직접 구현하는 것보다 의미 있는 것은 문제 06-1을 해결하는것이다!

14 연결 기반 스택의 활용: main 함수 listbasestack.h listbasestack. c
배열 기반 리스트 관련 main 함수와 완전히 동일하게 정의된 main 함수! listbasestack.h listbasestack. c listbasestackmain.c 실행결과

15 Chapter 06. 스택(Stack) Chapter 06-4: 계산기 프로그램 구현

16 구현할 계산기 프로그램의 성격 다음과 같은 문장의 수식을 계산할 수 있어야 한다.
( ) * ( 5 / 2 ) + ( 7 + ( 9 – 5 ) ) 다음과 같은 문장의 수식계산을 위해서는 다음 두 가지를 고려해야 한다. ∙ 소괄호를 파악하여 그 부분을 먼저 연산한다. ∙ 연산자의 우선순위를 근거로 연산의 순위를 결정한다. 계산기 구현에 필요한 알고리즘은 스택과는 별개의 것이다. 다만 그 알고리즘의 구현에 있어서 스택이 매우 요긴하게 활용된다.

17 세 가지 수식의 표기법: 전위, 중위, 후위 ∙ 중위 표기법(infix notation) 예) 5 + 2 / 7
∙ 전위 표기법(prefix notation) 예) + 5 / 2 7 ∙ 후위 표기법(postfix notation) 예) / + 수식 내에 연산의 순서에 대한 정보가 담겨 있지 않다. 그래서 소괄호와 연산자의 우선순위라는 것을 정의하여 이를 기반으로 연산의 순서를 명시한다. 수식 내에 연산의 순서에 대한 정보가 담겨 있다. 그래서 소괄호가 필요 없고 연산의 우선순위를 결정할 필요도 없다. 전위 표기법과 마찬가지로 수식 내에 연산의 순서에 대한 정보가 담겨 있다. 그래서 소괄호가 필요 없고 연산의 우선순위를 결정할 필요도 없다. 소괄호와 연산자의 우선순위를 인식하게 하여 중위 표기법의 수식을 직접 계산하게 프로그래밍 하는 것보다 후위 표기법의 수식을 계산하도록 프로그래밍 하는 것이 더 쉽다!

18 중위 → 후위 : 소괄호 고려하지 않고 1 수식을 이루는 왼쪽 문자부터 시작해서 하나씩 처리해 나간다.
피 연산자를 만나면 무조건 변환된 수식이 위치할 자리로 이동시킨다.

19 중위 → 후위 : 소괄호 고려하지 않고 2 연산자를 만나면 무조건 쟁반으로 이동한다.
숫자를 만났으니 변환된 수식이 위치할 자리로 이동!

20 중위 → 후위 : 소괄호 고려하지 않고 3 쟁반에 기존 연산자가 있는 상황에서의 행동 방식!
/ 연산자의 우선순위가 높으므로 + 연산자 위에 올린다. 쟁반에 기존 연산자가 있는 상황에서의 행동 방식! ☞ 쟁반에 위치한 연산자의 우선순위가 높다면 ∙ 쟁반에 위치한 연산자를 꺼내서 변환된 수식이 위치할 자리로 옮긴다. ∙ 그리고 새 연산자는 쟁반으로 옮긴다. ☞ 쟁반에 위치한 연산자의 우선순위가 낮다면 ∙ 쟁반에 위치한 연산자의 위에 새 연산자를 쌓는다. 우선순위가 높은 연산자는 우선순위가 낮은 연산자 위에 올라서서, 우선순위가 낮은 연산자가 먼저 자리를 잡지 못하게 하려는 목적!

21 중위 → 후위 : 소괄호 고려하지 않고 4 피 연산자는 무조건 변환된 수식의 자리로 이동!
나머지 연산자들은 쟁반에서 차례로 옮긴다!

22 중위 → 후위 : 정리하면 변환 규칙의 정리 내용 ∙ 피 연산자는 그냥 옮긴다. ∙ 연산자는 쟁반으로 옮긴다.
∙ 연산자가 쟁반에 있다면 우선순위를 비교하여 처리방법을 결정한다. ∙ 마지막까지 쟁반에 남아있는 연산자들은 하나씩 꺼내서 옮긴다.

23 중위 → 후위 : 고민 될 수 있는 상황 상황 1 + 연산자가 우선순위가 높다고 가정하고(+ 연산자가 먼저 등장했으므로) 일을 진행한다. 즉 + 연산자를 옮기고 그 자리에 – 연산자를 가져다 놔야 한다.” 상황 2

24 중위 → 후위 : 소괄호 고려 1 후위 표기법의 수식에서는 먼저 연산이 이뤄져야 하는 연산자가 뒤에 연산이 이뤄지는 연산자보다 앞에 위치해야 한다. 따라서 소괄호 안에 있는 연산자들이 후위 표기법의 수식에서 앞부분에 위치해야 한다. ( 연산자의 우선순위는 그 어떤 사칙 연산자들보다 낮다고 간주! 그래서 ) 연산자가 등장할 때까지 쟁반에 남아 소괄호의 경계 역할을 해야 함!

25 중위 → 후위 : 소괄호 고려 2 ) 연산자를 만나면 쟁반에서 ( 연산자 만날 때까지 연산자를 변환된 수식의 자리로 옮긴다!

26 중위 → 후위 : 소괄호 고려 3 조금 달리 설명하면 ( 연산자는 쟁반의 또 다른 바닥이다! 그리고 ) 연산자는 변환이 되어야 하는 작은 수식의 끝을 의미한다. 그래서 ) 연산자를 만나면 ( 연산자를 만날 때까지 연산자를 이동 시켜야 한다. 지금까지 설명한 내용에 해당하는 코드의 구현에 앞서 중위 표기법의 수식을 후위 표기법의 수식으로 바꾸는 연습을 할 필요가 있다.

27 중위 → 후위 : 프로그램 구현 1 변환 함수의 타입 중위 표기법 수식을 배열에 담아 함수의 인자로 전달한다.
함수 이름의 일부인 RPN은 후위 표기법의 또 다른 이름인 Reverse Polish Notation의 약자이다. 중위 표기법 수식을 배열에 담아 함수의 인자로 전달한다. 호출 완료 후 exp에는 변환된 수식이 담긴다.

28 중위 → 후위 : 프로그램 구현 2 함수 ConvToRPNExp의 첫 번째 helper function!
연산자의 우선순위에 대응하는 값을 반환한다. 값이 클수록 우선순위가 높은 것으로 정의되어 있다. ( 연산자는 ) 연산자가 등장할 때까지 쟁반에 남아 있어야 하기 때문에 가장 낮은 우선순위를 부여! ) 연산자는 소괄호의 끝을 알리는 메시지의 역할을 한다. 따라서 쟁반으로 가지 않는다. 때문에 ) 연산자에 대한 반환 값은 정의되어 있을 필요가 없다!

29 ConvToRPNExp 함수의 실질적인 Helper Function은 위의 함수 하나이다!
중위 → 후위 : 프로그램 구현 3 함수 ConvToRPNExp의 두 번째 helper function! 두 연산자의 우선순위 비교 결과를 반환한다. ConvToRPNExp 함수의 실질적인 Helper Function은 위의 함수 하나이다!

30 중위 → 후위 : 프로그램 구현 4 변환된 수식을 담을 공간 마련 마련한 공간 0으로 초기화
void ConvToRPNExp(char exp[]) { Stack stack; int expLen = strlen(exp); char * convExp = (char*)malloc(expLen+1); int i, idx=0; char tok, popOp; memset(convExp, 0, sizeof(char)*expLen+1); StackInit(&stack); for(i=0; i<expLen; i++) { } while(!SIsEmpty(&stack)) convExp[idx++] = SPop(&stack); strcpy(exp, convExp); free(convExp); 변환된 수식을 담을 공간 마련 마련한 공간 0으로 초기화 일련의 변환 과정을 이 반복문 안에서 수행 스택에 남아 있는 모든 연산자를 이동시키는 반복문 변환된 수식을 반환!

31 중위 → 후위 : 프로그램 구현 5 tok에 저장된 문자가 피연산자라면 tok에 저장된 문자가 연산자라면
void ConvToRPNExp(char exp[]) { for(i=0; i<expLen; i++) tok = exp[i]; if(isdigit(tok)) convExp[idx++] = tok; } else switch(tok) tok에 저장된 문자가 피연산자라면 tok에 저장된 문자가 연산자라면 연산자일 때의 처리 루틴을 switch문에 담는다!

32 중위 → 후위 : 프로그램 구현 6 함수 ConvToRPNExp의 일부인 switch문
tok에 저장된 연산자를 스택에 저장하기 위한 과정

33 중위 → 후위 : 프로그램의 실행 InfixToPostfix.h InfixToPostfix.c ListBaseStack.h
ListBaseStack.c InfixToPostfixMain.c ConvToRPNExp 함수의 선언과 정의 스택관련 함수의 선언과 정의 main 함수의 정의 실행결과

34 후기 표기법 수식의 계산 피연산자 두 개가 연산자 앞에 항상 위치하는 구조 후위 표기법 수식으로 후위 표기법 수식으로
1과 2의 곱 진행 2와 4의 곱 진행 2와 3의 합 진행

35 후기 표기법 수식 계산 프로그램의 구현 계산의 규칙 ∙ 피연산자는 무조건 스택으로 옮긴다.
∙ 연산자를 만나면 스택에서 두 개의 피연산자를 꺼내서 계산을 한다. ∙ 계산결과는 다시 스택에 넣는다.

36 후기 표기법 수식 계산 프로그램의 구현 이어서

37 후위 표기법 수식 계산 프로그램의 실행 ListBaseStack.h ListBaseStack.c PostCalculator.h
PostCalculator.c ListBaseStack.h ListBaseStack.c PostCalculatorMain.c EvalRPNExp 함수의 선언과 정의 스택관련 함수의 선언과 정의 main 함수의 정의 실행결과

38 중위 표기법 수식 → ConvToRPNExp → EvalRPNExp → 연산결과
계산기 프로그램의 완성1 계산의 과정 중위 표기법 수식 → ConvToRPNExp → EvalRPNExp → 연산결과 계산기 프로그램의 파일 구성 InfixCalculator.h InfixCalculator.c

39 InfixCalculatorMain.c
계산기 프로그램의 완성2 InfixCalculator.h InfixCalculatorMain.c 실행결과 InfixCalculator.c