5.스택(강의자료).key

Size: px

Start display at page:

Download "5.스택(강의자료).key"

예담 국
7 years ago
Views:

1 CHP 5:

3 ? (stack):

4 (LIFO:Last-In First-Out):. D C B C B C B C B

5 (element) C (top) B (bottom)

6 (DT) : n element : create() ::=. is_empty(s) ::=. is_full(s) ::=. push(s, e) ::= e. pop(s) ::=. peek(s) ::=.

7 push(): pop():

8 push(): pop():

9 push(): pop():

10 push(): pop(): push()

11 push(): pop(): push()

12 push(): pop(): push()

13 push(): pop(): push()

14 push(): pop(): push() push(b)

15 push(): pop(): push() push(b)

16 push(): pop(): push() push(b) B

17 push(): pop(): push() push(b) B

18 push(): pop(): push() push(b) B

19 push(): pop(): push() push(b) B

20 push(): pop(): push() push(b) B B

21 push(): pop(): push() push(b) push(c) B B

22 push(): pop(): push() push(b) push(c) B C B

23 push(): pop(): push() push(b) push(c) B C B

24 push(): pop(): push() push(b) push(c) B C B

25 push(): pop(): push() push(b) push(c) C pop() B B

26 push(): pop(): push() push(b) push(c) C pop() B B

27 push(): pop(): push() push(b) push(c) C pop() B B B

28 is_empty(s): is_full(s): create(): peek(s): ( )pop.

