9 replies to this topic

[lina]

1-Suppose an initially empty stack S has performed a total of 25 push operations, 12 top operations, and 10 pop operations, 3 of which generated EmptyStackExceptions, which were caught and ignored. What is the current size of S?


This what I did:
A total of 25 push operations performed on empty stack S indicate That S has 25 elements initially. Then 10 top operations were performed on S but it won’t affect the elements. Lastly, 10 pop operation was performed on S but 3 of them generated a EmptyStackException, which means that the size of S is 25 – 10 + 3 or 18 elements.

2- If we implemented the stack S from Problem 1 with an array, as described in chapter 5, then what is the current value of the top instance variable?

This what I did:

The current top instance variable is one less than the size of S, which is 17.

[lethalwire]

How can a stack throw an EmptyStackException if the stack isn't empty?

*Edit, unless those operations were not done in that order. Duh on my part.
I'd say anywhere from 15-18 elements.

Edited by lethalwire, 04 March 2011 - 11:25 AM.

[gregwarner]

Based on the wording of the original problem, it seems to suggest the stack underwent those operations, but not necessarily in that order. That's the only way there could be empty stack exceptions. Sounds to me like the problem is asking, "The stack underwent these operations in total, while experiencing these errors."

If there were a total of 10 pop operations, but 3 of them were unsuccessful, you can infer that 7 of the pop operations were successful.

As for part 2, there's no way of knowing without further information. Either the problem is worded very poorly, or there are some parts missing.

[lethalwire]

gregwarner said:

Based on the wording of the original problem, it seems to suggest the stack underwent those operations, but not necessarily in that order. That's the only way there could be empty stack exceptions. Sounds to me like the problem is asking, "The stack underwent these operations in total, while experiencing these errors."

If there were a total of 10 pop operations, but 3 of them were unsuccessful, you can infer that 7 of the pop operations were successful.

As for part 2, there's no way of knowing without further information. Either the problem is worded very poorly, or there are some parts missing.

Missing parts, yes.

Inferring that 7 pop operations were successful, no.
The top() operation can also throw EmptyStackExceptions.

[gregwarner]

lethalwire said:

Missing parts, yes.

Inferring that 7 pop operations were successful, no.
The top() operation can also throw EmptyStackExceptions.

I inferred from the wording "and 10 pop operations, 3 of which generated EmptyStackExceptions" that it meant 3 of the pop operations generated exceptions, but you could also parse it your way too. Just another testament to how poorly the original question was worded. The original poster should find out where the question came from and ask for clarification.

[lethalwire]

gregwarner said:

I inferred from the wording "and 10 pop operations, 3 of which generated EmptyStackExceptions" that it meant 3 of the pop operations generated exceptions, but you could also parse it your way too. Just another testament to how poorly the original question was worded. The original poster should find out where the question came from and ask for clarification.

You're right.
I googled the question and it comes from an older data structures book. There needs to be a set of standard rules or something similar to regulate how people post their questions.

[ZekeDragon]

lethalwire said:

There needs to be a set of standard rules or something similar to regulate how people post their questions.

We should write an English parser that parses an English sentence for ambiguities, and if it finds an ambiguous statement (which in English it will frequently), it should disallow the post. :)

That or we could always write in Lojban.

[gregwarner]

ZekeDragon said:

That or we could always write in Lojban.

Oh good lord, please no.

:P

[lethalwire]

ZekeDragon said:

We should write an English parser that parses an English sentence for ambiguities, and if it finds an ambiguous statement (which in English it will frequently), it should disallow the post. :)

That or we could always write in Lojban.

I do my crossword puzzles in Lojban :P

[ZekeDragon]

@OP: In the way that I interpret that sentence, yes, what you have is generally accurate. You should have 18 elements in the list, and assuming the stack is implemented with an array, the array index for that 18th element should be 17.