tuff question in Java

[Adami]

I need to create a static boolean method, boolean isValid(String str) which gets a string and check the brackets in it...

a correct expression is an expression as one of the following:

1) an empty string or a string that includes space only in it.

2) st1 +"" +st2, which st1 and st2 are correct bracket expressions.

3) ("+st+") or ["+st+"] or {"+st+"} which st is a correct bracket expression.

examples:

isValid(" ") == true

isValid("() [] ") == true

isValid("{] [}") == false

Another condition is that the complexity must be linear which says O(0).

Is anyone please can write me a try of that method ?

Thanks !

Adam.

[javaAddict]

Try using str.charAt(i) in a for-loop. This method returns one by one each char of the String. Then you can count the different brackets that open and close and make sure that each time the bracket count must be positive or zero. At the end of the loop all bracket counts must be zero. You must also check that you don't have a case such as this which is wrong :
{ [ } ]

public static boolean isValid(String str) {
  //code here
}

[Adami]

Try using str.charAt(i) in a for-loop. This method returns one by one each char of the String. Then you can count the different brackets that open and close and make sure that each time the bracket count must be positive or zero. At the end of the loop all bracket counts must be zero. You must also check that you don't have a case such as this which is wrong :
{ [ } ]

public static boolean isValid(String str) {
  //code here
}

The idea with the str.charAt(i) looks not bad ! but.... that algorithm does not speaks about the { [ } ] problem ... I've tried already some solutions but zero results... can you show me a suggestion for a real java code for it ? (linear one...)

thanks!

[Ezzaral]

Obviously the point of your homework is for YOU to come up with a solution. Handing you the solution defeats the purpose. Post your code and describe what troubles you are having if you would like assistance.

[Phaelax]

Let's see what you've tried. Easiest method would be to just use regular expressions.

The method javaAddict describes is very simple. When you encounter an opening bracket, increment your bracket counter. When you encounter a closing bracket, decrement the counter. If the counter is 0 at the end of the FOR loop, then the equation should be valid.

[Ezzaral]

Stacks are useful for such things as well.

[javaAddict]

In case you have something like this: { [ } ], perhaps you should have some boolean variables for the different brackets(isCloded, isOpened) so you can check that you cannot close something if you are inside a different unclosed bracket. Try to remember the most recent open bracket

[Adami]

In case you have something like this: { [ } ], perhaps you should have some boolean variables for the different brackets(isCloded, isOpened) so you can check that you cannot close something if you are inside a different unclosed bracket. Try to remember the most recent open bracket

gotcha :)

Or you could just use an abstract data structure, such as a stack which is ideal for this, like Ezzaral suggested in post #6