正しいparanthesisの最長部分文字列

Question

私は少し問題に遭遇しています。私が正しく閉じparanthesisの最長部分文字列を計算しなければならないとこれまでのところ、私はこれを行うことができた：

while (work_stack.size != 0){ 
    //I have a working stack in which I have stored the elements 
    //which in my case are brackets and while I have elements 
    //i pop the first element and see if it's a left or right 
    a1 = pop(&work_stack.data); 
    work_stack.size--; 

    if ('{' == ((Pair*)a1->info)->type || 
     '(' == ((Pair*)a1->info)->type || 
     '[' == ((Pair*)a1->info)->type) { 
     //if it's a left bracket, then I add it to the left stack 
     //which i'm going to use to compare with the right sided 
     //brackets i will encounter. 
      stanga++; //i'm incrementing the no of left brackets 
     if(ok == 0) //if there wasn't a match, then length is set to 0 
      length = 0; 
     if (ok == 1 && stanga > 1) 
      //if there was a match but then two brackets of left side 
      //are encountered, then length = 0 
      /* 
      Now I figured that here I am wrong. Given the input: 
      [][()()])())[][)] 
      The right value should be 8, but my code encounters 
      two left values and sets the length to 0. I need to 
      find a way to determine if the substring is worth keeping 
      */ 
      length = 0; 
     push(&left.data, a1); 
     left.size++; 
    } 
    if ('}' == ((Pair*)a1->info)->type || 
     ')' == ((Pair*)a1->info)->type || 
     ']' == ((Pair*)a1->info)->type){ 
     //if it's a right bracket and there are elements in the left 
     //then i pop the first element fro the left stack and compare 
     //it to my current bracket 
     if(left.size != 0){ 
      stanga = 0; 
      a2 = pop(&left.data); 
      left.size--; 

      //opposing is a function that returns 1 if 
      //i encounter something like () or [ ] or { } 
      //if the brackets are opposed, i increment the length 
      if (oposing(((Pair*)a2->info)->type, ((Pair*)a1->info)->type) == 1){ 
       length += 2; 
       ok = 1; 
      } 

      //otherwise, it seems that I have run into a stopping 
      //point, so I'm emptying the left stack because those 
      //paranthesis are not of use anymore and I'm saving 
      //the maximum length acquired by now 
      if (oposing(((Pair*)a2->info)->type, ((Pair*)a1->info)->type) == 0){ 
       ok = 0; 
       while(left.size > 0){ 
        a2 = pop(&left.data); 
        left.size--;  
       } 
       if(length > max){ 
        max = length; 
        length = 0; 
       } 
      } 
      //if i haven't encountered a stopping point, i just 
      //compare the length to my max and save it if it's bigger 
      if (length > max) 
       max = length; 
     } 
     //this line says that if the size of the left stack is 0 and 
     //i have encountered a right bracket, then I can't form a 
     //correct substring, so the length is 0 
     else length = 0; 
    } 
} 

はそれを注意するために：((Pair*)a1->info)->typeは私の文字です。 ありがとうございました！ その後編集： - 私はスタックとペアのための構造を追加している

typedef struct{ 
    int id; 
    char type; 
}Pair; 

typedef struct cel{ 
    void *info; 
    struct cel *urm; 
}Celula, *TLista, **ALista; 

typedef struct{ 
    TLista data; 
    int size; 
}stack; 

私のスタックは、リンクリストなどのデータ型を持つが、それはそれだけの操作が正しい（プッシュとポップされているような問題ではないはず）。

編集：コードにいくつかの新しい改良が追加されました。また、私が何をしているのかに関するコメントに新たな展開が追加されました。私はバグを特定しましたが、私はそのバグを解決するために失敗しています。

Answer 1

この問題は、スタックを使用して解決できます。ここに私のC++実装である、あなたは構文を理解し、私は今外だとして、コードではなく、説明のために

int longestValidParentheses(string s) { 
    stack <int> Stack; 
    int maxLen = 0; 
    int lastPos = -1; 
    for(int i = 0; i < s.length(); ++i) { 
     if(s[i] == '(') { 
      Stack.push(i); 
     } 
     else { 
      if(Stack.empty()) { 
       lastPos = i; 
      } 
      else { 
       Stack.pop(); 
       if(Stack.empty()) { 
        maxLen = max(maxLen, i - lastPos); 
       } else { 
        maxLen = max(maxLen, i - Stack.top()); 
       } 
      } 
     } 
    } 
    return maxLen; 
} 

申し訳C.

に翻訳するために何の難しさを感じていないことを願っています。私は、あなたが何らかの理由で説明が必要な場合は、明確化をします。今のところ、入力とペン＆ペーパで確認できます。