03장.스택

Size: px

Start display at page:

Download "03장.스택"

혜경 단
5 years ago
Views:

1 DT STRUCTURES USING C CHPTER 스택 1/30

2 스택이란? 스택 (stack): 쌓아놓은더미 후입선출 (LIFO:Last-In First-Out) 가장최근에들어온데이터가가장먼저나감 2/30

3 스택의구조 스택상단 : top 스택하단 : 불필요 요소, 항목 공백상태, 포화상태 삽입, 삭제연산 3/30

4 스택추상자료형 객체 : 무엇이든가능 ( 닦은접시들 ) 연산 ( 접시함의경우 ) 닦은접시를보관함에넣음 -> 새로운항목을스택에삽입 보관함에서접시하나를꺼냄 -> 하나의항목을꺼냄. 보관함에접시가있는지살핌 -> 스택이비어있는지살핌 고급접시함 고급기능추가 접시를꺼내지않고맨위의접시가무엇인지알아본다. 보관함이가득차있는지를살핀다. 보관함내의접시개수를알려준다. 보관함내에어떤접시가있는지모니터에출력해준다. 4/30

5 스택추상자료형 Stack DT 데이터 : 후입선출 (LIFO) 의접근방법을유지하는요소들의모음 연산 : init(): 스택을초기화한다. is_empty(): 스택이비어있으면 TRUE를아니면 FLSE를반환한다. is_full(): 스택이가득차있으면 TRUE를아니면 FLSE을반환한다. size(): 스택내의모든요소들의개수를반환한다. push(x): 주어진요소 x를스택의맨위에추가한다. pop(): 스택맨위에있는요소를삭제하고반환한다. peek(): 스택맨위에있는요소를삭제하지않고반환한다. 5/30

6 스택의연산 삽입 (push), 삭제 (pop) C push() push(b) push(c) C pop() B B B 초기상태 is_empty(): 스택이공백상태인지검사 is_full(): 스택이포화상태인지검사 peek(s): 요소를스택에서삭제하지않고보기만하는연산 ( 참고 ) pop 연산은요소를스택에서완전히삭제하면서가져옴. 6/30

7 스택의용도 함수호출 Undo기능 괄호검사 계산기 미로탐색등 7/30

8 배열을이용한스택의구현 1 차원배열 stack[ ] top: 가장최근에입력되었던자료를가리키는변수 stack[0] stack[top]: 먼저들어온순으로저장 공백상태이면 top은 -1 data[mx_stck_size] data[4] 4 4 E top data[3] 3 3 D data[2] C top C B data[1] B 0 0 data[0] -1 공백상태 top -1 포화상태 8/30

9 Push 연산 C C top 1 B top 1 B 0 0 push(x) if is_full(s) then error "overflow" else top top+1 data[top] x 9/30

10 Pop 연산 C top 2 1 B 1 B top 0 0 pop() if is_empty() then error "underflow" else e data[top] top top-1 return e 10/30

