스택 푸시 (X) 및 팝() 동작 간의 관계를 어떻게 찾을 수 있습니까?

Question

저는 데이터 구조에 관한 opendatatructures.org의 연습 문제의 첫 번째 질문에 어려움을 겪었습니다.

반다이 크의 단어 + 1과 -1의 순서의 접두사의 합이 결코 부정적인되는 속성의 순서입니다 : 내가 좋아하는 간다 질문. 예를 들어 +1, -1, + 1, -1은 Dyck 단어이지만 접두사 +1 - 1 - 1 <부터 +1, -1, -1, + 1은 Dyck 단어가 아닙니다. Dyck 단어와 Stack push (x) 및 pop() 연산 사이의 모든 관계.

조작 간의 관계를 어떻게 알 수 있습니까?

Answer 1

Dyck 단어가있는 단어가 스택인지 여부를 나타내는 한 가지 방법은 +1이 발생할 때마다 밀어 넣고 -1이 발생할 때마다 팝업하는 방법입니다. 빈 스택에서 튀어 나오려고하면 Dyck 단어가 아닙니다.

는 다음과 같은 psuedocode이 (문제는 분석에 대해 정말 아니기 때문에 단어가, 정수의 배열로 표현되어 있다고 가정)을 고려 :

는

boolean isDyck(int[] word) { 
    Object dummy = new Object(); // Just so you have something to push 
    Stack stack = new Stack(); 
    for (item : word) { 
     if (item > 0) { 
      stack.push(dummy); 
     } else { 
      if (stack.isEmpty()) { 
       return false; 
      } 
      stack.pop(); 
     } 
    } 
    return true; 
}