To check if parenthesis are balanced- Without stack

Question

Suppose I have a very huge file and I want to check if parenthesis are balanced. I can't use stack, right? Because it'd result in a stack overflow. What approach I can use?

Answer 1

A simple counter. Since all you're doing is counting parenthesis:

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'

Why the (possibly)? Well, with this method, you would find this balanced:

a(bc))d(ef

which is probably not what you expect... so... you probably want to break early here:

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

The "stack overflow" people normally mention has nothing to do with using stack (as a data structure) in your case.

Using stack is mostly a reasonable way. If your intention is just to find out

1. all opening parenthesis has corresponding closing one,
2. there is no case that a closing parenthesis happen before a open parenthesis;

then you can simply do it by a simple loop plus a counter:

in psuedo code:

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

One simple way to approach this problem is to keep a variable and increment on ( and decrement on ) if the variable is not zero, in that case, it's invalid. This will work for one type of bracket for multiple brackets you might have to implement an independent check with another variable.

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