最長的子字符串

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; 

我棧有數據類型作爲一個鏈表但應該那麼重要的操作是正確的（push和pop ）。

編輯：增加了對代碼的一些新的改進，以及關於我在做什麼的評論中的新外觀。我發現了這個錯誤，但是我沒有找到解決方案。

Answer 1

這個問題可以使用堆棧來解決。這裏是我的C++實現，希望你不會覺得難以理解的語法和它，因爲我是外地人，現在轉變成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; 
} 

很抱歉的代碼，而不是解釋。如果您需要解釋任何部分，我會澄清。現在，您可以檢查一些輸入和紙和筆。