• Post Reply Bookmark Topic Watch Topic
  • New Topic

Analyzing code that determines if a string is has a balanced delimiters  RSS feed

 
Aron Silvester
Ranch Hand
Posts: 63
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Did I answer this question correctly?

Question: Examine the following method – explain what it does; write the pre and post conditions.

For pre and post conditions I have:
- PreCondition: The String cannot be blank.
- PostCondition: A boolean value of true or false is returned whether the stack is empty once the program steps out of the for loop.

For explaining what the code does I have:
The method loops through all the characters of the string p. It takes each individual characters and analyzes. If it’s a left delimiter such as a parenthesis or a bracket, it adds it inside the stack which is referenced by the reference variable s. If it’s a right parenthesis, the method looks at the stack to see if it’s empty or there is no corresponding left parenthesis. If one of those condition is true then it returns false. The same is done if the next character is a right bracket. The default statement which throws an IllegalArgumentException if none of those cases executes.

 
Mike. J. Thompson
Bartender
Posts: 689
17
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
What is stopping the String being blank?*

*I take blank to mean the empty String "".
 
Piet Souris
Rancher
Posts: 1983
67
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hi Conrado,

excellent analysis.

I have two remarks though:

1) an empty string will give 'true' as a result, which is correct I think,
so the string might be blank (i.e. empty, but not null)

2) I would rather not talk about the stack being empty or not, but talk
about the string being balanced or not, when the boolean is returned.
The stack is only an implementing thing.
 
Mike. J. Thompson
Bartender
Posts: 689
17
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
For preconditions list the things that will cause the method to throw an exception. I can see one explicit case, and one implicit case.
 
Campbell Ritchie
Marshal
Posts: 55768
163
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I think this discussion is so similar to your other thread that the two should be merged into one.
 
Campbell Ritchie
Marshal
Posts: 55768
163
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I merged your stuff with the following thread. I hope that is okay by you.
 
Aron Silvester
Ranch Hand
Posts: 63
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This pseudocode is designed to determine if a sequence of parentheses is balanced. This design doesn't work. Here I give reasons for why it is an invalid design. Does anybody disagree with my statement? Also what (unbalanced) sequences will the code think is balanced?

Reasons:
- After the white loop executes it will print “balanced” regardless if the sequence is balanced or not.
- Since it will print balanced regardless of the sequence, all unbalanced sequence will be regarded as balanced by the code.


Pseudocode:

declare a character stack
while ( more input is available)
{
read a character
if ( the character is a '(' )
push it on the stack
else if ( the character is a ')' and the stack is not empty )
pop a character off the stack
else
print "unbalanced" and exit
}
print "balanced"
 
Mike. J. Thompson
Bartender
Posts: 689
17
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I think you are correct that the pseudocode does not work, but I don't think your reasoning is correct. If that code encounters the String ")" it will print "unbalanced", not "balanced".

Note that when the code prints "unbalanced", it immediately exits. It does not complete the while loop, so does not print the word "balanced".

I can see some cases where it will print the wrong thing though.

Try going through the following Strings and writing down exactly what will happen with each one.

"("
")"
"()"
"(()"
"(Test"
"(Test)"
"Test"
 
Piet Souris
Rancher
Posts: 1983
67
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hi Conrado,

well, if the string consists of only "(" it will be considered as balanced.
If the string is "A" it will be considered as unbalanced.

As for your two reasons:

a) correct, provided the while-loop is not exited by the 'print unbalanced and exit' statement
b) it will not always print 'balanced'; see my second 'if'
 
Campbell Ritchie
Marshal
Posts: 55768
163
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Alternative: have a bracketCount variable. Increment it for every ( and decrement it for every ).
 
Stefan Evans
Bartender
Posts: 1836
10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
With regards to your explanation of what the code does, I think you have gone into too much detail.
Taking the example from the pseudocode exercise: "determines if a sequence of parentheses is balanced"
That is a great example of saying what the code does, without going into detail.

You've written an almost blow by blow of the logic implemented in the code.
If you give that explanation to a non-technical person, their first question would be "but what does it DO?"
 
Aron Silvester
Ranch Hand
Posts: 63
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Mike. J. Thompson wrote:For preconditions list the things that will cause the method to throw an exception. I can see one explicit case, and one implicit case.


If the next character is not a delimiter, if it was a letter then none of the cases will execute and it will go to default and throw an exception. So another precondition will be the string has to be parenthesis or brackets or it will throw an IllegalArgumentExpetion?
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!