Microsoft PowerPoint - ch07_스택 [호환 모드]

Transcription

1 스택 (Stack) 자바로배우는쉬운자료구조

2 이장에서다룰내용 1 스택 2 스택의추상자료형 3 스택의구현 4 스택의응용 2

3 스택 (1) 스택 (stack) 접시를쌓듯이자료를차곡차곡쌓아올린형태의자료구조 스택에저장된원소는 top 으로정한곳에서만접근가능 top 의위치에서만원소를삽입하므로먼저삽입한원소는밑에쌓이고, 나중에삽입한원소는위에쌓인다. 마지막에삽입 (Last-In) 한원소는맨위에쌓여있다가가장먼저삭제 (First-Out) 된다. 후입선출구조 (LIFO, Last-In-First-Out) 3

4 스택 (2) 후입선출구조의예1 : 연탄아궁이 연탄을하나씩쌓으면서아궁이에넣으므로마지막에넣은 3번연탄이가장위에쌓여있다. 연탄을아궁이에서꺼낼때에는위에서부터하나씩꺼내야하므로마지막에넣은 3번연탄을가장먼저꺼내게된다. 4

5 스택 (3) 후입선출구조의예2 : 슈퍼맨의옷갈아입기 수퍼맨이옷을벗는순서 1 장화 2망토 3빨간팬츠 4파란옷 슈퍼맨이옷을입는순서 4 파란옷 3빨간팬츠 2망토 1장화 5

6 스택 (4) 스택의연산 스택에서의삽입연산 : push 스택에서의삭제연산 : pop 6

7 스택 (5) 스택에서의원소삽입 / 삭제과정 공백스택에원소 A, B, C를순서대로삽입하고한번삭제하는동안의스택변화 7

8 추상자료형스택 (1) 스택에대한추상자료형 ADT Stack [ADT 7-1] 데이터 : 0개이상의원소를가진유한순서리스트연산 : S Stack; item Element; createstack() ::= create an empty Stack; // 공백스택을생성하는연산 isempty(s) ::= if (S is empty) then return true else return false; // 스택 S가공백인지아닌지를확인하는연산 push(s, item) ::=insert item onto the top of S; // 스택 S의 top에 item( 원소 ) 을삽입하는연산 pop(s) ::= if (isempty(s)) then return error else { delete and return the top item of S }; // 스택 S의 top에있는item( 원소 ) 을스택에서삭제하고반환하는연산 delete(s) ::= if (isempty(s)) then return error else delete the top item;a // 스택 S의 top에있는item( 원소 ) 을삭제하는연산 peek(s) ::= if (isempty(s)) then return error else return (the top item of the S); // 스택 S의 top에있는item( 원소 ) 을반환하는연산 End Stack 8

9 추상자료형스택 (2) 스택의 push 알고리즘 1 top top+1; 스택 S에서 top이마지막자료를가리키고있으므로그위에자료를삽입하려면먼저 top의위치를하나증가 만약이때 top 의위치가스택의크기 (stack_size) 보다크다면오버플로우 (overflow) 상태가되므로삽입연산을수행하지못하고연산종료 2 S(top) x; 오버플로우상태가아니라면스택의 top이가리키는위치에 x 삽입 push(s, x) top top+1; // ❶ if (top > stack_size) then overflow; else S(top) x; // ❷ end push( ) [ 알고리즘 7-1] 9

