Scribd
Upload
4 views1 page

Understanding Stacks: LIFO Operations & Uses

Chapter 4 discusses the implementation and evaluation of stacks, focusing on converting infix expressions to postfix and evaluating postfix expressions. It details the operations of stacks, including push, pop, and peek, and highlights their applications in various scenarios such as string reversal and expression evaluation. The chapter also outlines special cases like underflow and overflow, emphasizing the importance of these operations in arithmetic expression handling.

Uploaded by

varshachandrashekar05
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
4 views1 page

Understanding Stacks: LIFO Operations & Uses

Chapter 4 discusses the implementation and evaluation of stacks, focusing on converting infix expressions to postfix and evaluating postfix expressions. It details the operations of stacks, including push, pop, and peek, and highlights their applications in various scenarios such as string reversal and expression evaluation. The chapter also outlines special cases like underflow and overflow, emphasizing the importance of these operations in arithmetic expression handling.

Uploaded by

varshachandrashekar05
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

Mapping – Chapter 4 STACKS

Infix to Postfix Evaluation of postfix expression


1. Create an empty string known as [Link] 1 = For each character in
postfix and stack known as postfix expression.
stack. • if operand: push to stack
2. For each character in infix • if operator : pop 2 operands
expression apply the operations push the
3. If ( then push to stack result into the stack
4. If ) then pop and add to postfix 2. STEP 2 = At the end, if 1 item in
until ( is found stack, pop the result
5. If operator = pop higher or equal 3. STEP 3 = Else, invalid expression
precedence operators & append
to post fix EX. 35+1*
6. Push current operator
7. If operand = append to postfix
8. Pop remaining operators to
postfix 5 1

3 3 8 8 8
EX. (A+B) *(E/F)
A+B = AB+ - P 5+3= 8 8*1 = 8
E/F = EF/ - Q
[Link] operation
= P*Q = PQ* Functions:
def oppush (stack , item):
= AB+EF/* 3. isempty()
stack append(item): def isempty(stack):
2. Pop operation if len(stack)==0:
Def oppop(stack): return True
if isempty(stack):
else:
print("stack underflow")
return False
return none
else: 4. size()
return [Link]() def size(stack):
return len(stack)

Summary of the lesson [Link]()


i. Stack= Linear Data structure def isfull(stack):
ii. Stack follows LIFO Principle if len(stack) == size:
iii. Operations – push, pop, peek(), isempty(), isfull(), size(), overflow, True
underflow else:
iv. Applications – String reversal, undo-redo in editors, back tracking, back return False
function in web browsers, parenthesis matching in expression.
v. Implementation function [Link]()
vi. Imp – push, pop, peek, isempty def peek(stack):
vii. Special cases {Rare cases} – isfull, size, display if isempty(stack):
viii. Arithmetic notations print("stack underflow")
ix. 1. Infix – a+b 2. Prefix - +ab 3. Postfix – ab+ return none
x. List Datatype is used to create an empty stack else:
xi. Append method is used to push the elements and pop method is used to pop return stack[-1]
the element
xii. Stacks are essential in converting and evaluating arithmetic expression [Link]()
xiii. [PS: Conversion algorithm an evaluation of arithmetic expression is imp, def display(stack):
the imp operations are push, pop and peek, special cases= Overflow & n = len(stack)
underflow] print("Elements in stack are:")
for i in range(n-1, -1, -1):
print(stack[i])

You might also like