See http://www.geeksforgeeks.org/the-stock-span-problem for problem description.
def stack_create():
return []
def stack_push(stack, value):
stack.append(value)
def stack_pop(stack):
return stack.pop()
def stack_top(stack):
return stack[-1]
def stack_is_empty(stack):
return len(stack) == 0
def stack_to_string(stack):
s = " TOP OF THE STACK\n"
s += "-------------------\n"
for v in reversed(stack):
s += str(v).center(20) + "\n"
s += "-------------------\n"
s += "BOTTOM OF THE STACK\n"
return s
p = [100, 80, 60, 70, 60, 75, 85]
def compute_span(prices):
s = []
# Traverse the list of prices
for i, price in enumerate(prices):
# For each price, traverse all the previous prices,
# incrementing S_i until we encounter a price that
# is larger than the current price.
s_i = 0
for prev_price in prices[i::-1]:
if prev_price > price:
break
else:
s_i += 1
s.append(s_i)
return s
compute_span(p)
# Stack-based implementation of the stock span problem.
# Notice how we only use the stack functions when interacting
# with the stack. We never access the values in the 'st' list
# directly.
def compute_span_stacks(prices):
s = []
# Create a stack
st = stack_create()
# Traverse the list of prices
for i, price in enumerate(prices):
# Pop elements from stack until we encounter a price that
# is greater than the current price, or until the stack
# is empty
while not stack_is_empty(st):
prev_price = prices[stack_top(st)]
if prev_price > price:
break
else:
stack_pop(st)
if stack_is_empty(st):
# If the stack is empty, then the current price
# is greater than all the elements to the left of
# it (note: this is trivially true for the first
# price in the list)
s_i = i + 1
else:
# Otherwise, the current price is only greater than the
# elements after the index at the top of the stack.
s_i = i - stack_top(st)
s.append(s_i)
# Push the index of this price into the stack
stack_push(st, i)
return s
compute_span_stacks(p)