10 추상자료형스택 (3) 스택의 pop 알고리즘 1 return S(top); 스택이공백스택이아니라면 top 이가리키는원소를먼저반환 2 top top-1; 스택의 top 원소를반환하였으므로 top 의위치는그아래의원소로변경하기위해 top 의위치를하나감소 pop(s) if (top = 0) then error; else { return S(top); // ❶ top top-1; // ❷ } end pop() [ 알고리즘 7-2] 10

11 스택의구현 (1) 순차자료구조를이용한스택의구현 순차자료구조인 1 차원배열을이용하여구현 스택의크기 : 배열의크기 스택에저장된원소의순서 : 배열원소의인덱스 인덱스 0 번 : 스택의첫번째원소 인덱스 n-1 번 : 스택의 n 번째원소 변수 top : 스택에저장된마지막원소에대한인덱스저장 공백상태 : top = -1 ( 초기값 ) 포화상태 : top = n-1 11

12 스택의구현 (2) 크기가 5 인 1 차원배열의스택에서 [ 그림 7-6] 의연산수행과정 12

13 스택의구현 (3) 순차자료구조방식을이용하여구현한스택프로그램 01 interface Stack{ 02 boolean isempty( ); 03 void push(char item); 04 char pop( ); 05 void delete( ); 06 char peek( ); 07 } class ArrayStack implements Stack{ 10 private int top; 11 private int stacksize; 12 private char itemarray[]; public ArrayStack(int stacksize){ 15 top = -1; 16 this.stacksize = stacksize; 17 itemarray = new char[this.stacksize]; 18 } [ 예제 7-1] 13

14 스택의구현 (4) 순차자료구조방식을이용하여구현한스택프로그램 19 [ 예제 7-1] 20 public boolean isempty(){ 21 return (top == -1); 22 } public boolean isfull(){ 25 return (top == this.stacksize-1); 26 } public void push(char item){ 29 if(isfull()){ 30 System.out.println("Inserting fail! Array Stack is full!!"); 31 } 32 else{ 33 itemarray[++top] = item; 34 System.out.println("Inserted Item : " + item); 35 } 36 } 14

15 스택의구현 (5) 순차자료구조방식을이용하여구현한스택프로그램 37 [ 예제 7-1] 38 public char pop(){ 39 if(isempty()) { 40 System.out.println("Deleting fail! Array Stack is empty!!"); 41 return 0; 42 } 43 else{ 44 return itemarray[top--]; 45 } 46 } public void delete(){ 49 if(isempty()){ 50 System.out.println("Deleting fail! Array Stack is empty!!"); 51 } 52 else { 53 top--; 54 } 55 } 15

16 스택의구현 (6) 순차자료구조방식을이용하여구현한스택프로그램 56 [ 예제 7-1] 57 public char peek(){ 58 if(isempty()){ 59 System.out.println("Peeking fail! Array Stack is empty!!"); 60 return 0; 61 } 62 else 63 return itemarray[top]; 64 } public void printstack(){ 67 if(isempty()) 68 System.out.printf("Array Stack is empty!! %n %n"); 69 else{ 70 System.out.printf("Array Stack>> "); 71 for(int i=0; i<=top; i++) 72 System.out.printf("%c ", itemarray[i]); 73 System.out.println(); System.out.println(); 74 } 16

17 스택의구현 (7) 순차자료구조방식을이용하여구현한스택프로그램 75 } 76 } class Ex7_1{ 79 public static void main(string args[]){ 80 int stacksize = 5; 81 char deleteditem; 82 ArrayStack S = new ArrayStack(stackSize); S.push('A'); 85 S.printStack( ); S.push('B'); 88 S.printStack(); S.push('C'); 91 S.printStack( ); [ 예제 7-1] 17

18 스택의구현 (8) 순차자료구조방식을이용하여구현한스택프로그램 92 [ 예제 7-1] 93 deleteditem = S.pop(); 94 if(deleteditem!= 0) 95 System.out.println("deleted Item : " + deleteditem); 96 S.printStack(); 97 } 98 } 18

19 스택의구현 (9) 순차자료구조로구현한스택의장점 순차자료구조인 1차원배열을사용하여쉽게구현 순차자료구조로구현한스택의단점 물리적으로크기가고정된배열을사용하므로스택의크기변경어려움 순차자료구조의단점을그대로가지고있다. 19

20 스택의구현 (10) 연결자료구조를이용한스택의구현 단순연결리스트를이용하여구현 스택의원소 : 단순연결리스트의노드 스택원소의순서 : 노드의링크포인터로연결 push : 리스트의마지막에노드삽입 pop : 리스트의마지막노드삭제 변수 top : 단순연결리스트의마지막노드를가리키는포인터변수 초기상태 : top = null 20

21 스택의구현 (11) 단순연결리스트의스택에서 [ 그림 6-6] 의연산수행과정 1 공백스택생성 :create(stack); 2 원소 A 삽입 :push(stack, A); 3 원소 B 삽입 :push(stack, B); 21

22 스택의구현 (12) 4 원소 C 삽입 :push(stack, C); 5 원소삭제 :pop(stack); 22

23 스택의구현 (13) 연결자료구조방식을이용하여구현한스택프로그램 01 interface Stack{ 02 boolean isempty(); 03 void push(char item); 04 char pop(); 05 void delete(); 06 char peek(); 07 } class StackNode{ 10 char data; 11 StackNode link; 12 } class LinkedStack implements Stack{ 15 private StackNode top; public boolean isempty(){ [ 예제 7-2] 23

24 스택의구현 (14) 연결자료구조방식을이용하여구현한스택프로그램 18 return (top == null); [ 예제 7-2] 19 } public void push(char item){ 22 StackNode newnode = new StackNode(); 23 newnode.data = item; 24 newnode.link = top; 25 top = newnode; 26 System.out.println("Inserted Item : " + item); 27 } public char pop(){ 30 if(isempty()) { 31 System.out.println("Deleting fail! Linked Stack is empty!!"); 32 return 0; 33 } 34 else{ 35 char item = top.data; 36 top = top.link; 24

25 스택의구현 (15) 연결자료구조방식을이용하여구현한스택프로그램 37 return item; [ 예제 7-2] 38 } 39 } public void delete(){ 42 if(isempty()){ 43 System.out.println("Deleting fail! Linked Stack is empty!!"); } 46 else { 47 top = top.link; 48 } 49 } public char peek(){ 51 if(isempty()){ 52 System.out.println("Peeking fail! Linked Stack is empty!!"); 25

26 스택의구현 (16) 연결자료구조방식을이용하여구현한스택프로그램 53 return 0; 54 } 55 else 56 return top.data; 57 } public void printstack(){ 60 if(isempty()) 61 System.out.printf("Linked Stack is empty!! %n %n"); 62 else{ 63 StackNode temp = top; 64 System.out.println("Linked Stack>> "); 65 while(temp!= null){ 66 System.out.printf("\t %c \n", temp.data); 67 temp = temp.link; 68 } 69 System.out.println(); 70 } [ 예제 7-2] 26

27 스택의구현 (17) 연결자료구조방식을이용하여구현한스택프로그램 71 } 72 } class Ex7_2{ 75 public static void main(string args[]){ 76 char deleteditem; 77 LinkedStack LS = new LinkedStack(); LS.push('A'); 80 LS.printStack(); LS.push('B'); 83 LS.printStack(); LS.push('C'); 86 LS.printStack(); 87 [ 예제 7-2] 27

28 스택의구현 (18) 연결자료구조방식을이용하여구현한스택프로그램 88 deleteditem = LS.pop(); [ 예제 7-2] 89 if(deleteditem!= 0) 90 System.out.println("deleted Item : " + deleteditem); 91 LS.printStack(); 92 } 93 } 28

29 스택의응용 (1) 역순문자열만들기 역순문자열만들기 스택의후입선출 (LIFO) 성질을이용 1 문자열을순서대로스택에 push 하기 29

30 스택의응용 (1) 역순문자열만들기 2 스택을 pop 하여문자열로저장하기 30

31 스택의응용 (2) 시스템스택 시스템스택 프로그램에서의호출과복귀에따른수행순서를관리 가장마지막에호출된함수가가장먼저실행을완료하고복귀하는후입선출구조이므로, 후입선출구조의스택을이용하여수행순서관리 함수호출이발생하면호출한함수수행에필요한지역변수, 매개변수및수행후복귀할주소등의정보를스택프레임 (stack frame) 에저장하여시스템스택에삽입 함수의실행이끝나면시스템스택의 top 원소 ( 스택프레임 ) 를삭제 (pop) 하면서프레임에저장되어있던복귀주소를확인하고복귀 함수호출과복귀에따라이과정을반복하여전체프로그램수행이종료되면시스템스택은공백스택이된다. 31

32 스택의응용 (2) 시스템스택 함수호출과복귀에따른전체프로그램의수행순서 32

33 스택의응용 (2) 시스템스택 1 프로그램이실행을시작하여 main() 함수가실행되면서 main() 함수에관련된정보를스택프레임에저장하여시스템스택에삽입 2 main() 함수실행중에 F_1() 함수호출을만나면함수호출과복귀에필요한정보를스택프레임에저장하여시스템스택에삽입하고, 호출된함수인 F_1() 함수로이동 이때스택프레임에는호출된함수의수행이끝나고 main() 함수로복귀할주소 a 를저장 33

34 스택의응용 (2) 시스템스택 3 호출된함수 F_1() 함수를실행 4 F_1() 함수실행중에 F_2() 함수호출을만나면다시함수호출과복귀에필요한정보를스택프레임에저장하여시스템스택에삽입. 호출된함수인 F_2() 함수를실행 스택프레임에는 F_1() 함수로복귀할주소 b 를저장 5 호출된함수 F_2() 함수를실행완료 6 시스템스택의 top 에있는스택프레임을 pop 하여정보를확인하고, F_1() 함수의 b 주소로복귀 34

35 스택의응용 (2) 시스템스택 7 복귀된함수 F_1() 함수의 b 주소이후부분을실행 8 시스템스택의 top 에있는스택프레임을 pop 하여정보를확인하고 main() 함수의 a 주소로복귀 9 복귀된 main() 함수의 a 주소이후부분에대한실행이완료되면시스템스택의 top 에있는스택프레임을 pop 하는데, 시스템스택이공백이되었으므로전체프로그램실행종료 35

36 스택의응용 (3) 수식의괄호검사 수식의괄호검사 수식에포함되어있는괄호는가장마지막에열린괄호를가장먼저닫아주어야하는후입선출구조로구성되어있으므로, 후입선출구조의스택을이용하여괄호를검사한다. 수식을왼쪽에서오른쪽으로하나씩읽으면서괄호검사 왼쪽괄호를만나면스택에 push 오른쪽괄호를만나면스택을 pop하여마지막에저장한괄호와같은종류인지를확인 같은종류의괄호가아닌경우괄호의짝이잘못사용된수식! 수식에대한검사가모두끝났을때스택은공백스택 수식이끝났어도스택이공백이되지않으면괄호의개수가틀린수식! 36

37 스택의응용 (3) 수식의괄호검사 수식의괄호검사알고리즘 testpair( ) exp Expression; Stack null; while (true) do { symbol getsymbol(exp); case { symbol = "(" or "[" or "{" : push(stack, symbol); symbol = ")" : open_pair pop(stack); if (open_pair "(") then return false; symbol = "]" : open_pair pop(stack); if (open_pair "[") then return false; symbol = "}" : open_pair pop(stack); if (open_pair "{") then return false; [ 알고리즘 7-3] 37

38 스택의응용 (3) 수식의괄호검사 수식의괄호검사알고리즘 symbol = null : if (isempty(stack)) then return true; else return false; else : } } end testpair( ) [ 알고리즘 7-3] 38

39 스택의응용 (3) 수식의괄호검사 수식의괄호검사예 검사할수식 : {(A+B)-3}*5+[{cos(x+y)+7}-1]*4 >> 계속 39

40 스택의응용 (3) 수식의괄호검사 >> 계속 40

41 스택의응용 (3) 수식의괄호검사 41

42 스택의응용 (3) 수식의괄호검사 42

43 스택의응용 (3) 수식의괄호검사 연결자료구조방식을이용하여구현한스택프로그램 001 interface Stack{ 002 boolean isempty( ); 003 void push(char item); 004 char pop( ); 005 void delete( ); 006 char peek( ); 007 } class StackNode{ 010 char data; 011 StackNode link; 012 } class LinkedStack implements Stack{ 015 private StackNode top; public boolean isempty(){ 018 return (top == null); 019 } [ 예제 7-3] 43

44 스택의응용 (3) 수식의괄호검사 연결자료구조방식을이용하여구현한스택프로그램 020 [ 예제 7-3] 021 public void push(char item){ 022 StackNode newnode = new StackNode(); 023 newnode.data = item; 024 newnode.link = top; 025 top = newnode; 026 // System.out.println("Inserted Item : " + item); 027 } public char pop(){ 030 if(isempty()) { 031 System.out.println("Deleting fail! Linked Stack is empty!!"); 032 return 0; 033 } 034 else{ 035 char item = top.data; 036 top = top.link; 037 return item; 038 } 44

45 스택의응용 (3) 수식의괄호검사 연결자료구조방식을이용하여구현한스택프로그램 039 } [ 예제 7-3] public void delete(){ 042 if(isempty()){ 043 System.out.println("Deleting fail! Linked Stack is empty!!"); } 046 else { 047 top = top.link; 048 } 049 } public char peek(){ 052 if(isempty()){ 053 System.out.println("Peeking fail! Linked Stack is empty!!"); 054 return 0; 055 } 056 else 057 return top.data; 45

46 스택의응용 (3) 수식의괄호검사 연결자료구조방식을이용하여구현한스택프로그램 058 } [ 예제 7-3] public void printstack(){ 061 if(isempty()) 062 System.out.printf("Linked Stack is empty!! %n %n"); 063 else{ 064 StackNode temp = top; 065 System.out.println("Linked Stack>> "); 066 while(temp!= null){ 067 System.out.printf("\t %c \n", temp.data); 068 temp = temp.link; 069 } 070 System.out.println(); 071 } 072 } 073 }

47 스택의응용 (3) 수식의괄호검사 연결자료구조방식을이용하여구현한스택프로그램 075 class OptExp{ 076 private String exp; 077 private int expsize; 078 private char testch, openpair; public boolean testpair(string exp){ 081 this.exp = exp; 082 LinkedStack S = new LinkedStack(); 083 expsize = this.exp.length(); 084 for(int i=0; i<expsize; i++){ 085 testch = this.exp.charat(i); 086 switch(testch){ 087 case '(' : 088 case '{' : 089 case '[' : 090 S.push(testCh); break; 091 case ')' : 092 case '}' : [ 예제 7-3] 47

48 스택의응용 (3) 수식의괄호검사 연결자료구조방식을이용하여구현한스택프로그램 093 case ']' : 094 if(s.isempty()) return false; 095 else{ 096 openpair = S.pop(); 097 if((openpair == '(' && testch!= ')') 098 (openpair == '{' && testch!= '}') 099 (openpair == '[' && testch!= ']')) 100 return false; 101 else break; 102 } 103 } 104 } 105 if (S.isEmpty()) return true; 106 else return false; 107 } public char[] topostfix(string infix){ 110 char testch; [ 예제 7-3] 48

49 스택의응용 (3) 수식의괄호검사 연결자료구조방식을이용하여구현한스택프로그램 111 exp = infix; 112 int expsize = 10; 113 int j=0; 114 char postfix[] = new char[expsize]; 115 LinkedStack S = new LinkedStack(); for(int i=0; i<=expsize; i++){ 118 testch = this.exp.charat(i); 119 switch(testch){ 120 case '0': 121 case '1': 122 case '2': 123 case '3': 124 case '4': 125 case '5': 126 case '6': 127 case '7': 128 case '8': [ 예제 7-3] 49

50 스택의응용 (3) 수식의괄호검사 연결자료구조방식을이용하여구현한스택프로그램 129 case '9': 130 postfix[j++] = testch; break; case '+' : 133 case '-' : 134 case '*' : 135 case '/' : 136 S.push(testCh); break; case ')' : postfix[j++] =S.pop(); break; default: 142 } 143 } 144 postfix[j] = S.pop(); 145 return postfix; 146 } 147 } [ 예제 7-3] 50

51 스택의응용 (3) 수식의괄호검사 연결자료구조방식을이용하여구현한스택프로그램 class Ex7_3{ 150 public static void main(string args[]){ 151 OptExp opt = new OptExp(); 152 String exp = "(3*5)-(6/2)"; 153 char postfix[]; 154 int value; 155 System.out.println(exp); 156 if(opt.testpair(exp)) 157 System.out.println(" 괄호맞음!"); 158 else 159 System.out.println(" 괄호틀림!!!"); System.out.printf("\n후위표기식 : "); 162 postfix = opt.topostfix(exp); 163 System.out.println(postfix); 164 } 165 } [ 예제 7-3] 51

52 스택의응용 (3) 수식의괄호검사 실행결과 52

53 스택의응용 (4) 수식변환 수식의표기법 전위표기법 (prefix notation) 연산자를앞에표기하고그뒤에피연산자를표기하는방법 예 ) +AB 중위표기법 (infix notation) 연산자를피연산자의가운데표기하는방법 예 ) A+B 후위표기법 (postfix notation) 연산자를피연산자뒤에표기하는방법 예 ) AB+ 53

