Scribd
Upload
10 views2 pages

Stack Revision Notes

The document provides a comprehensive overview of stacks, a linear data structure that operates on a Last In, First Out (LIFO) principle. It includes basic stack functions in Python, methods for balancing parentheses, converting infix expressions to postfix, and evaluating postfix expressions. Key functions such as push, pop, and is_balanced are defined, along with algorithms for expression conversion and evaluation.

Uploaded by

Avinash Chauhan
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
10 views2 pages

Stack Revision Notes

The document provides a comprehensive overview of stacks, a linear data structure that operates on a Last In, First Out (LIFO) principle. It includes basic stack functions in Python, methods for balancing parentheses, converting infix expressions to postfix, and evaluating postfix expressions. Key functions such as push, pop, and is_balanced are defined, along with algorithms for expression conversion and evaluation.

Uploaded by

Avinash Chauhan
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

STACKS - COMPLETE REVISION NOTES

1. What is a Stack?

A stack is a linear data structure that follows LIFO (Last In, First Out) principle. It supports operations like

push (insert), pop (remove), peek (view top), and isEmpty().

2. Basic Stack Functions in Python

def push(stack, element):


stack.append(element)

def pop(stack):
if not stack:
print("Underflow!")
return None
return stack.pop()

def top(stack):
if not stack:
print("Stack is empty.")
return None
return stack[-1]

def isEmpty(stack):
return len(stack) == 0

def display(stack):
for i in range(len(stack) - 1, -1, -1):
print(stack[i])

3. Parenthesis Balancing

def is_balanced(expr):
stack = []
for ch in expr:
if ch == '(':
stack.append(ch)
elif ch == ')':
if not stack:
return False
stack.pop()
return len(stack) == 0

4. Infix to Postfix Conversion

def precedence(op):
if op in '+-': return 1
if op in '*/': return 2
return 0

def is_operator(c):
STACKS - COMPLETE REVISION NOTES

return c in '+-*/'

def infix_to_postfix(expression):
stack = []
postfix = []
for token in expression.split():
if token.isdigit():
postfix.append(token)
elif token == '(':
stack.append(token)
elif token == ')':
while stack and stack[-1] != '(':
postfix.append(stack.pop())
stack.pop() # remove '('
elif is_operator(token):
while stack and precedence(stack[-1]) >= precedence(token):
postfix.append(stack.pop())
stack.append(token)
while stack:
postfix.append(stack.pop())
return ' '.join(postfix)

5. Postfix Evaluation

def evaluate_postfix(expression):
stack = []
for token in expression.split():
if token.isdigit():
stack.append(int(token))
else:
b = stack.pop()
a = stack.pop()
if token == '+':
stack.append(a + b)
elif token == '-':
stack.append(a - b)
elif token == '*':
stack.append(a * b)
elif token == '/':
stack.append(a // b)
return stack.pop()

You might also like