parentheses - 检查括号是否平衡 - 没有堆栈

Question

假设我有一个非常大的文件，我想检查括号是否平衡。我不能使用堆栈，对吗？因为它会导致堆栈溢出。我可以使用什么方法？

Answer 1

一个简单的计数器。由于您所做的只是计算括号：

balance = 0
for c in open('filename.ext', 'r'):
    if c == '(':
        balance += 1
    elif c == ')':
        balance -= 1
if balance == 0:
    print 'parenthesis are (possibly) balanced'
else:
    print 'parenthesis are not balanced'

为什么（可能）？好吧，使用这种方法，您会发现这是平衡的：

a(bc))d(ef

这可能不是你所期望的......所以......你可能想在这里早点休息：

balance = 0
for c in open('filename.ext', 'r'):
    if c == '(':
        balance += 1
    elif c == ')':
        balance -= 1
        if balance < 0:
            break # -1 -> we found a closing paren without an opening one...
if balance == 0:
    print 'parenthesis are balanced'
else:
    print 'parenthesis are not balanced'

Answer 2

人们通常提到的“堆栈溢出”与在您的情况下使用堆栈（作为数据结构）无关。

使用堆栈主要是一种合理的方式。如果你的目的只是为了找出

1. 所有左括号都有相应的右括号，
2. 不存在右括号出现在左括号之前的情况；

然后你可以简单地通过一个简单的循环加上一个计数器来做到这一点：

在伪代码中：

function boolean isBalanced(input) {
    int counter = 0;
    while (! input.hasMoreChar) {
      char c = input.readNextChar();
      if (c == OPEN_PARENTHESIS) {
        counter++;
      } else if (c == CLOSE_PARENTHESIS) {
        if (counter == 0) {
          return false;    // Close parenthesis appear without a corresponding open
        } else {
          counter--;
        }
      }
    }

    return counter == 0;
}

Answer 3

解决这个问题的一种简单方法是保留一个变量，如果变量不为零，则递增(和递减，在这种情况下，它是无效的。)这将适用于多个括号的一种类型的括号，您可能必须对另一个变量实施独立检查。

 bool checkParenthesis(string s) {
        int buffer = 0;
        for(int i=0; i<s.length(); i++){
            if(s[i]=='('){
                buffer++;
            }
            else if(s[i]==')'){
                if(buffer>0) buffer--;
                else return false;
            }
        }
        return !buffer;
    }

Answer 4

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int func(char *s);
int main()
{
    char *input1=malloc(sizeof(char)*100);
    printf("Balanced Parenthesis Program:\n");
    printf("Enter data for Balanced Parenthesis\n");
    scanf("%[^\n]%*c",input1);
    func(input1);
}

int func(char *input1)
{
    int count1=0,count2=0,count3=0,flag=0;
        for(int i=0;input1[i]!='\0';i++)
        {
            if(input1[i]=='('||input1[i]==')')
                count1++;
            else if(input1[i]=='{'||input1[i]=='}')
            count2++;
        else if(input1[i]=='['||input1[i]==']')
            count3++;
        else
            continue;
    }
    for(int i=0;input1[i]!='\0';i++)
    {
        if(input1[i]=='(')
        {
            if(input1[i+1]=='}'||input1[i+1]==']')
                return 0;
        }
        else if(input1[i]=='{')
        {
            if(input1[i+1]==']'||input1[i+1]==')')
                return 0;
        }
        else if(input1[i]=='[')
        {
            if(input1[i+1]==')'||input1[i+1]=='}')
            return 0;
        }
        else
            continue;
    }
    if((count1+count2+count3)%2==0)
         printf("Balanced");
    else
        printf("Unbalanced");
}

Answer 5

var a="{([])}";
var len=a.length();
var count=0;
for(var i=0;i<len;i++)
{
if(a[i]=='{'||a[i]=='['||a[i]=='(')
{ 
count++;
}
else
{
count--;
}
}
if(count==0)
{ 
console.log("balanced");
}
else
{
console.log("unbalanced");
}