54 스택의응용 (4) 수식변환 중위표기식의전위표기식변환방법 1 수식의각연산자에대해서우선순위에따라괄호를사용하여다시표현한다. 2 각연산자를그에대응하는왼쪽괄호의앞으로이동시킨다. 3 괄호를제거한다. 예 ) A*B-C/D 1단계 : ( (A*B) - (C/D) ) 2 단계 : -(*(A B) /(C D)) 3 단계 : -*AB/CD 54

55 스택의응용 (4) 수식변환 중위표기식의후위표기식변환방법 1 수식의각연산자에대해서우선순위에따라괄호를사용하여다시표현한다. 2 각연산자를그에대응하는오른쪽괄호의뒤로이동시킨다. 3 괄호를제거한다. 예 ) A*B-C/D 1단계 : ( (A*B) - (C/D) ) 2 단계 : ( (A B)* (C D)/ )- 3 단계 : AB*CD/- 55

56 스택의응용 (4) 수식변환 스택을사용하여입력된중위표기식을후위표기식으로변환 변환방법 1 왼쪽괄호를만나면무시하고다음문자를읽는다. 2 피연산자를만나면출력한다. 3연산자를만나면스택에 push한다. 4 오른쪽괄호를만나면스택을 pop하여출력한다. 5 수식이끝나면, 스택이공백이될때까지 pop하여출력한다. 56