29 (undo) int main() { int i=3; sub1(i);... int sub1(int a) { int j=5; sub2(j);... void sub2(int b) {... main PC=1 sub1 PC=20 a=3 main i=3 sub2 PC=150 b=5 sub1 PC=20 a=3 j=5 main i=3 sub1 PC=20 a=3 j=5 main i=3 main i=3

30 1 stack[ ] top stack[0], stack[top] top top top top

31 is_empty, is_full is_empty(s) is_full(s) if top = -1 then return TRUE else return FLSE if top = (MX_STCK_SIZE-1) then return TRUE else return FLSE 4 4 top top 0-1

32 push push(s, x) if is_full(s) then error "overflow" else top top+1 stack[top] x top top

33 pop pop(s, x) if is_empty(s) then error "underflow" else e stack[top] top top-1 return e top top

34 C typedef int element; typedef struct { element stack[mx_stck_size]; int top; StackType; element // void init(stacktype *s) { s->top = -1; // int is_empty(stacktype *s) { return (s->top == -1); // int is_full(stacktype *s) { return (s->top == (MX_STCK_SIZE-1));

35 // void push(stacktype *s, element item) { if( is_full(s) ) { fprintf(stderr," \n"); return; else s->stack[++(s->top)] = item; // element pop(stacktype *s) { if( is_empty(s) ) { fprintf(stderr, " \n"); exit(1); else return s->stack[(s->top)--]; // element peek(stacktype *s) { if( is_empty(s) ) { fprintf(stderr, " \n"); exit(1); else return s->stack[s->top];

36 push

37 Lab ivis.kr

38 (linked stack): : : top top NULL

39 typedef int element; typedef struct StackNode { element item; struct StackNode *link; StackeNode; typedef struct { StackNode *top; LinkedStackType; 9 top 7 3 NULL

40 push // void push(linkedstacktype *s, element item) top { StackNode *temp=(stacknode *)malloc(sizeof(stacknode)); if( temp == NULL (2) ){ (1) fprintf(stderr, " \n"); return; temp D else{ temp->item = item; temp->link = s->top; s->top = temp; C B NULL

41 // pop element pop(linkedstacktype *s) { if( is_empty(s) ) { else{ fprintf(stderr, " \n"); exit(1); StackNode *temp=s->top; int item = temp->item; s->top = s->top->link; free(temp); return item; top C B NULL temp

42 : ( [, ] ), ( {, ), ( (, ) ) ` (a(b) a(b)c) a{b(c[d]ef)

43 if( ( i==0 ) && (j==0 ) ( ) ( ( ( ( ( ( ( ( ( ( { [ (i+1 ) ]=0; ( [ { { [ { ( [ [ { { {

44 , top., ( ), 1( ).

45 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 ) then break if( ) then

46 // int check_matching(char *in) { StackType s; char ch, open_ch; int i, n = strlen(in); init(&s); for (i = 0; i < n; i++) { ch = in[i]; switch(ch){ case '(': case '[': push(&s, ch); break; case '{':

47 case ')': case ']': case '': if(is_empty(&s)) return FLSE; else { open_ch = pop(&s); if ((open_ch == '(' && ch!= ')') (open_ch == '[' && ch!= ']') (open_ch == '{' && ch!= '')) { return FLSE; break; if(!is_empty(&s)) return FLSE; return TRUE; int main() { if( check_matching("{ [(i+1)]=0; ") == TRUE ) printf(" \n"); else printf(" \n");

48 : (prefix), (infix), (postfix) 2+3*4 +2*34 234*+ a*b+5 +5*ab ab*5+ (1+2) > -> 2+3*4 -> 234*+ -> 14

49 ( ) 82/3-32*+ [0] [1] [2] [3] [4] [5] [6] / *

50 / / / 3 - -> -> -> 8/2= / / / 3-3 -> -> 4-1=1 -> =1

51 s. for in do if ( ) push(s, item) if ( op ) then second pop(s) first pop(s) result first op second // op +-*/ push(s, result) final_result pop(s);

52 // eval(char exp[]) { int op1, op2, value, i=0; int len = strlen(exp); char ch; StackType s; init(&s); for( i=0; i<len; i++){ ch = exp[i]; if( ch!= '+' && ch!= '-' && ch!= '*' && ch!= '/' ){ value = ch - '0'; // push(&s, value); else{ // op2 = pop(&s); op1 = pop(&s); switch(ch){ // case '+': push(&s,op1+op2); break; case '-': push(&s,op1-op2); break; case '*': push(&s,op1*op2); break; case '/': push(&s,op1/op2); break; return pop(&s);

53 ( ) ->. 2+3*4 -> 234*+ ->

54 ( a + b ) * c (

55 ( a + b ) * c a (

56 ( a + b ) * c + a (

57 ( a + b ) * c + a b (

58 ( a + b ) * c a b +

59 ( a + b ) * c a b + *

60 ( a + b ) * c a b + c *

61 ( a + b ) * c a b + c *

62 infix_to_postfix(exp) s while (exp ) ch switch (ch) case : while ( peek(s) ch ) do e pop(s) e push(s, ch); break; case : push(s, ch); break; case : e pop(s); while( e ) do e e pop(s) break; case : ch break; while( not is_empty(s) ) do e pop(s) e

63 // -> void infix_to_postfix(char exp[]) { int i = 0; char ch, top_op; int len = strlen(exp); StackType s; init(&s); for (i = 0; i<len; i++) { ch = exp[i]; // // switch (ch) { case '+': case '-': case '*': case '/': // // while (!is_empty(&s) && (prec(ch) <= prec(peek(&s)))) printf("%c", pop(&s)); push(&s, ch); break; case '(': // push(&s, ch); break;

64 case ')': // top_op = pop(&s); // while( top_op!= '(' ){ printf("%c", top_op); top_op = pop(&s); break; default: // printf("%c", ch); break; while(!is_empty(&s) ) // printf("%c", pop(&s)); // main() { infix_to_postfix("(2+3)*4+9");

65 m x

67 s x, while( ) do ; if(,,, ) then push if( is_empty(s) ) then else ;

68 #define MX_STCK_SIZE 100 #define MZE_SIZE 6 typedef struct StackObjectRec { short r; short c; StackObject; StackObject stack[mx_stck_size]; int top = -1; StackObject here={1,0, entry={1,0; char maze[mze_size][mze_size] = { {'1', '1', '1', '1', '1', '1', ; {'e', '0', '1', '0', '0', '1', {'1', '0', '0', '0', '1', '1', {'1', '0', '1', '0', '1', '1', {'1', '0', '1', '0', '0', 'x', {'1', '1', '1', '1', '1', '1',

69 void pushloc(int r, int c) { if( r < 0 c < 0 ) return; if( maze[r][c]!= '1' && maze[r][c]!= '.' ){ StackObject tmp; tmp.r = r; tmp.c = c; push(tmp); void printmaze(char m[mze_size][mze_size]) {

70 void printstack() { int i; for(i=5;i>top;i--) printf(" \n"); for(i=top;i>=0;i--) printf(" (%01d,%01d) \n", stack[i].r, stack[i].c); printf(" \n");

71 void main() { int r,c; here = entry; printmaze(maze); printstack(); while ( maze[here.r][here.c]!='x' ){ printmaze(maze); r = here.r; c = here.c; maze[r][c] = '.'; pushloc(r-1,c); pushloc(r+1,c); pushloc(r,c-1); pushloc(r,c+1);

72 printstack(); if( isempty() ){ printf(" \n"); printf(" \n"); return; else here = pop(); printmaze(maze); printstack(); getch();

74 Last In First Out,,

75 #6 5 Exercises 2-16, : 5 2

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():