# Check whether a given sequence can be rearranged using a stack

Working on a problem, for a given input sequence to a stack, check whether it could produce (using stack push/pop operations) the output sequence.

For example if input is [1,2,3,4,5], possible output is [4,5,3,2,1] (push 1, push 2, push 3, push 4, pop 4, push 5, pop 5, pop 3, pop 2, pop 1), but [4,3,5,1,2] is not a feasible output.

Here is my code written in Python 2.7, and wondering if logically is correct?

stackInput = [1,2,3,4,5]
expOutput = [4,5,3,2,1] # return True
#expOutput = [4,3,5,1,2] # return False
stack = []
outputIndex = 0
result = True
i = 0

while i < (len(stackInput)):
stack.append(stackInput[i])
i += 1
while outputIndex < len(expOutput) and stack[-1] == expOutput[outputIndex]:
stack.pop(-1)
outputIndex += 1

print outputIndex == len(expOutput)


FYI, this question is probably off-topic here because you asked "if [the code] is correct" instead of merely asserting that it was correct and waiting for someone else to find the bugs. ;) However, I think your code is correct, although it can be improved.

The biggest improvement you should make is to use functions. See your first few lines?

stackInput = [1,2,3,4,5]
expOutput = [4,5,3,2,1] # return True
#expOutput = [4,3,5,1,2] # return False


Commented-out code is a code smell. In this case, the root problem is that you need a way to run your algorithm with two (or more) different inputs... and the structured-programming solution to that is to use a function. Example:

def canBeReachedByStackManipulations(stackInput, expOutput):
# ...
return outputIndex == len(expOutput)

assert canBeReachedByStackManipulations([1,2,3,4,5], [4,5,3,2,1]) == True
assert canBeReachedByStackManipulations([1,2,3,4,5], [4,3,5,1,2]) == False


Ta-da, your whole program works without needing manual commenting-and-uncommenting! And as a bonus, you've gotten started on writing unit tests for your function.

By the way, I called the parameters stackInput and expOutput because that's what you did; but in practice I would call them input and output.

i = 0
while i < (len(stackInput)):
stack.append(stackInput[i])
i += 1


First, (len(stackInput)) is a silly way to write len(stackInput).

Second, you should learn about for-loops. What you wrote is equivalent to

for value in stackInput:
stack.append(value)


and if you actually needed the i for some reason, you could have written

for i, value in enumerate(stackInput):


It's strange that you call your output index outputIndex but you call your input index i. Your readers will appreciate it if you keep symmetry as much as possible: write inputIndex and outputIndex, or else write i and j, but don't mix and match like that.

result appears to be unused. This is especially obvious once you start using functions, because then it becomes an unused local variable, and there are plenty of tools out there (e.g. pyflakes or pep8) which will "lint" your code for unused variables and other trivial mistakes. You should get in the habit of using one of these linters and fixing all the issues it finds, even before you run your code for the first time.

Finally, here's your bug! (Remember how I said I thought your code was correct? Well, I did...)

assert canBeReachedByStackManipulations([1,2,3], [1,2,3]) == True

Traceback (most recent call last):
File "x.py", line 17, in <module>
assert canBeReachedByStackManipulations([1,2,3], [1,2,3]) == True
File "x.py", line 10, in canBeReachedByStackManipulations
while outputIndex < len(expOutput) and stack[-1] == expOutput[outputIndex]:
IndexError: list index out of range

• Thanks for pointing out the bug, I fix it by adding another and condition while outputIndex < len(expOutput) and len(stack) > 0 and stack[-1] == expOutput[outputIndex]:. Mark your reply as answer and vote up as well. Commented Aug 9, 2016 at 4:42