스 택 과 HashMap 을 이용 하여 괄호 일치 문 제 를 처리 합 니 다.

질문:
'(', ')', '{', '}', '[', ']' 만 포함 하 는 문자열 을 지정 하여 문자열 이 올 바른 지 판단 합 니 다.
유효한 문자열 만족:
왼쪽 괄호 는 같은 유형의 오른쪽 괄호 로 닫 아야 합 니 다.왼쪽 괄호 는 반드시 정확 한 순서 로 닫 아야 한다.빈 문자열 은 유효한 문자열 로 여 겨 질 수 있 습 니 다.
알고리즘:
1. 스 택 2 를 초기 화하 고 표현 식 의 모든 기호 3 을 순서대로 처리 합 니 다. 오른쪽 괄호 를 만나면 스 택 꼭대기 요 소 를 검사 합 니 다. 스 택 꼭대기 요소 가 같은 유형의 왼쪽 괄호 라면 스 택 꼭대기 요 소 를 꺼 냅 니 다. 그렇지 않 으 면 표현 식 이 잘못 되 었 음 을 의미 합 니 다.4. 왼쪽 괄호 를 만나면 스 택 에 5. 모든 기호 처리 가 끝 난 후에 스 택 에 요소 가 있 으 면 표현 식 이 잘못 되 었 음 을 의미 합 니 다.
대응 하 는 코드: 1,

Stack stack = new Stack();

2、

for( int i = 0; i < s.length(); i++)  //(String s)           
	char c = s.charAt(i);

3、

if(this.mappings.containsKey(c))
｛
	if(stack.isEmpty() || stack.peek() != this.mappings.get(c)); //   ——  key  value  
		return false;
	else 
		stack.pop();
｝	

또 다른 효율 적 인 방법: 표현 식 이 유효 하 다 면 오른쪽 괄호 를 만 났 을 때 스 택 꼭대기 요 소 는 반드시 대응 하 는 왼쪽 괄호 여야 합 니 다.그렇지 않 으 면 표현 식 이 잘못 되 었 습 니 다.따라서 창고 꼭대기 요 소 는 취하 지 않 으 면 무효 입 니 다.따라서 스 택 꼭대기 요 소 를 먼저 꺼 낼 수 있 습 니 다. 꺼 낸 스 택 꼭대기 요소 가 오른쪽 괄호 와 일치 하지 않 으 면 false 로 돌아 가면 됩 니 다.

char topElement = stack.empty()?  '#' : stack.pop();
if (topElement != this.mappings.get(c))
	return false;

4、

else stack.push(c); 

5、

return stack.isEmpty

다른: 구조 함수 에서 HashMap 초기 화

  private HashMap mappings;

  // Initialize hash map with mappings. This simply makes the code easier to read.
  public Solution() {
    this.mappings = new HashMap();
    this.mappings.put(')', '(');
    this.mappings.put('}', '{');
    this.mappings.put(']', '[');
  }

메모:
Stack 의 API
boolean empty() E peek() E pop() E push(E object) int search(Object o)
HashMap API
void clear() Object clone() boolean containsKey(Object key) boolean containsValue(Object value) Set> entrySet() V get(Object key) boolean isEmpty() Set keySet() V put(K key, V value) void putAll(Map extends K, ? extends V> map) V remove(Object key) int size() Collection values()