No9012 괄호 (Stack)

스택을 이용해서 푸는 문제다. 자바 Array를 사용하여 Stack을 직접 구현해보았다.

class ArrayStack {
	
	int top;
	int stackSize = 50;
	int[] stackArr;
	
	public ArrayStack() {
		top = -1;
		stackArr = new int[this.stackSize];
	}
	
	public boolean isEmpty() {
		if(top == -1) return true;
		return false;
	}
	
	public boolean isFull() {
		if(top == stackSize-1) return true;
		return false;
	}
	
	public void push(int value) {
	
		if(isFull()) {
			return;
		}
		stackArr[++top] = value;
	}
	
	public int pop() {
		if(isEmpty()) {
			return -1;
		}
		return stackArr[top--];
	}
	
	public int peek() {
		if(isEmpty()) return -1;
		return stackArr[top];
	}
	
	
}

스택을 사용하여 괄호가 vps 형식이 맞는지 확인하는 작업이 필요하다. 괄호가 vps 형식에 맞는지 안맞는지를 확인하기 위해서는 두가지 조건을 확인해야 한다.

 

첫째는 괄호가 열린 것이 없는데 닫히는 괄호가 나왔는지의 여부

둘째는 문장이 끝났을 때 안닫힌 괄호가 있는지의 여부

 

이를 stack 자료구조로 구현하기 위해 괄호가 열릴 때 숫자 1을 push하고 괄호가 닫힐 때 숫자 1을 pop한다.

 

vps 형식에 맞지 않는 조건을 stack 구조에서 생각해보면

첫번째 조건은

pop을 실행했을 때 isEmpty()가 true 인 상황이 한번이라도 발생한 경우를 말한다.

두번째 조건은

문장이 완료된 후 stack에 여전히 1이 남아 있는 경우, 즉 isEmpty가 false인 경우를 말한다.

public class No9012 {

	public static String verify(String str) {
		
		ArrayStack stack = new ArrayStack();
		
		for (int i = 0; i < str.length(); i++) {
			if(str.charAt(i) =='(') {
				stack.push(1);
			} else if(str.charAt(i) == ')') {
				if(stack.pop() == -1) return "NO";
			}
		}
		if(!stack.isEmpty()) return "NO";
		return "YES";
		
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int N = Integer.parseInt(br.readLine());

		while(N-->0) {
			sb.append(verify(br.readLine()) + "\n");
		}
		
		System.out.println(sb.toString());
		
	}

}

class ArrayStack {
	
	int top;
	int stackSize = 50;
	int[] stackArr;
	
	public ArrayStack() {
		top = -1;
		stackArr = new int[this.stackSize];
	}
	
	public boolean isEmpty() {
		if(top == -1) return true;
		return false;
	}
	
	public boolean isFull() {
		if(top == stackSize-1) return true;
		return false;
	}
	
	public void push(int value) {
	
		if(isFull()) {
			return;
		}
		stackArr[++top] = value;
	}
	
	public int pop() {
		if(isEmpty()) {
			return -1;
		}
		return stackArr[top--];
	}
	
	public int peek() {
		if(isEmpty()) return -1;
		return stackArr[top];
	}
	
	
}