'Algorithm&DataStructures'에 해당되는 글 38건

스택을 이용한 괄호 체크(delimiter matching)

- 스택을 이용하여 특정한 식의 괄호가 맞는지 체크한다

1. Stack.class

class StackImp{ private int top; private int stackSize; private char[] stackArr; public StackImp(int size){ this.top = -1; this.stackSize = size; this.stackArr = new char[stackSize]; } public void push(char element)throws Exception{ this.stackArr[++top] = element; } public char pop()throws Exception{ return this.stackArr[top--]; } public boolean isStackEmpty(){ return (top == -1); } public boolean isStackFull(){ return(top == stackSize -1); } }

2. DelimiterMatching .class

1) isDelimiterMatching()

public boolean isDelimiterMatching(String element) throws Exception{ int size = element.length(); StackImp stack = new StackImp(size); boolean flag = true; for(int i = 0; i<size; i++){ char target = element.charAt(i); switch(target){ case '(': case '[': case '{': stack.push(target); break; case ')': case ']': case '}': //괄호가 틀린지 맞는지 체크 if(!stack.isStackEmpty()){ char bb = stack.pop(); if((bb == '(' && target != ')')|| (bb == '{' && target != '}') || (bb == '[' && target != ']')){ flag = false; } }else{ //오른쪽에 괄호가 더 있는지 체크한다 flag = false; } break; default: break; } } //왼쪽에 괄호가 많은지 체크한다 if(!stack.isStackEmpty()){ flag = false; } return flag; }  

2) main()

public static void main(String[]args) throws Exception{ boolean result; DelimiterMatching aa = new DelimiterMatching(); result = aa.isDelimiterMatching("((a+b))-[a+b]"); System.out.println(result); }  

입력된 문자 뒤집기(Reverse a word)

- 입력된 문자를 스택을 이용해 뒤집어서 출력한다

1. Stack class

1) 변수 정의

private int top; private int stackSize; private char[] stackArr; public Stack(int size){ this.top = -1; this.stackSize = size; this.stackArr = new char[stackSize]; }

2) push(), isStackFull()

public void push(char element)throws Exception{ if(this.isStackFull()){ throw new Exception("Stack is full"); } this.stackArr[++top] = element; } public boolean isStackFull(){ return(top == stackSize -1); }  

3) pop(), isStackEmpty()

public char pop()throws Exception{ if(this.isStackEmpty()){ throw new Exception("Stack is empty"); } return stackArr[top--]; } public boolean isStackEmpty(){ return (top == -1); }  

2. Reverse class

1) reverseWord()

public String reverseWord(String word) throws Exception{ StringBuilder sb = new StringBuilder(); int size = word.length(); Stack st = new Stack(size); for(int i = 0; i<size; i++){ st.push(word.charAt(i)); } while(!st.isStackEmpty()){ sb.append(st.pop()); } return sb.toString(); }  

- Stringbuilder 사용

2) main()

public static void main(String[]args) throws Exception{ ReverseAword aaa=new ReverseAword(); Scanner word = new Scanner(System.in); String a = word.next(); System.out.println(a+">>>>>"+aaa.reverseWord(a)); word.close(); }  

- Scanner를 이용하여 입력받는다

스택(Stack) - 제네릭스택(Stack Using Generic)

- 제네릭을 이용하여 String, int 등 다양하게 받을 수 있다

1. 구현

1) 초기화

public class StackUsingGeneric <T extends Object>{ private int stackSize; private int top; private T[] stackArr; public StackUsingGeneric(int size){ this.stackSize = size; this.top = -1; this.stackArr = (T[]) new Object[stackSize]; }

- T 로 선언하여 객체 형태의 따라 받을 수 있게 한다

2) push(), isStackFull(), increaseCapacity()

public void push(T element){ if(this.isStackFull()){ System.out.println("Stack is full"); this.increaseCapacity(); } System.out.println("adding:"+element); this.stackArr[++top] = element; } public boolean isStackFull(){ return (this.stackSize -1 == top); } public void increaseCapacity(){ T[] newArr = (T[]) new Object[stackSize * 2]; for(int i = 0; i<stackSize; i++){ newArr[i] = stackArr[i]; } this.stackArr = newArr; this.stackSize = this.stackSize *2; }  

3) pop(), isStackEmpty(), peek()

public T pop()throws Exception{ if(this.isStackEmpty()){ throw new Exception("Stack is empty"); } System.out.println("removing:"+stackArr[top]); return stackArr[top--]; } public T peek(){ System.out.println("peeking:"+this.stackArr[top]); return this.stackArr[top]; }  

4) main()

public static void main(String[]args){ StackUsingGeneric<Integer> a1 = new StackUsingGeneric(2); try{ a1.push(1); a1.push(2); a1.peek(); a1.push(3); a1.pop(); }catch(Exception e){ System.out.print(e.getMessage()); } StackUsingGeneric<String> a2 = new StackUsingGeneric(2); try{ a2.push("a"); a2.push("b"); a2.peek(); a2.push("c"); a2.pop(); }catch(Exception e){ System.out.print(e.getMessage()); } }  

- 객체를 String, Integer 두개로 생성

 스택(Stack) - 동적스택(dynamicStack)

- 스택 오버플로우(stack overflow)날 경우 스택 사이즈를 동적으로 늘린다

1. 구현

1) 변수 초기화

private int top; private int[] stackArray; private int stackSize; public DynamicStack(int size){ this.top = -1; this.stackSize = size; this.stackArray = new int[stackSize]; }

2) push() and isStackFull()

public void push(int element)throws Exception{ if(this.isStackFull()){ System.out.println("Stack is full, We increase a stack size"); this.increaseCapacity(); } System.out.println("adding:"+element); this.stackArray[++top] = element; } public boolean isStackFull(){ return (stackSize-1 == top); }  

3) increaseCapacity()

public void increaseCapacity(){ int[] newArray = new int[stackSize *2]; for(int i = 0; i<stackArray.length;i++){ newArray[i] = this.stackArray[i]; } this.stackArray = newArray; this.stackSize = this.stackSize *2; }  

- 새로운 배열을 만들어 기존의 값을 넣는다

- 기존 배열을 새로운 배열로 변경한다

4) pop() and isStackEmpty()

public int pop()throws Exception{ if(this.isStackEmpty()){ throw new Exception("Stack is empty"); } int entity = stackArray[top--]; System.out.println("poping:"+entity); return entity; } public boolean isStackEmpty(){ return ( top == -1); }  

5) peek()

public int peek(){ System.out.println("peek:"+stackArray[top]); return stackArray[top]; }  

6) main()

public static void main(String[]args){ DynamicStack s1 = new DynamicStack(3); try{ s1.push(1); s1.push(2); s1.push(3); s1.push(4); s1.push(5); s1.pop(); s1.peek(); s1.pop(); s1.push(6); s1.push(7); s1.push(8); s1.push(9); }catch(Exception e){ System.out.println(e.getMessage()); } }