7 스택.

Presentation on theme: "7 스택."— Presentation transcript:

1 7 스택

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

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

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

5 스택 후입선출 구조의 예2 : 슈퍼맨의 옷 갈아입기 수퍼맨이 옷을 벗는 순서 슈퍼맨이 옷을 입는 순서
후입선출 구조의 예2 : 슈퍼맨의 옷 갈아입기 수퍼맨이 옷을 벗는 순서 ① 장화 → ②망토 → ③빨간팬츠 → ④파란옷 슈퍼맨이 옷을 입는 순서 ④ 파란옷 → ③빨간팬츠 → ②망토 → ①장화

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

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

8 스택의 추상 자료형 스택에 대한 추상 자료형 ADT Stack 데이터 : 0개 이상의 원소를 가진 유한 순서 리스트
스택에 대한 추상 자료형 ADT Stack 데이터 : 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 [ADT 7-1]

9 추상자료형 스택 스택의 push 알고리즘 top ← top+1;
스택 S에서 top이 마지막 자료를 가리키고 있으므로 그 위에 자료를 삽입하려면 먼저 top의 위치를 하나 증가 만약 이때 top의 위치가 스택의 크기(stack_SIZE)보다 크다면 오버플로우(overflow)상태가 되므로 삽입 연산을 수행하지 못하고 연산 종료 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]

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

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

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

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

14 스택의 구현 순차 자료구조 방식을 이용하여 구현한 스택 프로그램 19 20 public boolean isEmpty(){
return (top == -1); 22 } 23 24 public boolean isFull(){ return (top == this.stackSize-1); 26 } 27 28 public void push(char item){ if(isFull()){ System.out.println("Inserting fail! Array Stack is full!!"); } else{ itemArray[++top] = item; System.out.println("Inserted Item : " + item); } 36 } [예제 7-1]

15 스택의 구현 순차 자료구조 방식을 이용하여 구현한 스택 프로그램 37 38 public char pop(){
if(isEmpty()) { System.out.println("Deleting fail! Array Stack is empty!!"); return 0; } else{ return itemArray[top--]; } 46 } 47 48 public void delete(){ if(isEmpty()){ System.out.println("Deleting fail! Array Stack is empty!!"); } else { top--; } 55 } [예제 7-1]

16 스택의 구현 순차 자료구조 방식을 이용하여 구현한 스택 프로그램 56 57 public char peek(){
if(isEmpty()){ System.out.println("Peeking fail! Array Stack is empty!!"); return 0; } else return itemArray[top]; 64 } 65 66 public void printStack(){ if(isEmpty()) System.out.printf("Array Stack is empty!! %n %n"); else{ System.out.printf("Array Stack>> "); for(int i=0; i<=top; i++) System.out.printf("%c ", itemArray[i]); System.out.println(); System.out.println(); } [예제 7-1]

17 스택의 구현 순차 자료구조 방식을 이용하여 구현한 스택 프로그램 75 } 76 } 77 78 class Ex7_1{
75 } 76 } 77 78 class Ex7_1{ 79 public static void main(String args[]){ int stackSize = 5; char deletedItem; ArrayStack S = new ArrayStack(stackSize); 83 S.push('A'); S.printStack( ); 86 S.push('B'); S.printStack(); 89 S.push('C'); S.printStack( ); [예제 7-1]

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

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

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

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

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

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

24 스택의 구현 연결 자료구조 방식을 이용하여 구현한 스택 프로그램 18 return (top == null); 19 } 20
19 } 20 21 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 } 28 29 public char pop(){ 30 if(isEmpty()) { System.out.println("Deleting fail! Linked Stack is empty!!"); return 0; 33 } 34 else{ char item = top.data; top = top.link; [예제 7-2]

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

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

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

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

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

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

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

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

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

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

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

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

37 스택의 응용 수식의 괄호 검사 알고리즘 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 = "]" : if (open_pair ≠ "[") then return false; symbol = "}" : if (open_pair ≠ "{") then return false; [알고리즘 7-3]

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

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

40 스택의 응용 >> 계속

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

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

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

44 스택의 응용 연결 자료구조 방식을 이용하여 구현한 스택 프로그램 020
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 } 028 029 public char pop(){ 030 if(isEmpty()) { System.out.println("Deleting fail! Linked Stack is empty!!"); return 0; 033 } 034 else{ char item = top.data; top = top.link; return item; 038 } [예제 7-3]

45 스택의 응용 연결 자료구조 방식을 이용하여 구현한 스택 프로그램 039 } 040
039 } 040 041 public void delete(){ 042 if(isEmpty()){ System.out.println("Deleting fail! Linked Stack is empty!!"); 044 045 } 046 else { top = top.link; 048 } 049 } 050 051 public char peek(){ 052 if(isEmpty()){ System.out.println("Peeking fail! Linked Stack is empty!!"); return 0; 055 } 056 else return top.data; [예제 7-3]

46 스택의 응용 연결 자료구조 방식을 이용하여 구현한 스택 프로그램 058 } 059
058 } 059 060 public void printStack(){ 061 if(isEmpty()) System.out.printf("Linked Stack is empty!! %n %n"); 063 else{ StackNode temp = top; System.out.println("Linked Stack>> "); while(temp != null){ System.out.printf("\t %c \n", temp.data); temp = temp.link; } System.out.println(); 071 } 072 } 073 } 074 [예제 7-3]

