Valid Parentheses

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

 

문장 안에 여는 괄호가 있을 때 ,그 뒤에 알맞는 닫는 괄호가 있는지 검사하는 알고리즘을 만드는 문제이다.

1. 여는 괄호와 닫는 괄호를 매치시켜야 되므로 HashMap 을 사용하여 미리 대,중,소 괄호를 저장하였다.

 

2. 문장의 첫 문자부터 시작하여 여는 괄호인 경우에는 스택에 저장하고, 닫는 괄호인 경우에는 스택 최상단의 값과 매칭하여 알맞는 괄호인지 확인하였다. (스택이 비어있거나, 괄호의 형태(대,중,소)가 맞지 않는 경우 false)

 

3. 스택이 비어있는지 확인하여 여는괄호만 남겨지는 상태인 경우 false를 반환한다. 

 

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class ValidParentheses {
  public boolean isValid1(String str) {
    Map<Character, Character> braketChain = new HashMap<>();
    braketChain.put('(',')');
    braketChain.put('[',']');
    braketChain.put('{','}');
    Stack<Character> openBraketStack = new Stack<>();

    for (int i = 0 ; i < str.length() ; i++) {
      Character ch = str.charAt(i);
      if(braketChain.containsKey(ch)) {
        openBraketStack.push(ch);
        continue;
      }
      if(braketChain.containsValue(ch)) {
        if (openBraketStack.isEmpty()
            || braketChain.get(openBraketStack.pop()) != ch){
          return false;
        }
      }
    }
    if (openBraketStack.isEmpty()) {
      return true;
    }
    return false;
  }
 }