# Chapter 3: The Stack¶

## Example 1, page no. 28¶

In [2]:
MAXSIZE = 100

class stack:
def __init__(self):
self.stack = []
self.top = -1

def push(pu):
if(pu.top == MAXSIZE-1):
print "The stack is full"
else:
print "Enter the element to be inserted: "
item = int(raw_input())
pu.stack.append(item)
pu.top += 1

def pop(po):
if(po.top == -1):
print "Stack is empty"
else:
item = po.stack[po.top]
po.top-=1
print "The item deleted is: %d" %item

def traverse(pt):
if(pt.top == -1):
print "Stack is empty"
else:
print "The element(s) in the stack are..."
i = pt.top
while(i>=0):
print "%d" %pt.stack[i],
i-=1

ps = stack()
ch = 'y'

while(ch == 'Y' or ch == 'y'):
print "1. PUSH"
print "2. POP"
print "3. TRAVERSE"
choice = int(raw_input())
if(choice == 1):
push(ps)
elif(choice == 2):
pop(ps)
elif(choice == 3):
traverse(ps)
else:
print "You entered a wrong choice..."

print "\nPrint Y/y to continue"
ch = raw_input()

1. PUSH
2. POP
3. TRAVERSE
1
Enter the element to be inserted:
5

Print Y/y to continue
y
1. PUSH
2. POP
3. TRAVERSE
1
Enter the element to be inserted:
10

Print Y/y to continue
3


## Exampe 2, page no. 31¶

In [4]:
MAXSIZE = 100

class stack:

def __init__(self):
self.stack = []
self.top = -1

def push(self,pu):
if(pu.top == MAXSIZE-1):
print "The stack is full"
else:
print "Enter the element to be inserted: "
item = int(raw_input())
pu.stack.append(item)
pu.top += 1

def pop(self,po):
if(po.top == -1):
print "Stack is empty"
else:
item = po.stack[po.top]
po.top-=1
print "The item deleted is: %d" %item

def traverse(self,pt):
if(pt.top == -1):
print "Stack is empty"
else:
print "The element(s) in the stack are..."
i = pt.top
while(i>=0):
print "%d" %pt.stack[i],
i-=1

ps = stack()
ch = 'y'

while(ch == 'Y' or ch == 'y'):
print "1. PUSH"
print "2. POP"
print "3. TRAVERSE"
choice = int(raw_input())
if(choice == 1):
ps.push(ps)
elif(choice == 2):
ps.pop(ps)
elif(choice == 3):
ps.traverse(ps)
else:
print "You entered a wrong choice..."

print "\nPrint Y/y to continue"
ch = raw_input()

1. PUSH
2. POP
3. TRAVERSE
1
Enter the element to be inserted:
5

Print Y/y to continue
y
1. PUSH
2. POP
3. TRAVERSE
1
Enter the element to be inserted:
10

Print Y/y to continue
y
1. PUSH
2. POP
3. TRAVERSE
3
The element(s) in the stack are...
10 5
Print Y/y to continue
n


## Example 3, page no. 31¶

In [5]:
def fact(n):
if (n<=0):
return 1
else:
return n * fact(n-1)

print "Enter a number: "
n = int(raw_input())
n = fact(n)
print "Factorial is: %d" %n

Enter a number:
5
Factorial is: 120


## Example 4, page no. 36¶

In [6]:
class tower:

def __init__(self):
self.nodisk = 0
self.fromtower = ""
self.totower = ""
self.auxtower = ""

def hanoi(self,i, frm_t, to_t, aux_t):
if(i <= 1):
print "Move from disk 1 from tower " + frm_t + " to tower " + to_t
return
self.hanoi(i-1, frm_t, aux_t, to_t)
print "\nMove from disk " + str(i) + " from tower " + frm_t + " to tower " + to_t
self.hanoi(i-1,aux_t, to_t, frm_t)

print "-----------Tower of Hanoi-------------"
print "Enter number of disks: "
no = int(raw_input())
ob = tower()
ob.hanoi(no,'X','Y','Z')
print "Press any key to continue..."
raw_input()

-----------Tower of Hanoi-------------
Enter number of disks:
4
Move from disk 1 from tower X to tower Z

Move from disk 2 from tower X to tower Y
Move from disk 1 from tower Z to tower Y

Move from disk 3 from tower X to tower Z
Move from disk 1 from tower Y to tower X

Move from disk 2 from tower Y to tower Z
Move from disk 1 from tower X to tower Z

Move from disk 4 from tower X to tower Y
Move from disk 1 from tower Z to tower Y

Move from disk 2 from tower Z to tower X
Move from disk 1 from tower Y to tower X

Move from disk 3 from tower Z to tower Y
Move from disk 1 from tower X to tower Z

Move from disk 2 from tower X to tower Y
Move from disk 1 from tower Z to tower Y
Press any key to continue...


Out[6]:
''

## Example 5, page no. 48¶

In [9]:
MAXSIZE = 100

class stack:
def __init__(self):
self.stack = []
self.top = -1

def push(pu,symbol):
if(pu.top == MAXSIZE-1):
print "The stack is full"
else:
pu.stack.append(symbol)
pu.top += 1
return pu

def pop(po):
if(po.top == -1):
print "Stack is empty"
else:
symbol = po.stack.pop()
po.top-=1
return symbol,po

