CS 24102 : DATA STRUCTURE AND ALGORITHMS LABORATORY
Lab Assignment No : 5 Day & Date : September 25, 2025
Sections : IIIA-D; AIML Premises : SHA3, Lab 1, Lab 3, Lab7
Faculty : Akriti, Bikas, Debjani, Sandip, Shamama, Shruti and Supratim
Objectives: Design a class for a stack data structure - using an array and also a linked list; solve a few
application problems using stacks.
Resources Required : Linux and g++; knowledge of C++ language
Skills to be learnt : Design a data structure for stack using both an array and a linked list. Write algorithms for
basic stack functions, such as, creation of an empty stack; check if a stack is empty; check if a stack is full; insert
an element on top of stack; delete the element from the top of stack and return the element on top of stack.
Reinforcement of Concepts from Theory : Stack data structure - representation and operations.
Set-up : Follow the general instructions as given in the earlier lab sessions.
Problem 1. The following program fragments are given to you.
• A file, “stack_array.h” that contains a partial implementation of a stack using an array. You have to
complete the definitions of member functions, item_type pop ( ) {}; item_type peek() {}; bool empty ( )
{ } and bool full ( ) { }. Do not change the code given, unless it is absolutely necessary.
• A file, “stackuse.C”, that is complete and is to be directly, without any modifications, except for the
header file to be included, is to be used for compilation.
(a) Complete the definition of “stack_array.h”. Compile and execute the program “stackuse.C” with input from
the file, “[Link]”, also given to you. Manually validate the output generated using your knowledge of
functioning of a stack. In case all the strings in the input are not handled by the program, make minimal change
to ensure that all the input strings are processed.
(b) If you want to create a stack of real numbers, what are the changes needed in the files and at what locations
in either of the two files ? Implement the changes suggested by you and test the correctness by giving a list of
floating values as input.
Files provided : “stack_array.h”, “stackuse.C” and “[Link]”.
Problem 2. A file, “stack_linked.h” that contains a partial implementation of a stack using a linked list is
provided to you. You have to complete the function definitions. Do not change the code given unless it is
absolutely necessary. Make exactly one change in, “stackuse.C”, replacing the earlier included header file to the
one defined here. Compile and execute the program “stackuse.C” with the input from the file, “[Link]”
Manually validate the output generated using your knowledge of functioning of a stack and compare the outputs
of Problems 1 and 2.
Files Provided : “stack_linked.h”.
Problem 3. We are now prepared to test the designs to solve an application problem, known as Balanced
Parentheses Problem. A string is given as input, that contains three pairs of braces "(", ")", "[", "]", "{", and "}"
among other alphanumeric characters. The programming problem is to determine if all the parentheses in the
expression are balanced. If the expression has unbalanced parentheses, indicate the parenthesis that is
unbalanced in the expression, and also mention the parentheses pairs that are balanced (or matched). For
example, the string, “ x + ( y * [ 3 + z ) - 25 * { x + y] – 6} “ has 3 pairs of braces; the left brace of each pair
DSA Lab/Stack Experiment/Supratim/Sept 2025/1
occurs before its right counterpart, the number of left and right form of each brace match, yet the string is not
balanced with respect to parentheses. There are many imbalances with this string, such as
• The left brace “(“ before y does not have a matching right brace.
• The left brace “[“ before 3 does not have a matching right brace.
• The right brace “)” after z does no have a matching left brace
............
The algorithm that you must have learnt pushes a left parenthesis on a stack and matches an incoming right
parenthesis with the parenthesis on top of stack resulting in either a match or detection of an unbalanced right
parenthesis. Characters other than parentheses are read from the input and ignored. Complete the skeleton given
in the file, “balpar-incomplete.C”, in order to solve the problem. You have to check your design with both the
header files, one by one. The desired output for a few sample input files are given for your reference.
Input Desired Output
a(b{cd[5]2}1)0 parenthesis ] matches with stack-top [
parenthesis } matches with stack-top {
parenthesis ) matches with stack-top (
Input processing is over; Expression has balanced parentheses
a+(b*c(d{a]}cv)9{[ parenthesis ] does not match with stack top {
parenthesis } matches with stack-top {
parenthesis ) matches with stack-top (
Input exhausted but stack is non-empty
parenthesis [ is unbalanced
parenthesis { is unbalanced
parenthesis ( is unbalanced
Number of unbalanced parentheses in expression : 4
Input Files : “[Link]”, “[Link]”, “[Link]” Program : “balpar-incomplete.C”
Problem 4. Write a program to evaluate an expression in C or C++ which is given in postfix form. Recall that
there are 3 popular representations for an expression, depending on the location of an operator with respect to its
operands, and are summarized below. Consider the expression : a + b * c – d for which all the 3 forms are given.
Note that all the expressions are equivalent in the sense that they produce the same value. The properties of the C
/ C++ operators are given in the Appendix.
Infix form Prefix form Postfix form
a+b*c−d −+a*b c d a b c*+ d−
As you may be aware, a postfix expression is relatively easy to evaluate because they are parentheses free.
Given an expression in postfix form, involving the operators { +, -, *, /, %, } and integer operands, write a
program to find the value of the expression. The algorithm uses a stack to save the operands till it encounters an
operator at which point the sub-expression is evaluated and the result saved on stack. A few sample input and
output are given to you for your reference. Write your own program or use the incomplete C++ program given to
you. A few simple functions are also given, you may use them if you wish to do so.
Input / output Sample 1 Sample 2 Sample 3
Input postfix expression 2 5 + 6 * 12 4 / - 12 41 9 3 / % + 6 2 * -
Output result of expression result of expression 2 5 + 6 * 12 4 /
2 5 + 6 * 12 4 / - is 39 12 41 9 3 / % + 6 2 * - is 2 result of expression
expression is well formed expression is well formed 2 5 + 6 * 12 4 / is ….
expression is not well formed
Input Files : “postfix_inp1”, “postfix_inp2”, “postfix_inp3”, “postfix_inp4”, “postfix_inp5”
program files : “postfix_evaluation_incomplete.C”
DSA Lab/Stack Experiment/Supratim/Sept 2025/2
Problem 5. Write a program to convert an infix expression in C or C++ to its equivalent postfix form. For this
problem, you may assume that the infix expression is without parentheses. A few sample input and desirable
output are given below. The properties of a few C++ operators are given in "[Link]"
Input / output Sample 1 Sample 2 Sample 3
Infix expression 2 + 5 * 6 - 12 / 4 41 % 9 / 3 - 6 * 2 + 13 12 + 41 - 9 / 3 % 6 * 2 - 1
Postfix expression Infix expression is : Infix expression is : Infix expression is :
2 + 5 * 6 - 12 / 4 41 % 9 / 3 - 6 * 2 + 13 12 + 41 - 9 / 3 % 6 * 2 - 1
Postfix expression is : Postfix expression is : Postfix expression is :
2 5 6 * + 12 4 / - 41 9 % 3 / 6 2 * - 13 + 12 41 + 9 3 / 6 % 2 * - 1 -
Take Home Assignment :
1. The output message of Problem 3 can be misleading, specially in the case of multiple instances of the same
parenthesis in the expression, as the location of the parenthesis is not specified. State all the changes that are
required in the present design to change the output to the form shown below.
Input Desired Output
a+ ( b *c (d { a ] } c v ) 9 { [ parenthesis ] at position 11 does not match with stack top { at position 9
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 parenthesis } at position 12 matches with stack-top { at position 9
parenthesis ) at position 15 matches with stack-top ( at position 7
Input exhausted but stack is non-empty
parenthesis [ at position 18 is unbalanced
parenthesis { at position 17 is unbalanced
parenthesis ( at position 3 is unbalanced
Number of unbalanced parentheses in expression : 4
2. Modify the design of Problem 4 so that for an input in postfix form, the intermediate calculations that lead to
the final value is also displayed. See the desired output for a sample input given in column 3 below.
Postfix Problem 4 Desired Output
Expression
Input 2 5 + 6 * 12 4 / − 2 5 + 6 * 12 4 / −
Output Result of expression Evaluation of input postfix expression
2 5 + 6 * 12 4 / − is 39 1. 2 5 + value 7 2. 7 6 * value 42 3. 12 4 / value 3
4. 42 3 − value 39
The value of the expression is 39
3. Write a program that directly evaluates an infix expression. You are not permitted to convert the infix expression to
postfix form (as in Problem 5) and then evaluate the resultant postfix expression (as in Problem 4). Assume that the
input expression comprises of integer operands and a chosen subset of binary operators.
(a) You may test your design for the operators such as {*, /, %, +, −, = } and braces '(' and ')' as a first step.
(b). Extend the program so that it works for a larger subset of the table that would include other operators such as
relational, logical, etc.
DSA Lab/Stack Experiment/Supratim/Sept 2025/3
APPENDIX : ATTRIBUTES OF C++ OPERATORS
Precedence Associativity Arity Operator Function
17 R unary :: global scope
17 L binary :: class scope
16 L binary ->, . member selectors
16 L binary [] array index
16 L binary () function call
16 L binary () type construction
15 R sizeof size in bytes
15 R unary ++, -- increment, decrement
15 R unary ~ bitwise NOT
15 R unary ! logical NOT
15 R unary +, - unary minus, plus
15 R unary *, & dereference, address of
15 R binary () type conversion
15 R unary new, delete free store management
14 L binary ->*, .* member pointer selectors
13 L binary *, /, % multiplicative operators
12 L binary +, − arithmetic operators
11 L binary <<, >> bitwise shift
10 L binary <, <=, >, >= relational operators
9 L binary ==, != equality, inequality
8 L binary & bitwise AND
7 L binary ^ bitwise XOR
6 L binary | bitwise OR
5 L binary && logical AND
4 L binary || logical OR
3 L ternary ?: arithmetic if
=, *=, /=,
%=, +=, -=,
2 R binary assignment operators
<<=, >>=,
&=, |=, ^=
1 L binary , comma operator
L : Left Associative R : Right Associative
Precedence : Higher value denotes higher precedence
########## End of Stack Experiment ############
DSA Lab/Stack Experiment/Supratim/Sept 2025/4