C语言 编写一个程序来检查给定的输入字符串是否有平衡括号
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/30446061/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Write a program to check given input string have balance brackets
提问by Sarthak Singhal
Given a string of parentheses, write a program to find whether its valid or not.
给定一串括号，编写一个程序来判断它是否有效。
Examples-
例子-
input : {{{}}}
output: Valid
input : }{}{}{}}
output: Invalid
I wrote the following code in C and tested that the output were coming correct.
我用 C 编写了以下代码并测试输出是否正确。
#include <stdio.h>
#include <stdlib.h>
int main()
{
char str[20];
int i=0;
printf("Enter String: ");
gets(str);
int count = 0;
while (str[i] != 'if (count == 0) {
printf("Valid\n");
} else {
printf("Invalid\n");
}
return 0;
')
{
if (str[i] == '}')
count--;
if (str[i] == '{')
count++;
if (count < 0)
{
printf("\nInvalid");
break;
}
i++;
}
if (count == 0)
printf("\nValid");
return 0;
}
This program doesn't work for the case where input is {{{}}, what condition(s) am I missing?
该程序不适用于 input 为 的情况，{{{}}我缺少什么条件？
回答by chux - Reinstate Monica
Code should state if the final result is not 0 as in the case of "{"
代码应该说明最终结果是否不为 0，如 "{"
if (count < 0) {
// printf("\nInvalid");
break;
}
Also simple break out of loop.
也是简单的跳出循环。
char str[20];
fgets(str, sizeof str, stdin);
gets()has been depreciated since C99 and eliminated from C(C11), use fgets().
gets()自 C99 起已折旧并从C(C11) 中剔除，使用fgets()。
int ch;
while ((ch = fgetc(stdin)) != '\n' && ch != EOF) {
if (str[i] == '}')
count--;
if (count < 0) {
break;
}
else if (str[i] == '{')
count++;
}
}
There is no need to read the entire string in. Code could use 1 charar a time.
无需读入整个字符串。代码一次可以使用 1 个charar。
#include <stdio.h>
int main (void) {
int debug = 0; // for debugging purposes.
int ch, level = 0; // character and current level.
// Output prompt, read characters while valid.
printf("Enter string: ");
while (((ch = getchar()) == '{') && (ch == '}')) {
// Select based on '{' or '}'.
if (ch == '{') {
// Open bracket, just add one.
++level;
if (debug) printf("DEBUG: {:%d\n",level);
} else {
// Close bracket, subtract one and check.
if (--level < 0) {
puts ("Level has gone below zero.");
return 1;
}
if (debug) printf("DEbug: }:%d ",level);
}
}
// If not endline/endfile, we have invalid character.
if ((ch != '\n') && (ch != EOF)) {
puts ("Invalid character in input.");
return 1;
}
// Level should be zero.
if (level != 0) {
puts ("Level still positive at end of line.");
return 1;
}
// All checks now passed okay.
puts ("Input was fine.");
return 0;
}
回答by paxdiablo
You don't really need to input the whole string at once since you're only every sequentially processing the characters. Hence you can avoid using unsafe methods like gets()and even safe-but-complicating methods like fgets().
您真的不需要一次输入整个字符串，因为您只是按顺序处理字符。因此，您可以避免使用不安全的方法gets()，例如fgets().
Instead, just use getchar()to read and process each individual character - that should greatly simplify what you need to do.
相反，只需用于getchar()读取和处理每个单独的字符 - 这应该会大大简化您需要做的事情。
As to the logic, you basically have it right. Maintain the bracket level, a value initially set to zero. Then read each character and action it as follows:
至于逻辑，你基本上是对的。保持括号级别，该值最初设置为零。然后读取每个字符并按如下方式操作：
- If it's
{, just add one to the level. - If it's
}, subtract one from the level, then check to ensure the level is non-negative. If not, then you've had too many closing brackets and you can exit. - If it's end of line or end of file, stop processing characters. Check to make sure the final level is zero. If not, you haven't closed off all the brackets so it's invalid. If the level is zero, everything is balanced.
- Any other character can be considered an error.
- 如果是
{，只需在级别上添加一个。 - 如果是
}，则从级别中减去 1，然后检查以确保级别为非负值。如果没有，那么你的右括号太多了，你可以退出。 - 如果是行尾或文件尾，则停止处理字符。检查以确保最终级别为零。如果没有，您还没有关闭所有括号，因此它无效。如果水平为零，则一切都是平衡的。
- 任何其他字符都可以视为错误。
See below for one example on how to implement this:
有关如何实现这一点的示例，请参见下文：
#include<iostream>
#include<string.h>
using namespace std;
{
string mathEx ;
cout<<"Please Enter math Expression contain ')' , '(' to
check balance \n"<<"MathExpression = ";
cin>>mathEx ;
int i =0 , count = 0 ;
while (mathEx [i] != 'while (str[i] != 'char str[6];
gets(str);
')
{
if (str[i] == '}')
{
count--;
if (count < 0)
{
printf("\nInvalid");
break;
}
}
else if (str[i] == '{')
count++;
i++;
}
'){
if(mathEx[i]=='('){
count++;
}
if(mathEx[i]==')'){
count--;
}
if(count<0){
break ;
}
i++;
}
if(count==0){
cout<<"True !";
}
else {
cout<<"Invalid !"<<endl;
}
return 0;
}
回答by Mei Misaki
I hope you find this useful and simple ^-^
我希望你觉得这有用且简单^-^
iharob
回答by elliott.col
Previous answers have covered avoiding buffer overflows and potential cases where it will not work - to improve performance I would modify the while loop to avoid checking conditions which we know will always be false. e.g. no point in checking if count is less than 0 unless we just decreased the count; no point in checking for an open bracket if the character was a close bracket:
以前的答案涵盖了避免缓冲区溢出和它不起作用的潜在情况 - 为了提高性能，我将修改 while 循环以避免检查我们知道始终为假的条件。例如，检查计数是否小于 0 没有意义，除非我们只是减少计数；如果字符是右括号，则检查左括号没有意义：
fgets(str, sizeof(str), stdin);
回答by Iharob Al Asimi
You should never use gets(), the gcccompiler even warns about it being dangerous because there is no way to prevent a buffer overflow, for example
你永远不应该使用gets()，gcc编译器甚至警告它是危险的，因为没有办法防止缓冲区溢出，例如
with the following input
使用以下输入
##代码##is a problem, because there is no room for the '\0'terminator or the '\n', instead
是一个问题，因为没有空间给'\0'终止符或'\n', 取而代之
would be safe with any input, although the input string would be trimmed to fit the buffer, but no buffer overflow will occur.
对任何输入都是安全的，尽管输入字符串会被修剪以适应缓冲区，但不会发生缓冲区溢出。
