valid string bracket URGENT

[desert564]

Correct Sequence of brackets is always of primary importance both for written programs and mathematical expressions. By correct sequence we mean that for every opening bracket there is a closing bracket. The problem is to write a program that takes a random sized (size max 15) input of brackets from user, as a string, and can validate the sequence for e.g.
{([]{()})} valid
{[]}(} invalid
[]{{{} invalid
(((}))) invalid
{{{}}}} invalid
guys pls help me out with this

[quuba]

implement stack URGENT

[monarchmk]

Let hope that someone will not rep me - again for dropping solution
Anyway it was pleasure doing this one :)

public class parenthesis {

	public static void main(String[] args)
	{
		//Next ones are several strings just for testing. Only one should be active in a time
		String s="{([]{()})}"; //should be true
		//String s="{[]}(}"; //Should be false
		//String s="[]{{{}"; //Should be false
		//String s="[]{{}{}}"; //Should be true
		//String s="(((})))"; //Should be false
		//String s="((({})))"; //Should be true
		//String s="{{{}}}}"; //should be false
		
		String [][] par=new String [s.length()][2]; //Make array with length of a string s and 2 spare position for parenthesis and used/unused state
		boolean valid=true; //Lets be positive from start...
		
		for (int i=0;i<s.length();i++) //First will fill array with parenthesis
		{
			par[i][0]=s.substring(i, i+1);
			par[i][1]="0"; //means not yet used
		}
		
		for (int i=0;i<s.length();i++)
		{
//Check [ parenthesis
			if (par[i][0].equalsIgnoreCase("]")) //Checking for [ ]
			{
				//means there is closed  parenthesis.. check previous if there is opened one of same type and not already used
				//also check if previous is opened one but from other type, this is also invalid
				for (int j=i-1;j>=0;j--)
				{
					if ((par[j][0].equalsIgnoreCase("[") || par[j][0].equals("{")|| par[j][0].equals("(")) && par[j][1].equals("0")) //Check if previous parenthesis is open one of any type and not used one
					{
						//OK, i have open parenthesis... now check type. Valid is only if opened one match with closed one...
						if (par[j][0].equals("[")) //If previous is open and is right type then 
						{
							//OK, i need this type...
							par[j][1]="1"; //MAke it used
							par[i][1]="1"; //Make closed parenthesis used
							//I make both used because on end of software there is a check for unused parenthesis.
							break; //bailout if you found a match
						}
						else
						{
							valid=false; //Match not found... job done, parenthesis are wrong...
						}
						
					}
				}
				
			}
//Check { } parenthesis
			if (par[i][0].equalsIgnoreCase("}")) //Checking for [ ]
			{
				for (int j=i-1;j>=0;j--)
				{
					if ((par[j][0].equalsIgnoreCase("[") || par[j][0].equals("{")|| par[j][0].equals("(")) && par[j][1].equals("0"))
					{
						if (par[j][0].equals("{"))
						{
							par[j][1]="1"; 
							par[i][1]="1";
							break;
						}
						else
						{
							valid=false;
						}
						
					}
				}
				
			}
//Check ( ) parenthesis
			if (par[i][0].equalsIgnoreCase(")")) //Checking for [ ]
			{
				for (int j=i-1;j>=0;j--)
				{
					if ((par[j][0].equalsIgnoreCase("[") || par[j][0].equals("{")|| par[j][0].equals("(")) && par[j][1].equals("0"))
					{
						if (par[j][0].equals("("))
						{
							par[j][1]="1"; 
							par[i][1]="1";
							break;
						}
						else
						{
							valid=false;
						}
						
					}
				}
				
			}


		}
		//Ok, we chekc every closed parenthesis... now we are checking for opened or closed orphans ( par[X][1]="0" - not used)
		for (int i=0;i<s.length();i++)
			if (par[i][1].equals("0")) valid=false; //If parenthesis is not used, too bad, not valid
	
		System.out.println(valid); //print status
	}
}

If this solve your problem mark post SOLVED, else i'll be glad to answer if there is a problem with solution

[jon.kiparsky]

Please cut it out. I don't know why rep would be important to you, but you'll lose some every time I see a post like this.
When someone posts a homework assignment and you do it for them, you are helping them cheat.
You are also cheating them of an opportunity to learn something that they will need to know if they are planning on working in software in the future. The only way to learn to write code is to write code, lots of it. If you do the homework, they're not going to write the code, at most they might read it over and get about ten percent of what's in it.

But don't take my word for it - here it is from the Queen Bee herself http://www.daniweb.com/forums/announcement8-2.html

If you want to be useful here, be a teacher, not an answer book.

[monarchmk]

OK, calm down... as you can see in other my post... all codes are restricted.. or breaked apart, this one however i try to break apart but i lost my self in explanation and thats why i had to put all of it here. And its not reps that is important, i'll have bunch of ++ in not time thats not a problem... but please learn to ask before you judge!

[Taywin]

Hmm... Your solution is really a brute force. :P If you do it as stack-liked as quuba said, it would be much easier and shorter. Also, you would go through the string only once, not twice - one for the whole string and the other for the array you created. Hmm... I don't know why you need equalsIgnoreCase() while these strings won't be 'case' anyway...

[desert564]

I have a simple, though perhaps erroneous idea, that I will submit

It's a destructive algorithm, which means that if you ever need the string it would not help (since you would need to copy it down).

Otherwise, the algorithm work with a simple index within the current string.

The idea is to remove pairs one after the others:

([{}()])
([()])
([])
()
empty -> OK
It is based on the simple fact that if we have matching pairs, then at least one is of the form () without any pair character in between.

Algorithm:

i := 0
Find a matching pair from i. If none is found, then the string is not valid. If one is found, let i be the index of the first character.
Remove [i:i+1] from the string
If i is at the end of the string, and the string is not empty, it's a failure.
If [i-1:i] is a matching pair, i := i-1 and back to 3.
Else, back to 1.
The algorithm is O(n) in complexity because:

each iteration of the loop removes 2 characters from the string
the step 2., which is linear, is naturally bound (i cannot grow indefinitely)
And it's O(1) in space because only the index is required.

Of course, if you can't afford to destroy the string, then you'll have to copy it, and that's O(n) in space so no real benefit there!

Unless, of course, I am deeply mistaken somewhere... and perhaps someone could use the original idea (there is a pair somewhere) to better effect.

[jon.kiparsky]

Not bad... but what do you do if there's something in the brackets?
(ie, what if there's a point to the program)

That's not so bad - you can remove from front until you have a paren of some sort, and then remove from back until you have a paren of some sort, and then compare - if they're a matched set, keep going, else return false.

But what do you do if you have complex nesting?

ie, what do you do with

(define sum (lambda (l)
( cond
  ( (null? l)) 0)
  ( (null? (cdr l)) (car l))
  ( (list? (cdr l)) (+ (car l)(sum (cdr l))))
  ( else (+ (car l) (cdr l)))
)))

If you don't speak lisp, don't worry about it - this just takes a list of numbers and (if I haven't screwed it up) returns the sum. If you do speak lisp, please don't pick on my lisp, I just pulled this out of my head, and I haven't had any coffee yet!

But start with the modified algorithm:

we match the first and second parens with the last and penultimate. But then we have a problem. It doesn't immediately fail, but we match the third paren incorrectly with the last-2 paren. And then we hit the problem: we have a correctly balanced close paren matched with a close paren, and we (incorrectly) return false.
(It may be that I've slipped up and there's an imbalance in there, but we haven't found one yet - the algorithm shouldn't fail based on what we've looked at so far)

No, the first answer is still the best - a stack is your way to go. Advance a pointer down the String, following three rules:
1) put left brackets in the stack
2) ignore non-bracket characters
3) if you find a right bracket, pop the stack and compare. If they're not matched, return false

If you get to the end and the stack is empty, return true. So in the example above, you're pushing (, (, (, then pop and compare, push 3 and pop 3, and so forth.

(the compare is superfluous in this example)

Notice that this also makes it easy to track the depth of nesting. If you want to know how deep your implicit tree is, or how branchy it is, you can keep track of that as you go.

[desert564]

function isValid(string) {
    lastOpen = -1;  // Not null, as this catches the case where the first character
                    // is a closing brace.

    for(i=0; i<string.length; i++) {
         char = string.charAt(i);

         // Increment count on opening brace, decrement on close
         // and keep track of the last opening brace
         if(openingBrace) {
             parenCount[braceType] ++;  //Where braceType is an enum of reg, curly, square
             lastOpen = braceType;
         } else {
             // If the last opening brace does not match the next closing => fail
             if(lastOpen != null && lastOpen != braceType) { 
                 return false; 
             }
             lastOpen = null;
             parenCount[braceType] --;  //Where type is an enum of reg, curly, square
         }

    }

    // If parens are not balanced in number => fail
    for(j=0; j<parenCount.length; j++) {
        if(parenCount[j] != 0) {
            return false;
        }
    }

    return true;
}

well! i failed with this function

[Taywin]

Hmm... You adopted monarchmk method which is not a stack-liked method. Do you know what 'stack' is? The stack-liked pseudo code should be as followed:

/*
str <- a string which may be empty
stack <- a stack-liked storage
pos <- an integer of current position in the string

pos = 0
create an empty stack
while (pos < string_length)
  if str[pos] is an open bracket
    push str[pos] onto stack
  else if str[pos] is a closed bracket
    if the top of the stack matches the type of str[pos]
      pop the stack
    else
      return false  // invalid closing bracket, no need to go further
  increases pos by 1
end while

if the stack is empty
  return true  // all open brackets match their closed brackets
else
  return false  // some open brackets have no closed brackets
*/

I think I didn't forget anything...

[desert564]

so can you tell me what exactly is wrong with my one

[jon.kiparsky]

You're sort of doing a stack-ish thing there. But you'll notice that "lastOpen" doesn't rack anything but the most recent open brace type. If you have [{[]}) , how does it know that the } is correct and the ] is wrong?

Since you know that each closing brace has to match the most recent opening brace, you need a way to store each brace type in the reverse order that you encountered them. That's what a stack is for. In short, stacks store items and return them in greek pastry order - first in, last out, or filo.

If you haven't used stacks before, you should read up on them, and then look at the Stack class in java.util. It's worth your while to implement your own Linked Lists, Stacks, and Queues, so you really get a sense of the mechanics involved, but for the purposes of this assignment, you should probably just use the library stack code, unless that's forbidden.

[monarchmk]

@desert564
Even if you try non stacked way, i think, you could not do it with one variable. LastOpen would help only if brackets are in order [].If you had several different oppening you will know only how many opened brackets by type are, but not which one is last. After first closing bracket you will have lastOpen=null for the rest of code. So either stack-liked method or array to keep track of all brackets.

@Taywin

I don't know why you need equalsIgnoreCase() while these strings won't be 'case' anyway...

I do not know either :), it is problem with speeding instead of "(" i click on "I" so Eclipse choose wrong template proposal :).I see it but was already too late to correct it.

[jon.kiparsky]

I do not know either , it is problem with speeding instead of "(" i click on "I" so Eclipse choose wrong template proposal .I see it but was already too late to correct it.

Exhibit A for the prosecution in the IDE vs. editor argument. I've never had a mistake like that in vi... :)