Data Structures and Algorithms — Lab 7
Topic
To Understand the concept of Stack (Last In, First Out) through some basic applications and conversions
through stack.
Objectives
• Understand the purpose of Stack and how it follows the Last in, First Out Approach.
• Explore the use of Push and Pop Operations.
• Practice the implementation of expression evaluations.
• Develop and manipulate Stack data structures with advanced functionalities.
• Gain familiarity with practical applications of Stack.
Outcomes
1. Develop a comprehensive understanding of creating and using Stack to enforce specific behaviors.
2. Gain experience implementing Push and Pop Operations to define the essential working of the stack
with the help of LIFO.
3. Build practical skills in implementing a Stack data structure with advanced functionality, such as
custom insertion and inserting elements at the Top.
4. Enhance problem-solving skills by designing functions that meet specific operational requirements,
such as Expressions Evaluation and Stack Reverse.
Content
The following sections will be covered during this lab session:
1. Implementation of Basic Stack Operations
• Push: Add an element to the top of the stack.
• Pop: Remove the element from the top of the stack.
• Top: Retrieve the top element without removing it.
• Empty: Check if the stack is empty.
• Full: Check if the stack is full or not.
2. Advanced Stack Manipulation
• Extend Stack operations with specialized scenarios:
➢ Stack reverse
➢ Brackets matching
Task Instructions
Students are required to complete the following tasks during lab time. Create a private repository on your
GitHub accounts. The name of the repository should be Lab-5-DSA. All files should be uploaded to this
repository, including the header and cpp files. Please note that the name of class-related files should be the
same as the class name. If there is only 1 task, we can name the main file Task_1.cpp or Task.cpp. We
recommend you work in .h files for classes only since we must work on templates.
Page 1 of 4
Task 1- Basic Stack’s Implementation using ADT
You are required to implement a menu-driven program that performs various expression conversions
using stack data structure. Based on the user's input, your program should convert the given expression
accordingly.
Press 1 → Convert Infix to Postfix
Press 2 → Convert Infix to Prefix
Press 3 → Convert Postfix to Infix
Press 4 → Convert Prefix to Infix
Press 5 → Convert Postfix to Prefix
Press 6 → Convert Prefix to Postfix
Press 7 → Evaluate Postfix Expression
Press 8 → Evaluate Prefix Expression
Press 9 → Exit
Convert Infix to Postfix
Sample Input:
A+B*C-D
Expected Output:
ABC*+D-
Hint: Use the stack to handle operator precedence and associativity.
2. Convert Infix to Prefix
Sample Input:
(A + B) * (C - D)
Expected Output:
*+AB-CD
3. Convert Postfix to Infix.
Sample Input:
AB+CD-*
Expected Output:
(A + B) * (C - D)
Page 2 of 4
Task 2- Brackets Matching using stack
Write a program that checks whether the parentheses/brackets in a given expression are balanced or not
using a stack. An expression may contain the following types of brackets:
• Round Brackets: ( )
• Curly Brackets: { }
• Square Brackets: [ ]
You must use a stack to keep track of the opening brackets and check if each closing bracket correctly
matches the last opened one.
Input:
• A single string representing the expression.
Example:
(A + B) * [C - {D / E}]
Output:
• Display "Balanced" if the brackets are properly matched.
• Display "Not Balanced" if any mismatch or missing bracket is found.
Page 3 of 4
Page 4 of 4