def prec(symbol):
if symbol == '(':
return 1
elif symbol == ')':
return 2
elif symbol == '+' or symbol == '-':
return 3
elif symbol == '*' or symbol == '/' or symbol == '%':
return 4
elif symbol == '^':
return 5
else:
return 0

def infix_postfix(infix):

length = len(infix)
ps = stack()
infix += ')'
ps = push(ps,'(')
postfix = []
for i in range(0,length+1):
ret_val = prec(infix[i])
if ret_val == 1:
ps = push(ps,infix[i])
elif(ret_val == 2):
ch,ps = pop(ps)
while(ch != '('):
postfix.append(ch)
ch,ps = pop(ps)
elif(ret_val == 3):
ch,ps = pop(ps)
while(prec(ch) >= 3):
postfix.append(ch)
ch,ps = pop(ps)
ps=push(ps,ch)
ps=push(ps,infix[i])
elif(ret_val == 4):
ch,ps = pop(ps)
while(prec(ch) >= 4):
postfix.append(ch)
ch,ps = pop(ps)
ps=push(ps,ch)
ps=push(ps,infix[i])
elif(ret_val == 5):
ch,ps = pop(ps)
while(prec(ch) == 5):
postfix.append(ch)
ch,ps = pop(ps)
ps=push(ps,ch)
ps=push(ps,infix[i])
else:
postfix.append(infix[i])

print "The postfix expression is: "
print postfix

choice = 'y'
while (choice == 'Y' or choice == 'y'):
print "Enter an infix expression: "
infix = raw_input()
infix_postfix(infix)
print "Do you want to continue? Y/y "
choice = raw_input()

Enter an infix expression:
a+b
The postfix expression is:
['a', 'b', '+']
Do you want to continue? Y/y
n


## Example 6, page no. 52¶

In [1]:
MAXSIZE = 100

class stack:
def __init__(self):
self.stack = []
self.top = -1

def push(self, pu, symbol):
if(pu.top == MAXSIZE-1):
print "The stack is full"
else:
pu.stack.append(symbol)
pu.top += 1
return pu

def pop(self, po):
if(po.top == -1):
print "Stack is empty"
else:
symbol = po.stack.pop()
po.top-=1
return symbol,po

def prec(self, symbol):
if symbol == '(':
return 1
elif symbol == ')':
return 2
elif symbol == '+' or symbol == '-':
return 3
elif symbol == '*' or symbol == '/' or symbol == '%':
return 4
elif symbol == '^':
return 5
else:
return 0

def infix_postfix(infix):

length = len(infix)
ps = stack()
infix += ')'
ps = ps.push(ps,'(')
postfix = []
for i in range(0,length+1):
ret_val = ps.prec(infix[i])
if ret_val == 1:
ps = ps.push(ps,infix[i])
elif(ret_val == 2):
ch,ps = ps.pop(ps)
while(ch != '('):
postfix.append(ch)
ch,ps = ps.pop(ps)
elif(ret_val == 3):
ch,ps = ps.pop(ps)
while(ps.prec(ch) >= 3):
postfix.append(ch)
ch,ps = ps.pop(ps)
ps = ps.push(ps,ch)
ps = ps.push(ps,infix[i])
elif(ret_val == 4):
ch,ps = ps.pop(ps)
while(ps.prec(ch) >= 4):
postfix.append(ch)
ch,ps = ps.pop(ps)
ps = ps.push(ps,ch)
ps = ps.push(ps,infix[i])
elif(ret_val == 5):
ch,ps = ps.pop(ps)
while(ps.prec(ch) == 5):
postfix.append(ch)
ch,ps = ps.pop(ps)
ps = ps.push(ps,ch)
ps = ps.push(ps,infix[i])
else:
postfix.append(infix[i])
print "The postfix expression is: "
print postfix

choice = 'y'
while (choice == 'Y' or choice == 'y'):
print "Enter an infix expression: "
infix = raw_input()
infix_postfix(infix)
print "Do you want to continue? Y/y "
choice = raw_input()

Enter an infix expression:
a+b
The postfix expression is:
['a', 'b', '+']
Do you want to continue? Y/y
n


## Example 7, page no. 57¶

In [ ]:
MAXSIZE = 100

class stack:
def __init__(self):
self.stack = []
self.top = -1

def push(pu,item):
if(pu.top == MAXSIZE-1):
print "The stack is full"
else:
pu.stack.append(item)
pu.top += 1
return pu

def pop(po):
if(po.top == -1):
print "Stack is empty"
else:
item = po.stack.pop()
po.top-=1
return po, item

def postfix_eval(postfix):
ps = stack()
for i in range(0,len(postfix)):
if(postfix[i]<='9' and postfix[i]>='0'):
ps = push(ps, postfix[i])
else:
ps, a = pop(ps)
ps, b = pop(ps)
a = int(a)
b = int(b)
temp = 0
if postfix[i] == "+":
temp = b+a
elif postfix[i] == "-":
temp = b-a
elif postfix[i] == "*":
temp = b*a
elif postfix[i] == "/":
temp = b/a
elif postfix[i] == "%":
temp = a%b
elif postfix[i] == "^":
temp = pow(a,b)
ps = push(ps, temp)
ps, a = pop(ps)
return a

choice = "y"
while(choice == "Y" or choice == "y"):
print "Enter the postfix expression: ",
post_fix = raw_input()
print "The post fix evaluation is ", postfix_eval(post_fix),
print "\nYou want to continue(Y/y) ?? "
choice = raw_input()

Enter the postfix expression: