자료구조: CHAP 5 스택 2017. 5. 4 순천향대학교 컴퓨터공학과 하 상 호

스택이란? 스택(stack): 쌓아놓은 더미

스택의 특징 삽입, 삭제가 한 쪽 끝에서만 이루지도록 제한 후입선출(LIFO:Last-In First-Out): 가장 최근에 들어온 데이터가 가장 먼저 나감. C A B D

스택의 구조 요소(element) 스택 상단(top) C B A 스택 하단(bottom)

스택의 ADT 객체: 0개 이상의 원소를 가진 유한 순서 리스트 연산: s: 스택, item: 원소 create_stack() ::= 빈 스택 생성 is_empty(s) ::= if (s가 비어 있으면) then return true else return false is_full(s) ::= if (s가 꽉 차있으면) then return true push(s, item) ::= s의 상단에 item을 삽입 pop(s) ::= if (is_empty(s)) then return error else s의 상단의 항목을 삭제하여 반환 peek(s) ::= if (is_empty(s)) then return error else s의 상단의 항목을 반환 delete(s) ::= if (is_empty(s)) then return error else s의 상단의 항목을 삭제

스택의 ADT 스택 사용 프로그램 // 스택 정의 procedure main() create_stack(); // 스택 생성 // 스택에 값 저장 push(1); push(2); push(3); // print stack while (!is_empty() ) do print( pop() ); repeat end main

스택의 연산 삽입(push), 삭제(pop) 초기상태 push(A) push(B) push(C) pop() A B C

스택의 용도 입력 순서와 역순의 출력이 필요한 경우 함수 호출 편집기에서 undo 기능

스택 표현 배열 리스트 4 9 3 top 2 top 9 7 1 7 3 3 NULL 리스트 배열

스택 구현: 배열 1차원 배열로 표현 스택 크기 원소의 타입 element stack[n]; int top; 스택 상단 표시 4 4 4 top 3 3 3 2 2 top 2 1 1 1 -1 top -1 -1 공백상태 포화상태