47 스택의 응용 연결 자료구조 방식을 이용하여 구현한 스택 프로그램 075 class OptExp{
076 private String exp; 077 private int expSize; 078 private char testCh, openPair; 079 080 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++){ testCh = this.exp.charAt(i); switch(testCh){ case '(' : case '{' : case '[' : S.push(testCh); break; case ')' : case '}' : case ']' : if(S.isEmpty()) return false; else{ openPair = S.pop(); if((openPair == '(' && testCh != ')') || (openPair == '{' && testCh != '}') || (openPair == '[' && testCh != ']')) return false; else break; } } } 105 if (S.isEmpty()) return true; else return false; 107 } 108 109 public char[] toPostfix(String infix){ char testCh; exp = infix; int expSize = 10; int j=0; char postfix[] = new char[expSize]; LinkedStack S = new LinkedStack(); 116 for(int i=0; i<=expSize; i++){ testCh = this.exp.charAt(i); switch(testCh){ case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9': postfix[j++] = testCh; break; 131 case '+' : case '-' : case '*' : case '/' : S.push(testCh); break; 137 case ')' : postfix[j++] =S.pop(); break; 139 140 default: } 143 } 144 postfix[j] = S.pop(); 145 return postfix; 146 } 147 } 148 149 class Ex7_3{ 150 public static void main(String args[]){ 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)) System.out.println("괄호 맞음!"); 158 else System.out.println("괄호 틀림!!!"); 160 System.out.printf("\n후위표기식 : "); 162 postfix = opt.toPostfix(exp); 163 System.out.println(postfix); 164 } 165 } [예제 7-3]

48 스택의 응용 연결 자료구조 방식을 이용하여 구현한 스택 프로그램 075 class OptExp{
076 private String exp; 077 private int expSize; 078 private char testCh, openPair; 079 080 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++){ testCh = this.exp.charAt(i); switch(testCh){ case '(' : case '{' : case '[' : S.push(testCh); break; case ')' : case '}' : [예제 7-3]

49 스택의 응용 연결 자료구조 방식을 이용하여 구현한 스택 프로그램 093 case ']' :
if(S.isEmpty()) return false; else{ openPair = S.pop(); if((openPair == '(' && testCh != ')') || (openPair == '{' && testCh != '}') || (openPair == '[' && testCh != ']')) return false; else break; } } } 105 if (S.isEmpty()) return true; else return false; 107 } 108 109 public char[] toPostfix(String infix){ char testCh; [예제 7-3]

50 스택의 응용 연결 자료구조 방식을 이용하여 구현한 스택 프로그램 111 exp = infix;
int expSize = 10; int j=0; char postfix[] = new char[expSize]; LinkedStack S = new LinkedStack(); 116 for(int i=0; i<=expSize; i++){ testCh = this.exp.charAt(i); switch(testCh){ case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': [예제 7-3]

51 스택의 응용 연결 자료구조 방식을 이용하여 구현한 스택 프로그램 129 case '9':
postfix[j++] = testCh; break; 131 case '+' : case '-' : case '*' : case '/' : S.push(testCh); break; 137 case ')' : postfix[j++] =S.pop(); break; 139 140 default: } 143 } 144 postfix[j] = S.pop(); 145 return postfix; 146 } 147 } [예제 7-3]

52 스택의 응용 연결 자료구조 방식을 이용하여 구현한 스택 프로그램 148 149 class Ex7_3{
150 public static void main(String args[]){ 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)) System.out.println("괄호 맞음!"); 158 else System.out.println("괄호 틀림!!!"); 160 System.out.printf("\n후위표기식 : "); 162 postfix = opt.toPostfix(exp); 163 System.out.println(postfix); 164 } 165 } [예제 7-3]

53 스택의 응용 실행결과

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

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

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

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

58 스택의 응용 예) ((A*B)-(C/D))

59 스택의 응용 예) ((A*B)-(C/D))

60 스택의 응용 예) ((A*B)-(C/D))

61 스택의 응용 예) ((A*B)-(C/D))

62 스택의 응용 중위 표기법에 대한 후위 표기법 변환 알고리즘 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 else : } end infix_to_postfix( ) [알고리즘 7-4]

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

64 스택의 응용 후위 표기 수식의 연산 알고리즘 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]

65 스택의 응용 예) AB*CD/-

66 스택의 응용 예) AB*CD/-

67 스택의 응용 예) AB*CD/-

68 스택의 응용 후위 표기 수식의 연산 프로그램 01 class StackNode{ 02 int data;
03 StackNode link; 04 } 05 06 class LinkedStack{ 07 private StackNode top; 08 09 public boolean isEmpty(){ 10 return (top == null); 11 } 12 13 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]

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

70 스택의 응용 후위 표기 수식의 연산 프로그램 39 int opr1, opr2, value; 40 char testCh;
41 for(int i=0; i<7; i++){ testCh = exp.charAt(i); if(testCh != '+' && testCh != '-' && testCh !='*' && testCh != '/'){ value = testCh - '0';45 S.push(value); } else{ opr2 = S.pop(); opr1 = S.pop(); switch(testCh){ case '+' : S.push(opr1 + opr2); break; case '-' : S.push(opr1 - opr2); break; case '*' : S.push(opr1 * opr2); break; case '/' : S.push(opr1 / opr2); break; } } 57 } 58 return S.pop(); [예제 7-4]

71 스택의 응용 후위 표기 수식의 연산 프로그램 59 } 60 } 61 62 class Ex7_4{
59 } 60 } 61 62 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]