最长的子字符串

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; 
} 

很抱歉的代码，而不是解释。如果您需要解释任何部分，我会澄清。现在，您可以检查一些输入和纸和笔。