chap x: G입력

Transcription

1 원형큐 (Circular Queue) [2] [3] [2] [3] [1] [4] [1] [4] [0] [5] front = 0, rear = 0 [2] [3] [0] [5] front = 0, rear = 3 [1] [4] [0] [5] front = 0, rear = 0 최대큐이용률 = MAX_Q_SIZE 1 3 장. 스택과큐 (Page 13)

2 원형큐의구현 void addq(element item) { // 원형큐에새로운항목을추가 rear = (rear + 1) % MAX_QUEUE_SIZE; if (rear == front) { queue_full(); return; queue[rear] = item; element deleteq() { // 원형큐의항목을 return if (front == rear) return queue_empty(); front = (front + 1) % MAX_QUEUE_SIZE; return queue[front]; 3 장. 스택과큐 (Page 14)

3 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 15)

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

5 그림 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 17)

6 미로찾기프로그램의구현 (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 18)

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

8 미로찾기프로그램의구현 (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 20)

9 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 21)

10 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 22)

11 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 = pop(); // top의위치로이동 row = position.row; col = position.col; dir = position.dir; 3 장. 스택과큐 (Page 23)

12 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; push(position); // 현재좌표와방향을 stack 저장 row = next_row; // 안가본길로전진. 방향은북쪽 col = next_col; dir = 0; else ++dir; 3 장. 스택과큐 (Page 24)

13 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 25)

14 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 26)

15 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 27)

16 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 28)

17 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 29)

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

19 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 31)

20 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; // 수식문자열의현재판독위치 top = -1; // stack 초기화 token = get_token(&symbol, &n); while (token!= eos) { if (token == operand) push(symbol 0 ); // 피연산자를만나면스택에저장 3 장. 스택과큐 (Page 32)

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

22 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 34)

23 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 35)