CODEWITHSUNDEEP
parentheses
karate_kid
karate_kid

Reputation: 155

To check if parenthesis are balanced- Without stack

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?

Upvotes: 6

Views: 23848

Answers (5)

Anonymous
Anonymous

Reputation: 1

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

Upvotes: 0

Ritankar Paul
Ritankar Paul

Reputation: 75

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

Upvotes: 0

Mogish Elangovan
Mogish Elangovan

Reputation: 1

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

Upvotes: -3

Adrian Shum
Adrian Shum

Reputation: 40036

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

Upvotes: 5

Daren Thomas
Daren Thomas

Reputation: 70324

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'

Upvotes: 18

Related Questions