11 스택의구현 데이터 data[] top 전역변수로선언 typedef int Element; Element data[mx_stck_size]; int top; int is_empty() { if( top == -1 ) return 1; else return 0; 간단한함수 void init_stack() { top = -1; int size() { return top+1; int is_empty() { return (top == -1); int is_full() { return (top == MX_STCK_SIZE-1); 11/30

12 스택의주요함수 void push ( Element e ) { if( is_full() ) error (" 스택포화에러 "); data[++top] = e; Element pop ( ) { if( is_empty() ) error (" 스택공백에러 "); return data[top--]; Element peek ( ) { if( is_empty() ) error (" 스택공백에러 "); return data[top]; void print_stack(char msg[]) { int i; printf("%s[%2d]= ", msg, size()) ; for (i=0 ; i<size() ; i++ ) printf("%2d ", data[i]); printf("\n"); 12/30

13 사용방법 void main() { int i; init_stack(); for( i=1 ; i<10 ; i++ ) push( i ); print_stack(" 스택 push 9 회 "); printf("\tpop() --> %d\n", pop()); printf("\tpop() --> %d\n", pop()); printf("\tpop() --> %d\n", pop()); print_stack(" 스택 pop 3 회 "); 9 번 push() 연산후 3 번 pop() 연산후 설명출력현재항목수스택내용 13/30

14 구조체를저장하는스택 학생정보스택 구조체정의 Element 정의 typedef struct Student_t { int id; char name[32]; char dept[32]; Student; 출력함수수정 typedef Student Element; void print_stack(char msg[]) { int i; printf("%s[%2d]= ", msg, size()) ; for (i=0 ; i<size() ; i++ ) printf("\n\t%-15d %-10s %-20s", data[i].id, data[i].name, data[i].dept); printf("\n"); 14/30

15 학생정보스택프로그램 Student get_student(int id, char* name, char* dept) { Student s; s.id = id; strcpy(s.name, name); strcpy(s.dept, dept); return s; void main() { init_stack( ); push( get_student( , " 홍길동 ", " 컴퓨터공학과 ") ); push( get_student( , " 이순신 ", " 기계공학과 ") ); push( get_student( , " 김연아 ", " 체육과 ") ); push( get_student( , " 황희 ", " 법학과 ") ); print_stack(" 친구 4 명삽입후 "); pop( ); print_stack(" 친구 1 명삭제후 "); 15/30

16 스택구현의다른방법 연결리스트를이용하는방법 16/30

17 스택응용 : 괄호검사 괄호의종류 : 대중소 ( [, ] ), ( {, ), ( (, ) ) 조건 왼쪽괄호의개수와오른쪽괄호의개수가같아야한다. 왼쪽괄호는오른쪽괄호보다먼저나와야한다. 괄호사이에는포함관계만존재한다. 잘못된괄호사용의예 (a(b) a(b)c) a{b(c[d]ef) 17/30

18 괄호검사예 { [ (i+1 ) ]=0; 비교 비교 비교 [ { ( 성공 ( [ [ [ { { { { { if( ( i==0 ) && (j==0 ) [ ( i+1 ] ) =0; 비교 비교 비교 오류 ( ( 오류 ( ( ( ( ( ( ( ( ( ( [ [ ( 18/30

19 괄호검사알고리즘 알고리즘의개요 문자열에있는괄호를차례대로조사하면서왼쪽괄호를만나면스택에삽입하고, 오른쪽괄호를만나면스택에서 top 괄호를삭제한후오른쪽괄호와짝이맞는지를검사한다. 이때, 스택이비어있으면조건 1 또는조건 2 등을위배하게되고괄호의짝이맞지않으면조건 3 등에위배된다. 마지막괄호까지를조사한후에도스택에괄호가남아있으면조건 1 에위배되므로 0( 거짓 ) 을반환하고, 그렇지않으면 1( 참 ) 을반환한다. 19/30

20 괄호검사알고리즘 check_matching(expr) while ( 입력 expr 의끝이아니면 ) ch expr 의다음글자 switch(ch) case '(': case '[': case '{': ch 를스택에삽입 break case ')': case ']': case ']': if ( 스택이비어있으면 ) then 오류 else 스택에서 open_ch 를꺼낸다 if (ch 와 open_ch 가같은짝이아니면 ) break then 오류보고 if( 스택이비어있지않으면 ) then 오류 왼쪽괄호이면스택에삽입 오른쪽괄호이면스택에서삭제비교 20/30

21 괄호검사테스트프로그램 void main() { char expr[4][80] = { "{[(i+1)]=0;", "if((i==0) && (j==0)", "[(i+1])=0;", "[i] =f)(;" ; int err, i; for( i=0 ; i<4 ; i++ ) { err = check_matching(expr[i]); if( err == 0 ) printf(" 괄호정상 : %s\n", expr[i]); else printf(" 괄호오류 : %s ( 조건 %d 위반 )\n", expr[i], err); 21/30

22 수식의계산 수식의표기방법 : 전위 (prefix), 중위 (infix), 후위 (postfix) 중위표기법 전위표기법 후위표기법 2+3*4 +2*34 234*+ a*b+5 +5*ab ab*5+ (1+2) 컴퓨터에서의수식계산순서 중위표기식-> 후위표기식-> 계산 2+3*4 -> 234*+ -> 14 모두스택을사용 22/30

23 후위표기수식계산 알고리즘 Calc_postfix (expr) 스택초기화 ; for 항목 in expr do if ( 항목이피연산자이면 ) s.push(item); if ( 항목이연산자 op 이면 ) then second pop(); result pop(); first pop(); temp first op second; // op 는 +-*/ 중의하나 push(temp); 23/30

24 후위표기수식계산예 후위표기수식 : 8 2 / * / 2 = 피연산자 8 -> push( 8) 피연산자 2 -> push( 2) 연산자 / pop( ) ->2 pop( ) ->8 8/ 2 = 4 push( 4) 피연산자 3 -> push( 3) 후위표기수식 : 8 2 / * = * 연산자 - pop( ) ->3 pop( ) ->4 4-3 = 1 push( 1) 피연산자 3 push( 3) 피연산자 2 push( 2) 연산자 * push( 3*2) 연산자 + push( 1+6) 24/30

25 후위표기수식계산프로그램 double calc_postfix( char expr[] ) {... init_stack( ); while( expr[i]!= '\0' ) { c = expr[i++]; if (c>='0' && c<='9') { val = c - '0'; push( val ); else if( c=='+' c=='-' c=='*' c=='/' ){... switch( c ) { case '+': push( val1 + val2); break;... void main() { char expr[2][80] = { "8 2 / * +", "1 2 / 4 * 1 4 / *" ; printf(" 수식 : %s = %lf\n", expr[0], calc_postfix(expr[0])); printf(" 수식 : %s = %lf\n", expr[1], calc_postfix(expr[1])); 계산결과 25/30

26 중위표기수식의후위표기변환 중위표기와후위표기 중위와후위표기법의공통점 : 피연산자의순서가동일 연산자들의순서만다름 ( 우선순위순서 ) 알고리즘 연산자만스택에저장했다가출력 2+3*4 -> 234*+ 피연산자를만나면그대로출력 연산자를만나면스택에저장했다가스택보다우선순위가낮은연산자가나오면그때출력 왼쪽괄호는우선순위가가장낮은연산자로취급 오른쪽괄호가나오면스택에서왼쪽괄호위에쌓여있는모든연산자를출력 26/30

27 중위 후위표기변환예 중위표기수식 연산자스택 후위표기수식 중위표기수식 연산자스택 후위표기수식 + B * C * B + C + B * C * B + C + B * C * B + C + * + B * C B * B + C B + * + B * C 연산자우선순위비교 ( * > +) * 를바로삽입 * + B * B + C 연산자우선순위비교 ( +<= *) 우선순위가같거나높은 * 를먼저출력후 + 삽입 + B * + B * C * + B C * B + C + B * C + B * C B C * + * B + C B * C + 27/30

28 후위표기변환예 중위표기수식 ( + B ) * C 연산자스택 후위표기수식 ( + B ) * C 괄호는일단삽입 ( ( + B ) * C ( + B ) * C + ( 괄호는우선순위가가장낮음 ->+ 삽입 ( + B ) * C + B ( ( + B ) * C B + ) 가나오면 ( 전까지모두출력괄호는후위표기식에출력하지않음 ( ( + B ) * C B * ( + B ) * C B * + + C ( + B ) * C B + C * 28/30

29 후위표기변환알고리즘 Infix_to_postfix(expr) 스택초기화. while (expr 에처리할항이남아있으면 ) term 다음에처리할항 ; switch (term) case 피연산자 : term 을출력 ; break; case 왼쪽괄호 : push(term); break; case 오른쪽괄호 : e pop(); while( e 왼쪽괄호 ) do e 를출력 ; break; e pop(); case 연산자 : while ( peek() 의우선순위 term 의우선순위 ) do e pop(); e 를출력 ; push(term); break; while( not is_empty() ) do e pop(); e 를출력 ; 29/30

30 후위표기변환프로그램 static int precedence( char op ) { switch (op) { case '(' : case ')' : return 0; case '+' : case '-' : return 1; case '*' : case '/' : return 2; return -1; void infix_to_postfix( char expr[] ) {... void main() { char expr[2][80] = { "8/2-3+(3*2)", "1/2* 4 * (1/4)" ; printf(" 중위수식 : %s ==> 후위수식 :", expr[0]); infix_to_postfix(expr[0]); printf(" 중위수식 : %s ==> 후위수식 :", expr[1]); infix_to_postfix(expr[1]); 후위표기변환결과 30/30

03장.스택.key

03장.스택.key ---------------- DATA STRUCTURES USING C ---------------- 03CHAPTER 1 ? (stack): (LIFO:Last-In First-Out) 2 : top : ( index -1 ),,, 3 : ( ) ( ) -> ->. ->.... 4 Stack ADT : (LIFO) : init():. is_empty():