如何找到正确的括号序列?

huangapple go评论82阅读模式
英文:

How to find the correct brackets sequence?

问题

I've to figure it out that the bracket sequence is correct. Here is my problem.
Neat bracket

& Here is my solution code.

#include <stdio.h>
int main()
{
    char s[100];
    int c=0,count1=0,count2=0,count3=0;
    scanf("%[^\n]",s);
    while(s[c] !='
#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;
}
'
)
{ 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; }

But it returns incorrect answer for a test case. & I also know that the algorithm is not proper 'cause it fails to give the correct answer for this test case

)))""(((

So how can I improve my algorithm???

英文:

I've to figure it out that the bracket sequence is correct. Here is my problem.
Neat bracket

& Here is my solution code.

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

But it returns incorrect answer for a test case. & I also know that the algorithm is not proper 'cause it fails to give the correct answer for this test case

> )))""(((

So how can I improve my algorithm???

答案1

得分: 1

使用std::stack来完成。思路是:

  1. 如果栈为空,将s[i]推入栈中。
  2. 比较当前字符(即s[i])与stack.top(),如果匹配,则弹出栈。
  3. 当找不到匹配时,将当前字符(即s[i])推入栈。

假设输入是:"()(())"。现在进行逐步演示:

A. i = 0。最初栈为空。将"("推入栈。栈 - "("。

B. i = 1。栈不为空。比较"s1"即")"与栈顶的"("。它匹配。现在弹出栈。栈 - ""。

C. i = 2。现在栈为空。将"("推入栈。栈 - "("。

D. i = 3。栈不为空。比较"s[3]"即"("与栈顶的")"。它不匹配。现在将"("推入栈。栈 - "(("。

E. i = 4。栈不为空。比较"s[4]"即")"与栈顶的"("。它匹配。现在弹出栈。栈 - "("。

F. i = 5。栈不为空。比较"s[5]"即")"与栈顶的"("。它匹配。现在弹出栈。栈 - ""。

现在,栈为空,我们可以说字符串是整洁的 - 如问题中所述。如果栈中仍然存在未匹配的括号,那将意味着字符串不整洁。

// 假设s是包含括号序列的字符数组。
int i = 0;
std::stack<char> st;
while (s[i] != '
// 假设s是包含括号序列的字符数组。
int i = 0;
std::stack<char> st;
while (s[i] != '\0') // 更好的选择是使用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");
'
) // 更好的选择是使用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");
英文:

Do it with std::stack. Idea is to

  1. If stack is empty, push s[i] to stack.
  2. Compare current character aka s[i] with stack.top() and pop stack if does match.
  3. Push current character aka s[i] onto stack when no match is found.

Assume input is : "()(())". Now,

A. i = 0. Initially stack is empty. Push "(" on stack. Stack - "(".

B. i = 1. Stack is not empty. Compare ")" aka s1 with stack's top - "(". It does match. Now, pop stack. Stack - "".

C. i = 2. Now stack is empty. Push "(" on stack. Stack - "(".

D. i = 3. Stack is not empty. Compare "(" aka s[3] with stack's top - ")". It does not match. Now, push "(" to stack. Stack - "(("

E. i = 4. Stack is not empty. Compare ")" aka s[4] with stack's top - "(". It does match. Now, pop stack. Stack - "("

F. i = 5. Stack is not empty. Compare ")" aka s[5] with stack's top - "(". It does match. Now, pop stack. Stack - ""

Now, Stack is empty, We can say string is neat - as mentioned in question. Had we left with any unmatched parenthesis in stack, that'd mean string is not neat.

     //Assuming s is the char array containing parenthesis sequence.
     int i = 0;
     std::stack&lt;char&gt; st;
     while(s[i] != &#39;
     //Assuming s is the char array containing parenthesis sequence.
int i = 0;
std::stack&lt;char&gt; st;
while(s[i] != &#39;\0&#39;) //Better choice would be to use std::string
{
if(st.empty() )
{
st.push( s[i++] ); 
continue;
} 
if( st.top() == &#39;(&#39; &amp;&amp; s[i] == &#39;)&#39; )
{ st.pop(); i++ }
else
st.push(s[i++]);   
}
if(st.empty() )  
printf(&quot;Yes&quot;);
else 
printf(&quot;No&quot;);
&#39;) //Better choice would be to use std::string { if(st.empty() ) { st.push( s[i++] ); continue; } if( st.top() == &#39;(&#39; &amp;&amp; s[i] == &#39;)&#39; ) { st.pop(); i++ } else st.push(s[i++]); } if(st.empty() ) printf(&quot;Yes&quot;); else printf(&quot;No&quot;);

答案2

得分: 0

好的。我已完成。这是我的解决方案。感谢 "max66"。
所以在这个问题中,你需要识别一件非常重要的事情,就是 ")" 没有与其闭合标签一起使用。这就是我已经做到的。
这是我的解决方案。

#include <stdio.h>
int main()
{
    int c=0,count1=0,count2=0;
    char s[1000];
    scanf("%[^\n]",s);
    while(s[c] != '
好的。我已完成。这是我的解决方案。感谢 "max66"。
所以在这个问题中,你需要识别一件非常重要的事情,就是 ")" 没有与其闭合标签一起使用。这就是我已经做到的。
这是我的解决方案。

#include <stdio.h>
int main()
{
    int c=0,count1=0,count2=0;
    char s[1000];
    scanf("%[^\n]",s);
    while(s[c] != '\0')
    {
        if(s[c] == '"')
        {
            ++count2;
        }
        if(s[c] == ')')
        {
            --count1;
        }
        if (count1 != -1)
        {
            if(s[c]== '(')
            {
               ++count1;
            }
        }

        ++c;
    }
    ///printf("%d\n",count1);
    ///printf("%d\n",count2);
    if(count1 == 0 && count2%2 == 0)
    {
        printf("一切正常!\n");
    }
    else
    {
        printf("有些不对劲!\n");
    }
    return 0;
}
')
{ if(s[c] == '"') { ++count2; } if(s[c] == ')') { --count1; } if (count1 != -1) { if(s[c]== '(') { ++count1; } } ++c; } ///printf("%d\n",count1); ///printf("%d\n",count2); if(count1 == 0 && count2%2 == 0) { printf("一切正常!\n"); } else { printf("有些不对劲!\n"); } return 0; }
英文:

Ok. I've done. Here is my solve. Thanks to " max66 ".
So in this problem , you've to identify one most important thing that ")" isn't used without its closing tags. That's I've done.
Here is my solution.

#include &lt;stdio.h&gt;
int main()
{
    int c=0,count1=0,count2=0;
    char s[1000];
    scanf(&quot;%[^\n]&quot;,s);
    while(s[c] != &#39;
#include &lt;stdio.h&gt;
int main()
{
int c=0,count1=0,count2=0;
char s[1000];
scanf(&quot;%[^\n]&quot;,s);
while(s[c] != &#39;\0&#39;)
{
if(s[c] == &#39;&quot;&#39;)
{
++count2;
}
if(s[c] == &#39;)&#39;)
{
--count1;
}
if (count1 != -1)
{
if(s[c]== &#39;(&#39;)
{
++count1;
}
}
++c;
}
///printf(&quot;%d\n&quot;,count1);
///printf(&quot;%d\n&quot;,count2);
if(count1 == 0 &amp;&amp; count2%2 == 0)
{
printf(&quot;Every thing is OK!\n&quot;);
}
else
{
printf(&quot;Something is fishy!\n&quot;);
}
return 0;
}
&#39;) { if(s[c] == &#39;&quot;&#39;) { ++count2; } if(s[c] == &#39;)&#39;) { --count1; } if (count1 != -1) { if(s[c]== &#39;(&#39;) { ++count1; } } ++c; } ///printf(&quot;%d\n&quot;,count1); ///printf(&quot;%d\n&quot;,count2); if(count1 == 0 &amp;&amp; count2%2 == 0) { printf(&quot;Every thing is OK!\n&quot;); } else { printf(&quot;Something is fishy!\n&quot;); } return 0; }

huangapple
  • 本文由 发表于 2020年1月7日 00:39:44
  • 转载请务必保留本文链接:https://go.coder-hub.com/59615805.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定