스택 구현 배열 create_stack() { element stack[n]; // 인덱스 범위: 0 ~ n-1 top <- -1; } is_empty(stack) if (top < 0)then true else return false; is_full(stack) is(top >= n-1) then return true; 4 3 2 top 9 1 7 3 배열

스택 구현: 배열 4 3 2 1 top 4 3 2 top 1 push(stack, item) { 2 1 4 3 top push(stack, item) { if (is_full(stack)) then stack_full(); else { top <- top + 1; stack[top] <- item; } pop(stack) if (is_empty(stack)) then stack_empty(); item <- stack[top]; top <- top – 1; return item; 2 1 4 3 top

스택 구현: 리스트 리스트 create_stack() { top <- null; } is_empty(stack) if (top = null )then return true else return false; push(stack, item) // item 포함 노드의 생성 및 최상단에 위치 pop(stack) // 최상단 노드의 데이터 반환 9 top 7 3 NULL 리스트

C: 스택 타입 정의 프로그램에서 여러 개의 스택 사용시 편리 스택 연산 표현 (C 코드) void init(stack_type *s) int is_empty(stack_type s) int is_full(stack_type s) void push(stack_type *s, element item) element pop(stack_type *s) define MAX_STACK_SIZE 100 typedef int element ; typedef struct { element stack[MAX_STACK_SIZE]; int top; } stack_type;

스택 응용 괄호 검사 수식 계산 미로 탐색

스택 응용: 괄호 검사 수학 수식은 소괄호, 중괄호, 대괄호를 사용하여 표현 다음 수식에서 괄호의 쌍이 올바른가?  

스택 응용: 괄호 검사 수학 수식에서 괄호 검사 조건 예제: 다음 수식에서 괄호가 올바르게 사용되었는가? 왼쪽 괄호의 개수와 오른쪽 괄호의 개수는 동일 같은 유형의 괄호에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나온다. 괄호 사이에는 포함관계만 존재한다. 예제: 다음 수식에서 괄호가 올바르게 사용되었는가? 주어진 수식으로부터 괄호를 어떻게 검사하는가? { a[(i+1)] = 0; } if ((i==0) && (j == 0) a[(i+1]) = 0;

스택 응용: 괄호 검사 스택을 이용한 수식 괄호 검사 알고리즘 개요 왼쪽 괄호가 나오면 스택에 삽입 오른쪽 괄호가 나오면 스택으로부터 원소를 삭제하여 반환된 괄호와 동일한 유형인지를 검사. 수식 끝에 도달하였고 스택이 비어 있으면, 수식 괄호는 올바르게 사용된 경우임 스택에 삽입 스택에서 꺼내어 비교 { a[(i+1)] = 0; } if ((i==0) && (j == 0) a[(i+1]) = 0;

스택 응용: 괄호 검사 다음 수식을 스택을 이용하여 괄호 검사하라. { a[(i+1)] = 0; }

스택 응용: 괄호 검사 다음 수식을 스택을 이용하여 괄호 검사하라. if ((i==0) && (j == 0)

스택 응용: 괄호 검사 (1) 알고리즘 paren_test(exp: array [1..SIZE] of characters) // 수식에 괄호‘(‘만을 포함한다고 가정 // 수식 괄호가 올바르면 true, 그렇지 않으면 false 반환 // 스택 s를 가정 { while (exp의 끝에 도달하지 않았으면) do symbol <- get_symbol(); // exp의 다음번째 문자 repeat // 스택이 비어 있는지 유무 고려 }

스택 응용: 괄호 검사 (2) 알고리즘 paren_test(exp: array [1..SIZE] of characters) // 수식에 괄호가 ‘(‘, ‘]’, ‘}’을 포함한다고 가정 // 수식 괄호가 올바르면 true, 그렇지 않으면 false 반환 // 스택 s가 정의되어 있다고 가정 { while (exp의 끝에 도달하지 않았으면) do symbol <- get_symbol(); // exp의 다음번째 문자 case symbol = ‘(‘ or ‘[‘ or ‘{‘: symbol = ‘)’: symbol = ‘]’: symbol = ‘}’: end case repeat if is_empty(stack) then return true; else return false; end if } 알고리즘

폴랜드 논리학자 Jan Lucasiewicz이 고안하여 폴리쉬 표기법(polish notation)이라고도 함 스택 응용: 수식 계산 폴랜드 논리학자 Jan Lucasiewicz이 고안하여 폴리쉬 표기법(polish notation)이라고도 함 수식 표기법 다음 수식의 후위식 표기법(postfix notation)은? A+B*C-D/E +*ab5 ++127

수식 계산 후위 표기식의 이점은? 연산 순서가 간단 괄호가 필요없다 => 컴퓨터는 중위식을 후위식으로 변환하여 수식 계산 중위식을 후위식으로 어떻게 변환하는가? 후위식을 어떻게 평가하는가?

후위 식 평가 다음 후위 식을 평가하라. (Hint 스택 이용) 8 2 / 3 – 3 2 * +

후위 식 평가 1 2 3 8 / - 4 피연산자-> 삽입 연산자-> 8/2=4 삽입 연산자-> 4-1=1 삽입 1 2 3 8 / - 4 피연산자-> 삽입 연산자-> 8/2=4 삽입 연산자-> 4-1=1 삽입 종료->전체 연산 결과=1

후위 식 평가 알고리즘 eval_postfix(exp: array [1..size] of characters) // 후위식 exp를 평가하여 그 결과를 반환 // 스택 생성 및 초기화 while (exp의 끝에 도달하지 않았으면) do token <- get_token(exp); case { token = operand: token = operator: endcase repeat return pop(stack)); // 결과값 반환 end eval_postfix 수치가 두자리 이상이면?

후위 표기식 변환 방법 1 (수동변환) 후위 표기식을 연산자 기준(우선순위 반영)으로 완전히 괄호로 묶는다. 각 연산자를 묶고 있는 괄호의 오른쪽 괄호 밖으로 연산자를 이동 괄호를 모두 제거한다. 예제: A + B * C – D / E 수식을 한번 읽어가면서 변환 가능한가?

후위 표기식 변환 방법 2 (스택을 이용한 자동변환) 식을 읽어가면서 피연산자는 바로 출력 연산자는 스택에 넣어두고, 적절한 시기에 스택에서 꺼내어 출력 예제: A + B * C A * B + C (A+B) * C A + B * C – D / E A * (B + C) / D 연산자를 언제 출력하는가? 괄호는 어떻게 처리하는가?

후위 표기식 변환 연산자를 언제 스택에 넣고, 꺼내는가? 수식에서 읽어들인 연산자와 스택 상단의 연산자간의 우선순위를 비교하는 것이 필요 수식상의 연산자 우선순위(PIE), 스택상의 연산자 우선순위(PIS) If (PIE <= PIS) then 스택 상단의 연산자를 꺼내어 출력하고, 이 과정을 반복 (다시 스택 상단의 연산자의 비교) else 수식상의 연산자를 스택 상단에 저장 예제: A + B * C – D / E

후위 표기식 변환 괄호는 연산자처럼 취급: A * (B + C) / D 왼쪽 괄호 오른쪽 괄호는? 연산자 PIS PIE 수식상의 왼쪽 괄호는 무조건 스택에 저장 (우선순위를 가장 높게) 스택 탑이 왼쪽 괄호일 때 수식상의 연산자는 무조건 스택에 저장 (우선순위를 가장 낮게) 오른쪽 괄호는? 해당 왼쪽 괄호가 스택에서 꺼내질 때까지 스택상의 연산자를 출력 대응되는 왼쪽 괄호는 단순히 제거 연산자 PIS PIE *, / 2 +, - 1 ( 3

후위 표기식 변환 예제: 다음 식을 스택을 이용하여 후위식으로 변환하라. (a+b) *c a*(b+c)/d

후위식 변환 알고리즘 postfix(exp) while (exp의 끝이 아니면) do token <- get_token(exp); //토큰은 연산자, 피연산자 또는 괄호 case token = operand: print(token); token = operator: token = “)”: endcase repeat while (스택이 빌 때까지) do print(pop(stack)); end postfix

문제 다음 식을 후위 표기법으로 변환하라: 변환 과정시 스택의 상태를 보여라. 여러분은 스택에 항목의 삽입, 삭제시 그 상태를 보여야 한다. 5 * [(10+2) % 2] 위에서 변환된 후위 표기법을 평가하라. 평가 과정시 스택의 상태를 보여라. 여러분은 스택에 항목의 삽입, 삭제시 그 상태를 보여야 한다.

예제: 후위 표기식 변환 예제: 다음 식을 스택을 이용하여 후위식으로 변환하라. 5 * (10+2) % 2 a / b – c + d * e – a * c 2 * { 3 + [(1+2)*4] – 5}

스택 응용: 미로 탐색 하나의 입구에서 출발하여 여러 갈림길을 거쳐서 하나 밖에 없는 출구까지의 경로를 찾는 문제 입구 미로를 어떻게 표현할 것인가? 어떻게 경로를 찾아가게 할 것인가? 입구

미로 탐색 해결 방법(시행착오방법) 하나의 경로를 선택하여 시도하고, 안되면 다른 경로를 시도 => 가능한 다른 경로를 어딘가에 저장하는 것이 필요 => 경로가 막혔을 경우에 어떤 다른 경로를 취할 것인가? 한번 시도된 경로는 다시 시도하면 안되게 => 시도된 경로를 표시해 둔다

미로 탐색 해결 스택을 이용 현재 가능한 다른 모든 경로들을 스택에 저장해 두고, 길이 막힌 경우에 스택으로부터 다른 경로를 가져와서 재시도

미로 표현 2차원 배열로 표현 벽은 1로 표현 1: 막혀있는 벽 0: 이동 가능 위치 M*n의 미로 => (m+2)*(n+2)의 미로로 표현 입구: maze[1,1], 출구: maze[m, n] 1 m x 입구 출구

미로 탐색 알고리즘 이동 가능 위치 이미 방문된 위치 표기 현재위치 X: (i, j) 북: (i-1, j), 동(I, j+1), 남(i+1, j), 서(i, j-1) 이미 방문된 위치 표기 Maze[]의 해당 위치의 원소 값을 ‘.’으로 변경 또는 별도의 mark[] 배열을 사용 N E W X S

미로 탐색 알고리즘 Maze_path() stack_type s; int maze[m+2, n+2]; // 스택 s, 미로 maze 초기화 // 입구를 현재 위치로 설정 while (현재 위치가 출구가 아니면) do 현재 위치를 방문한 것으로 표시; if (현재 위치의 위, 아래, 왼쪽, 오른쪽 위치가 아직 방문되지 않았고, 이동 가능하면) then 그러한 위치들을 모두 스택에 저장 endif if (스택이 비어 있으면) then print(“실패”); else 스택에서 한 위치를 꺼내어 현재 위치로 만든다 repeat print(“성공”); end maze_path