57 스택의응용 (4) 수식변환 예 ) ((A*B)-(C/D)) 57

58 스택의응용 (4) 수식변환 예 ) ((A*B)-(C/D)) 58

59 스택의응용 (4) 수식변환 예 ) ((A*B)-(C/D)) 59

60 스택의응용 (4) 수식변환 예 ) ((A*B)-(C/D)) 60

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

62 예 ) (a+b)*c ( a + b ) * c ( 62

63 예 ) (a+b)*c ( a + b ) * c a ( 63

64 예 ) (a+b)*c ( a + b ) * c + a ( 64

65 예 ) (a+b)*c ( a + b ) * c + a b ( 65

66 예 ) (a+b)*c ( a + b ) * c a b + 66

67 예 ) (a+b)*c ( a + b ) * c a b + * 67

68 예 ) (a+b)*c ( a + b ) * c a b + c * 68

69 예 ) (a+b)*c ( a + b ) * c a b + c * 69

70 스택의응용 (4) 수식변환 중위표기법에대한후위표기법변환알고리즘 infix_to_postfix(exp) while(true) do { symbol getsymbol(exp); case { symbol = operand : // 피연산자처리 print(symbol); symbol = operator : // 연산자처리 push(stack, symbol); symbol = ")" : // 오른쪽괄호처리 print(pop(stack)); symbol = null : // 중위수식의끝 while(top > -1) do print(pop(stack)); else : } } end infix_to_postfix( ) [ 알고리즘 7-4] 70

71 스택의응용 (5) 후위표기식연산 스택을사용하여후위표기식을연산 연산방법 1 피연산자를만나면스택에 push 한다. 2연산자를만나면필요한만큼의피연산자를스택에서 pop하여연산하고, 연산결과를다시스택에 push 한다. 3 수식이끝나면, 마지막으로스택을 pop하여출력한다. 수식이끝나고스택에마지막으로남아있는원소는전체수식의연산결과값이된다. 71

72 스택의응용 (5) 후위표기식연산 8 2 / / / 피연산자 -> 삽입피연산자 -> 삽입연산자 -> 8/2=4 삽입 8 2 / / / 피연산자 -> 삽입연산자 -> 4-1=1 삽입종료 -> 전체연산결과 =1 72

73 스택의응용 (5) 후위표기식연산 후위표기수식의연산알고리즘 evalpostfix(exp) while (true) do { symbol getsymbol(exp); case { symbol = operand : // 피연산자처리 push(stack, symbol); symbol = operator : // 연산자처리 opr2 pop(stack); opr1 pop(stack); result opr1 op(symbol) opr2; // 스택에서꺼낸피연산자들을연산자로연산 push(stack, result); symbol = null : // 후위수식의끝 print(pop(stack)); } } end evalpostfix() [ 알고리즘 7-5] 73

74 스택의응용 (5) 후위표기식연산 예 ) AB*CD/- 74

75 스택의응용 (5) 후위표기식연산 예 ) AB*CD/- 75

76 스택의응용 (5) 후위표기식연산 예 ) AB*CD/- 76

77 스택의응용 (5) 후위표기식연산 후위표기수식의연산프로그램 01 class StackNode{ 02 int data; 03 StackNode link; 04 } class LinkedStack{ 07 private StackNode top; public boolean isempty(){ 10 return (top == null); 11 } public void push(int item){ 14 StackNode newnode = new StackNode(); 15 newnode.data = item; 16 newnode.link = top; 17 top = newnode; 18 } 19 [ 예제 7-4] 77

78 스택의응용 (5) 후위표기식연산 후위표기수식의연산프로그램 20 public int pop(){ [ 예제 7-4] 21 if(isempty()) { 22 System.out.println("Deleting fail! Linked Stack is empty!!"); 23 return 0; 24 } 25 else{ 26 int item = top.data; 27 top = top.link; 28 return item; 29 } 30 } 31 } class OptExp2{ 34 private String exp; public int evalpostfix(string postfix){ 37 LinkedStack S = new LinkedStack(); 38 exp = postfix; 78

79 스택의응용 (5) 후위표기식연산 후위표기수식의연산프로그램 39 int opr1, opr2, value; [ 예제 7-4] 40 char testch; 41 for(int i=0; i<7; i++){ 42 testch = exp.charat(i); 43 if(testch!= '+' && testch!= '-' && testch!='*' && testch!= '/'){ 44 value = testch - '0';45 S.push(value); 46 } 47 else{ 48 opr2 = S.pop(); 49 opr1 = S.pop(); 50 switch(testch){ 51 case '+' : S.push(opr1 + opr2); break; 52 case '-' : S.push(opr1 - opr2); break; 53 case '*' : S.push(opr1 * opr2); break; 54 case '/' : S.push(opr1 / opr2); break; 55 } 56 } 57 } 58 return S.pop(); 79

80 스택의응용 (5) 후위표기식연산 후위표기수식의연산프로그램 59 } 60 } class Ex7_4{ 63 public static void main(string args[]){ 64 OptExp2 opt = new OptExp2(); 65 int result; 66 String exp = "35*62/-"; 67 System.out.printf("\n후위표기식 : %s", exp); 68 result = opt.evalpostfix(exp); 69 System.out.printf("\n 연산결과 = %d \n", result); 70 } 71 } [ 예제 7-4] 80

81 스택의응용 (6) 미로탐색 체계적인방법필요 현재의위치에서가능한방향을스택에저장해놓았다가막다른길을만나면스택에서다음탐색위치를꺼낸다 입구 출구 m x

82 스택의응용 (6) 미로탐색 82

83 스택의응용 (6) 미로탐색 미로탐색알고리즘 스택 s과출구의위치 x, 현재생쥐의위치를초기화 while( 현재의위치가출구가아니면 ) do 현재위치를방문한것으로표기 if( 현재위치의위, 아래, 왼쪽, 오른쪽위치가아직방문되지않았고갈수있으면 ) then 그위치들을스택에 push if( is_empty(s) ) then 실패 else 스택에서하나의위치를꺼내어현재위치로만든다 ; 성공 ; 83

84 자바로배우는쉬운자료구조 7 장끝