c - 如何找到正确的括号顺序？

Question

我必须弄清楚括号顺序是否正确。这是我的问题。 Neat bracket

&这是我的解决方案代码。

#include <stdio.h>
int main()
{
    char s[100];
    int c=0,count1=0,count2=0,count3=0;
    scanf("%[^\n]",s);
    while(s[c] !='\0')
        {
        if(s[c] == '(')
        {
            ++count1;
        }
        if(s[c] == ')')
        {
            ++count2;
        }
        if(s[c] == '"')
        {
            ++count3;
        }
        ++c;
    }
    if(count1==count2 && count3%2 ==0)
    {
        printf("Yes");
    }
    else
    {
        printf("No");
    }
    return 0;
}

但它返回测试用例的错误答案。 &我也知道该算法不正确，因为它无法给出此测试用例的正确答案

)))""(((

那么我该如何改进我的算法？？？

Answer 1

用std::stack来做。想法是

1. 如果堆栈为空，则将 s[i] 压入堆栈。
2. 将当前字符(又名 s[i])与 stack.top() 进行比较，如果匹配则弹出堆栈。
3. 未找到匹配项时，将当前字符(又名 s[i])压入堆栈。

假设输入为:“()(())”。现在，

A. i = 0。最初堆栈是空的。将“(”压入堆栈。堆栈 - “(”。

B. i = 1。堆栈不为空。比较“)”又名 1与堆栈顶部 - “(”。它确实匹配。现在，弹出堆栈。堆栈 - “”。

C. i = 2。现在堆栈是空的。将“(”压入堆栈。堆栈 - “(”。

D. i = 3。堆栈不为空。将“(”又名 s[3] 与堆栈顶部 - “)”进行比较。它不匹配。现在，将“(”压入堆栈。堆栈 - “((”

E. i = 4。堆栈不为空。将 ")"又名 s[4] 与堆栈顶部 - "("进行比较。它确实匹配。现在，弹出堆栈。堆栈 - "("

F. i = 5。堆栈不为空。将“)”(又名 s[5])与堆栈顶部 - “(”进行比较。它确实匹配。现在，弹出堆栈。堆栈 - “”

现在，堆栈是空的，我们可以说字符串是整齐的 - 正如问题中提到的。如果我们在堆栈中留下任何不匹配的括号，那就意味着字符串不整齐。

     //Assuming s is the char array containing parenthesis sequence.
     int i = 0;
     std::stack<char> st;
     while(s[i] != '\0') //Better choice would be to use std::string
     {
        if(st.empty() )
        {
             st.push( s[i++] ); 
             continue;
        } 
        if( st.top() == '(' && s[i] == ')' )
            { st.pop(); i++ }
        else
            st.push(s[i++]);   

      }
       if(st.empty() )  
          printf("Yes");
       else 
          printf("No");