Validating nested string in java

Question

Hi what is the best way to validate a nested string in java?

sample valid string is [aaaa{bbb}] while [{ss]} is not.

Thanks!

Answer 1

You have to be a bit more specific than that, I'm afraid. If you're just looking for a certain substring, there's String.contains(), if you want to validate something like "aaabbb cccddd eeefff" where you have to check if there's exactly three letters of each, then it's a job for regular expressions.

Answer 2

I'd use a stack. Iterate over the characters in the string, and every time I see an opening brace, I'd push the corresponding closing brace onto the stack. Every time I see a closing brace, I check to see if it matches the top of the stack. If so, I pop the character from the stack and keep going. Otherwise, it's an invalid string.

Answer 3

Split the string by "{" and "}", while pushing the tokens to a stack. See if everything checks out by the time you reach the last "}".

Answer 4

I like the stack answer, but depending on the rules for valid strings, that may get complicated. If you can construct a grammar to describe valid strings, you could probably generate a parser using something like ANTLR.