General discussions: Matching Brackets Problem

Mandeep_Verma 2016-01-20 15:06:30

I thought about an algorithm to store all the bracket openings in a stack and to pop the stack by one if a closing bracket of same type occurs otherwise to infer that the bracket sequence is wrong.But it does not seem to work PLEASE help!
My code is in JAVA:
import java.io.*;
class brack
{
public static void brackets()throws IOException
{
BufferedReader ob=new BufferedReader(new InputStreamReader(System.in));
int n=Integer.parseInt(ob.readLine());
String x;
int top,det,j;
char a[];
for(int i=0;i<n;i++)
{det=1;
x=ob.readLine();
a=new char[x.length()];top=0;
for(j=0;j<x.length();j++)
{
if(x.charAt(j)=='('||x.charAt(j)=='['||x.charAt(j)=='{'||x.charAt(j)=='<')
{a[top]=x.charAt(j);
top++;
}
if(x.charAt(j)==')')
{
if(a[top]=='(')
top--;
else
{det=0;
break;}}
if(x.charAt(j)=='}')
{
if(a[top]=='{') top--;
else
{det=0;
break;}}
if(x.charAt(j)==']')
{
if(a[top]=='[')
top--;
else
{det=0;
break;}}
if(x.charAt(j)=='>')
{
if(a[top]=='<')
top--;
else
{det=0;
break;}}
if(top==(-1))
{
det=0;}}
System.out.print(det+" ");}
}
}

calvinbbcard 2016-01-21 16:51:31

import java.io.*;
class brack
{
    public static void brackets()throws IOException
    {
        BufferedReader ob=new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(ob.readLine());
        String x;
        int top,det,j;
        char a[];
        for(int i=0;i<n;i++)
        {
            det=1;
            x=ob.readLine();
            a=new char[x.length()];top=0;
            for(j=0;j<x.length();j++)
            {
                if(x.charAt(j)=='('||x.charAt(j)=='['||x.charAt(j)=='{'||x.charAt(j)=='<')
                {a[top]=x.charAt(j);
                    top++;
                }
                if(x.charAt(j)==')')
                {
                    if(a[top]=='(') top--;
                    else
                    {
                        det=0;
                    break;
                    }
                }
                if(x.charAt(j)=='}')
                {
                    if(a[top]=='{') top--;
                    else
                    {
                        det=0;
                        break;
                    }
                }
                if(x.charAt(j)==']')
                {
                    if(a[top]=='[') top--;
                    else
                    {
                        det=0;
                        break;
                    }
                }
                if(x.charAt(j)=='>')
                {
                    if(a[top]=='<') top--;
                    else
                    {
                        det=0;
                        break;
                    }
                }
                if(top==(-1))
                {
                    det=0;
                }
            }
            System.out.print(det+" ");}
    }
}

To format it correctly, you need 4 spaces before each line. I think I did it right, not sure.

Matthew Cole 2016-01-22 19:43:51

Given that I don't have your entry point main() function, I can't see exactly what's happening.

That said, I have pretty good reason to believe that your stack is not stacking as you think it should stack. So...

Try inserting a trace print of the contents of a[] after each iteration of the for(j=0;j<x.length();j++) loop. You'll see what I'm seeing with pencil and paper.
Check out java.util.stack... you might find it easier/more enlightening to use the existing library data structure than to try to implement your own using array arithmetic.
What should happen if I finish reading the line from stdin and I still have left-braces remaining on the stack?
What should happen if I have an empty stack and encounter a right-brace?

You're on the right path by using the stack data structure though!