chap x: G입력

Transcription

1 3. 미로찾기 (Mazing Problem) 2 차원배열을이용한미로의구현 maze[row][column]: 0 길, 1 벽 그림 3.8 참조 이동방향 8 방향 (N, NE, E, SE, S, SW, W, NW) 각방향에대한 maze 배열의첨자변환 : 그림 3.9 경계지역 : 8 방향이아님. ( 모서리 : 3 방향, 변 : 5 방향 ) m p 미로를 (m + 2) (p + 2) 미로로변환 각경계영역의 maze 배열값은 1 로설정 입구 : maze[1][1], 출구 : maze[m][p] 3 장. 스택과큐 (Page 1)

2 그림 3.8: 예제미로 entrance exit 3 장. 스택과큐 (Page 2)

3 그림 3.9: 이동가능지점 NW [row 1][col 1] N [row 1][col] NE [row 1][col + 1] W [row][col 1] X [row] [col] E [row][col + 1] [row + 1][col 1] SW [row + 1][col] S [row + 1][col + 1] SE 3 장. 스택과큐 (Page 3)

4 미로찾기프로그램의구현 (1) 8 가지이동방향을구현하기위해 move[8] 배열사용 typedef struct { short int x; short int y; offsets; offsets move[8]; Name Dir move[dir].x move[dir].y N NE E SE S SW W NW 장. 스택과큐 (Page 4)

5 그림 3.8: 예제미로 entrance exit 3 장. 스택과큐 (Page 5)

6 미로찾기프로그램의구현 (2) 현재좌표가 (row, col) 일경우, 다음이동좌표의계산 next_row = row + move[dir].x next_col = col + move[dir].y 북쪽 (N) 부터다음이동좌표를차례대로계산하여이동가능한지 ( 즉, 길 or 벽 ) 확인한후, 길이면이동. 한번갔었던길을다시갈필요는없으므로, 기존에다녀온길들을 mark[m+2][p+2] 배열에저장 모든 mark[row][col] 의값은 0 으로초기화 maze[i][j] 를방문한후, mark[i][j] 를 1 로설정 갔다가길이없을경우돌아와야지? stack[] 사용 #define MAX_STACK_SIZE 100 // = m p typedef struct { short int row; short int col; short int dir; element; element stack[max_stack_size]; 3 장. 스택과큐 (Page 6)

7 Program 3.7: 미로찾기초기버전 (1) 미로의입구좌표와 N 방향으로 stack 초기화 // 최적화? while ( stack is not empty ) { // stack top 의위치로이동 <row, col, dir> = delete from top of stack; while ( there are more moves from current position ) { <next_row, next_col> = coordinate of next move; dir = direction of move; if ((next_row == EXIT_ROW) && (next_col == EXIT_COL)) success; 3 장. 스택과큐 (Page 7)

8 Program 3.7: 미로찾기초기버전 (2) if (maze[next_row][next_col] == 0 && mark[next_row][next_col] == 0) { // 정상적인길이며아직방문한적이없음 mark[next_row][next_col] = 1; // 이제방문 // 현재좌표와방향을 stack에저장 add <row, col, dir> to the top of the stack; row = next_row; col = next_col; dir = north; printf( No path found \ n ); 3 장. 스택과큐 (Page 8)

9 Program 3.7: 미로찾기최종버전 (1) void path(void) { // 미로를통과하는경로가존재할경우, 이를출력 int i, row, col, next_row, next_col, dir; int found = FALSE; element position; // 미로의입구좌표와 E 방향으로 stack 초기화 mark[1][1] = 1; top = 0; stack[0].row = 1; stack[0].col = 1; stack[0].dir = 2; while ( top > -1 &&!found ) { // stack이 empty가아니고, 아직 // 경로를발견못할때까지실행 position = delete(&top); // top의위치로이동 row = position.row; col = position.col; dir = position.dir; 3 장. 스택과큐 (Page 9)

10 Program 3.7: 미로찾기최종버전 (2) while ( dir < 8 &&!found ) { // 8방향을차례대로검사 next_row = row + move[dir].x; // move in direction dir next_col = col + move[dir].y; if ( next_row == EXIT_ROW && next_col == EXIT_COL ) found = TRUE; // 출구발견. 경로는어디에? else if (!maze[next_row][next_col] &&!mark[next_row][next_col] ) { // 아직안가본길 mark[next_row][next_col] = 1; position.row = row; position.col = col; position.dir = ++dir; add( &top, position ); // 현재좌표와방향을 stack 저장 row = next_row; // 안가본길로전진. 방향은북쪽 col = next_col; dir = 0; else ++dir; 3 장. 스택과큐 (Page 10)

11 Program 3.7: 미로찾기최종버전 (3) if (found) { // stack 에저장된경로출력 printf( " The path is: \ n " ); printf ( "row col \ n" ); for ( i=0; i <= top; i++ ) printf( " %2d %5d ", stack[i].row, stack[i].col ); printf( " %2d %5d \ n ", row, col ); printf( " %2d %5d \ n ", EXIT_ROW, EXIT_COL ); else printf( " The maze does not have a path \ n " ); 3 장. 스택과큐 (Page 11)

12 4. 수식계산 (Evaluation of Expressions) 수식에서 Precedence 와 Associativity Precedence: 연산자들간의우선순위 Associativity: 동일한우선순위를갖는연산자들간의실행순서 Example x = a / b c + d * e a * c x = ( ( a / ( b c + d ) ) * ( e a ) * c 3 장. 스택과큐 (Page 12)

13 C 언어에서 Precedence/Associativity(1) Token Operator Precedence Associativity ( ) [ ] >. function call array element struct or union member 17 left to right ++ increment, decrement 2 16 left to right ++! ~ + & sizeof decrement, increment 3 logical not one s complement unary minus or plus address or indirection size ( in bytes ) 15 right to left ( type ) type cast 14 right to left / % multiplicative 13 left to right + binary add or subtract 12 left to right 3 장. 스택과큐 (Page 13)

14 C 언어에서 Precedence/Associativity(2) << >> shift 11 left to right > >= < <= relational 10 left to right ==!= equality 9 left to right & bitwise and 8 left to right ^ bitwise exclusive or 7 left to right bitwise or 6 left to right && logical and 5 left to right logical or 4 left to right?: conditional 3 right to left = += -= /= = %= assignment 2 right to left <<= >>= &= ^= =, comma 1 left to right 3 장. 스택과큐 (Page 14)

15 Infix 수식과 Postfix 수식 Infix: 사람들이사용하는수식 Postfix: 컴퓨터가사용하는수식 Precedence 와 associativity 를고려할필요없음 한번의 left-to-right scan 으로수식계산가능 Infix * 4 a * b + 5 ( ) * 7 a * b / c ( ( a / ( b c + d ) ) * ( e a ) * c a / b c + d * e a * c Postfix * + a b * * a b * c / a b c d + / e a - * c * a b / c d e * + a c * - 3 장. 스택과큐 (Page 15)

16 Postfix 수식의계산 Stack 을이용 : 6 2 / * + Token Stack[0] Stack[1] Stack[2] Top 6 2 / * / 2 6 / / / / / * 2 6 / * 장. 스택과큐 (Page 16)

17 Postfix 수식계산을위한자료구조 #define MAX_STACK_SIZE 100 #define MAX_EXPR_SIZE 100 typedef enum { lparen, rparen, plus, minus, times, divide, mod, eos, operand precedence; int stack [ MAX_STACK_SIZE ]; // global stack char expr [ MAX_EXPR_SIZE ]; // input string 3 장. 스택과큐 (Page 17)

18 Program 3.9: Postfix 수식계산 (1) int eval (void) { // expr[] 배열에문자열로저장된 postfix 수식계산. // expr[] 과 stack[], 그리고 top 은전역변수임. // get_token() 함수는수식의각문자의 precedence 를 return // 수식에서피연산자는한문자로구성된다고가정. precedence token; char symbol; int op1, op2; int n = 0; // 수식문자열의현재판독위치 int top = -1; token = get_token (&symbol, &n); while (token!= eos) { if (token == operand) add (&top, symbol 0 ); // 피연산자를만나면스택에저장 3 장. 스택과큐 (Page 18)

19 Program 3.9: Postfix 수식계산 (2) else { // stack에서피연산자 2개를제거한후이를이용하여 // 수식을계산한후결과를다시 stack에저장 op2 = delete ( &top ); // stack delete op1 = delete ( &top ); switch ( token ) { case plus : add ( &top, op1 + op2 ); break; case minus : add ( &top, op1 op2 ); break; case times : add ( &top, op1 * op2 ); break; case divide : add ( &top, op1 / op2 ); break; case mod : add ( &top, op1 % op2 ); token = get_token ( &symbol, &n ); return delete ( &top ); /* return result */ 3 장. 스택과큐 (Page 19)

20 Program 3.9: Postfix 수식계산 (3) precedence get_token (char *symbol, int * n) { // 수식문자열에서다음문자를검사하여해당 token 을반환 *symbol = expr[(*n)++]; switch (*symbol) case ' ( ' : return lparen; case ' ) ' : return rparen; case ' + ' : return plus; case ' ' : return minus; case ' / ' : return divide; case ' * ' : return times; case ' % ' : return mod; case ' ' : return eos; default : return operand; // 오류검사없음. 피연산자 3 장. 스택과큐 (Page 20)

21 Infix 수식을 Postfix 수식으로변환 알고리즘 1: 괄호를이용하여변환 예 : a / b c + d * e a * c ((((a / b) c) + (d * e)) (a * c)) a b / c d e * + a c * 두단계처리로인해비효율적임 알고리즘 2: Stack 을이용하여변환 예 : 그림 3.15, 그림 3.16 precedence(top) < precedence(incoming) 일때까지입력연산자를 stack 에저장 괄호가있는수식처리에주의 3 장. 스택과큐 (Page 21)

22 그림 3.15: 수식변환의예 (1) Token a Stack [0] [1] [2] Top -1 Output a a b + 0 ab + 1 ab c + 1 abc eos -1 abc + 3 장. 스택과큐 (Page 22)

23 그림 3.15: 수식변환의예 (2) Token Stack [0] [1] [2] Top Output a -1 a 0 a ( ( 1 a b ( 1 ab + ( + 2 ab c ( + 2 abc ) 0 abc + 0 abc + d 0 abc + d eos 0 abc + d 3 장. 스택과큐 (Page 23)

24 수식변환을위한자료구조 연산자를위한 stack 필요 괄호연산자를처리하기위한두종류의우선순위 int isp[]: stack 에저장된연산자의우선순위 int icp[]: 입력연산자의우선순위 precedence stack[ MAX_STACK_SIZE ]; /* isp and icp arrays - index is value of precedence lparen, rparen, plus, minus, times, divide, mod, eos */ int isp[ ] = { 0, 19, 12, 12, 13, 13, 13, 0 ; int icp[ ] = { 20, 19, 12, 12, 13, 13, 13, 0 ; 3 장. 스택과큐 (Page 24)

25 Program 3.11: 수식변환 (1) void postfix ( void ) { // 수식변환프로그램. (infix postfix) // expr[](infix 저장 ) 과 stack[] 은전역변수 char symbol; precedence token; int n = 0; int top = 0; stack[0] = eos; // place eos on stack for (token = get_token(&symbol, &n); token!= eos; token = get_token(&symbol, &n)) { if (token == operand) printf( %c, symbol); 3 장. 스택과큐 (Page 25)

26 Program 3.11: 수식변환 (2) else if (token == rparen) { // 왼쪽괄호가나올때까지 stack pop while (stack[top]!= lparen) print_token(delete(&top)); delete(&top); // 왼쪽괄호제거 else { // 우선순위가높은연산자 pop. associativity? while (isp[stack[top]] >= icp[token]) print_token(delete(&top)); add(&top, token); while ( (token = delete(&top) )!= eos) print_token(token); printf( \ n ); 3 장. 스택과큐 (Page 26)

27 5. 다중스택과큐 (Multiple Stacks and Queue) 스택이나큐를배열로구현할경우문제점 정적메모리할당. 스택 / 큐오버플로우혹은메모리낭비 다중스택과큐의기본개념 memory[msize] 에 n 개의스택 / 큐를저장하자 C 언어에서다중스택의구현 #define MSIZE 100 // 메모리크기 #define MAX_STACKS 10 // 최대스택수 + 1 // 전역메모리선언 element memory[msize]; int top[max_stacks]; int boundary[max_stacks]; int n; // 사용자가입력한스택의수 3 장. 스택과큐 (Page 27)

28 C 언어에서다중스택의구현 (1) memory[] 배열을 n 개의스택으로균등하게분할 top [0] = boundary [0] = -1; for ( i = 1; i < n; i++ ) top [i] = boundary [i] = ( MSIZE / n ) * i 1 ; boundary [n] = MSIZE 1; Stack_Full 과 Stack_Empty 조건 Stack_Full top[stack_no] == boundary[stack_no + 1] Stack_Empty top[stack_no] == boundary[stack_no] 3 장. 스택과큐 (Page 28)

29 다중스택의초기구성 0 1 m/n 2 m/n m-1 boundary[0] top[0] boundary[1] top[1] boundary[2] top[2] boundary[n] 모든스택은초기에 empty 이며, memory[] 배열을균등하게배분. 3 장. 스택과큐 (Page 29)

30 C 언어에서다중스택의구현 (2) void add ( int i, element item ) { // i- 번째스택에새로운 item 을추가 if (top[i] == boundary [i+1]) return ( stack_full ( i ) ); memory[++top[i]] = item; element delete ( int i ) { // i- 번째스택의 top 에저장된항목을삭제 if ( top[i] == boundary[i] ) return ( stack_empty ( i ) ); return ( memory[top[i]--] ); 3 장. 스택과큐 (Page 30)

31 Stack_Full 의구현 배경 i- 번째스택이 full(top[i] == boundary[i+1]) 이라도 memory[] 배열에는여유공간이있을수있다. boundary[] 와 top[] 을변경하여 i- 번째스택에추가적인공간을제공하자 구현방법 가정 : top[stack_no] == boundary[stack_no+1] j (stack_no < j < n && top[j] < boundary[j + 1]) 오른쪽스택에여유공간있음. 한칸씩 Shift Right. j (0 < k < stack_no && top[k] < boundary[k + 1]) 왼쪽스택에여유공간있음. 한칸씩 Shift Left. Otherwise, Memory_FULL 실제로구현해볼것! 3 장. 스택과큐 (Page 31)

32 Stack_Full 의동작예 t[0] t[1] t[2] t[0] t[1] t[2] b[0] b[1] b[2] b[3] b[0] b[1] b[2] b[3] add(1,x) t[0] t[1] t[2] add(1,x) t[0] t[1] t[2] b[0] b[1] b[2] b[3] b[0] b[1] b[2] b[3] t[0] t[1] t[2] t[0] t[1] t[2] b[0] b[1] b[2] b[3] add(0, y)? b[0] b[1] b[2] b[3] add(2, y)? 3 장. 스택과큐 (Page 32)