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

Slides:



Advertisements
Similar presentations
비즈쿨 - 정 성 욱 - - 금오공고 비즈쿨 - 정 성 욱 1. 나는 각 단원들의 활동들에 성실하게 참여 하겠습니다. 우리의 다짐 2. 나는 나와 전체의 발전을 위해 각 멘토들의 지도에 순종하겠습니다. 3. 나는 각 단원들을 숙지함으로써 비즈니스 마인드를 함양하고 자신의.
Advertisements

노인복지론 담당교수 : 최 병태 교수님 학과 : 보건복지경영학과 학번 : 이름 : 김 태인 날짜 :
개인의견 차가있을수있음 훈훈한남자 배우 TOP 5. 5 위는 박보검 웃을때보이는 치명적인 미소 꺄 ~~~ 5위5위.
스택 스택 추상자료형 스택 스택의 구현 스택의 응용 한빛미디어(주).
가수 아이돌 김수빈.
1. 자료구조 개념 (1) 자료구조의 개요 1) 자료구조 ① 일련의 자료들을 조직하고 구조화하는 것 ② 자료의 표현과 그것과 관련된 연산 2) 자료구조에 따라 저장공간의 효율성과 프로그램의 실행시간이 달라짐 3) 어떠한 자료구조에서도 필요한 모든 연산들을 처리하는 것이.
어서와 Java는 처음이지! 제2장 자바 프로그래밍 기초.
Basic of Buffer Over Flow
컴퓨터 응용 및 실습 Part1. OOP&Java Programming data type Review
Recursion SANGJI University KO Kwangman
①신생아기의 신체발달 ②신생아기의 운동발달 ③신생아기의 감각기관의 발달 ☞차례. ①신생아기의 신체발달 ②신생아기의 운동발달 ③신생아기의 감각기관의 발달 ☞차례.
3 장 stack and queue.
Chapter 10 – 추상 자료형 Outline 10.1 소개 10.2 Ada의 추상 자료형 10.3 C++의 추상 자료형
시스템 생명 주기(System Life Cycle)(1/2)
명품 C++ 13장 예외 처리와 C 언어와의 링크 지정.
CHAP 6:큐 C로 쉽게 풀어쓴 자료구조 생능출판사 2005.
자료구조 실습 (03분반)
제 1 장 마이크로프로세서의 기본동작.
제7장 제어구조 I – 식과 문장.
Internet Computing KUT Youn-Hee Han
시스템 생명 주기(System Life Cycle)(1/2)
4장 스택.
제5장 제어명령
C언어: 배열 (Arrays).
7 스택.
윤성우의 열혈 C 프로그래밍 윤성우 저 열혈강의 C 프로그래밍 개정판 Chapter 14. 포인터와 함수에 대한 이해.
Choi, Namseok Java 기초 (Java의 제어문과 배열) Choi, Namseok
스택(stack) SANGJI University Kwangman Ko
CHAP 6:큐 C로 쉽게 풀어쓴 자료구조 Slide 1 (of 27).
CHAP 6:큐 C로 쉽게 풀어쓴 자료구조 생능출판사 2005.
다음 주 과제 7장 읽어오기 숙제 해서 다음 주(11월 12일) 제출하기. 큐(Queue) E304호,
Chapter 9 – 구조형과 리스트 처리 Outline 9.1 자신 참조 구조형 9.2 선형 연결 리스트 9.3 리스트 연산
버퍼 오버플로우 시스템보안 인터넷공학전공 권영락.
Chapter 06. 스택.
1과목 데이터베이스 강사 이 민 욱.
Chapter 05. 클래스 완성. chapter 05. 클래스 완성 01. 복사 생성자 복사 생성(Copy Construction) 생성될 때 자신과 같은 타입의 객체를 변수로 받아, 이 객체와 같은 값을 갖는 새로운 객체를 생성하는 것 명시적인 생성 과정뿐만.
Chapter 10 그래프(graph) SANGJI University Kwangman KO
스택(Stack) 김진수
명령어 구조 컴퓨터 하드웨어의 구성 프로그램 명령어 프로그램 실행 동작.
Introduction To Data Structures Using C
2.1 재배정 재배정요구등록 재배정승인취소 재배정부서연결 재배정단위업무연결
C언어 프로그래밍의 이해 Ch13. 선행처리기와 주석문.
Computer System Architecture
배열과 연결리스트 연결리스트 배열 메모리 할당이 연속적이어서 인덱스 사용시 검색이 빠르다.
컴퓨터의 기초 제 2강 - 변수와 자료형 , 연산자 2006년 3월 27일.
Ch.1 Iterator Pattern <<interface>> Aggregate +iterator
다음 주 과제 3장 읽어오기 숙제 해서 제출하기. 자료구조와 알고리즘, 순환 E304호,
칼빈의 생애와 개혁자로의 변모 사학과 김종식.
국제의료관광 관련 법, 제도.
CHAP 2:순환.
3장. 변수와 연산자. 3장. 변수와 연산자 3-1 연산자, 덧셈 연산자 연산자란 무엇인가? 연산을 요구할 때 사용되는 기호 ex : +, -, *, / 3-1 연산자, 덧셈 연산자 연산자란 무엇인가? 연산을 요구할 때 사용되는 기호 ex : +, -, *, /
Java의 정석 제 4 장 조건문과 반복문 Java 정석 남궁성 강의
Chapter 11. 배열과 포인터.
자바 5.0 프로그래밍.
제 3장 데이터형과 연산자 Hello!! C 언어 강성호 김학배 최우영.
남아메리카 선교 김수정, 이하정 전희진, 장성경.
내장형 소프트웨어 -페인트 보드 만들기 발표자 : 백종인.
CHAPTER 9-1 한국의 사회복지정책 - 사회보험제도 -
성립전예산 요구등록 (사업담당자) 사업관리카드 1 2
최대 공약수 구하기 (1) 프로그램 예제2 : 최대 공약수 구하기 문제 해결 방법 구상 (아는 지식 정리) GCD1 알고리즘
대한민국-스웨덴 수교 60주년 기념 행사 주 스웨덴 대한민국 대사관 (토)
9장. C 언어의 핵심! 함수. 9장. C 언어의 핵심! 함수 9-1 함수의 정의와 선언 main 함수 다시 보기 : 함수의 기본 형태 { } 그림 9-1.
시민이 체감하는 편리한 건축인허가 절차 개선 추진.
청소년 댄스 경연대회 제35회 문화체육관광부장관大賞 전국레크리에이션대회
10장. 컴퓨터 구조에 대한 세 번째 이야기 작성자: 윤성우.
C.
Chapter 09. 배열.
Choi Younghwan CSE HUFS
배열, 포인터, 함수 Review & 과제 1, 2.
경찰학 세미나 제 5 강 경찰관직무집행법 2조 5호의 의미 신라대학교 법경찰학부 김순석.
Presentation transcript:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

중위 → 후위 : 프로그램 구현 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으로 초기화 일련의 변환 과정을 이 반복문 안에서 수행 스택에 남아 있는 모든 연산자를 이동시키는 반복문 변환된 수식을 반환!

중위 → 후위 : 프로그램 구현 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문에 담는다!

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

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

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

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

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

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

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

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