Experiment on Stack Data Structure

Objective : Design a data structure for stack. You have to decide on the data members and also the function
members if you use C++, analogous decisions need to be made for implementation in C. The basic member
functions are for i) construct an empty stack, ii) empty() : that returns true when a stack is empty and false
otherwise; iii) full() that returns true when stack is full and false otherwise; iv) push() to insert an element at top
of stack; v) pop() to delete the element from the top of stack and return the deleted element; vi) peek() to return
the element at top of stack without changing the stack contents. Operations, such as traverse() a stack, that lists
the elements from stack top to the bottom element, without changing the contents of the stack, copy() that
makes a copy of a given stack (without changing its contents), etc. are not commonly used but can be supported
if required.

Skills to be learnt : Design a stack data structure with associated functions; first using an array representation
and then using a linked list for organizing its data. Test both the designs using a common main() to ensure that
we may use either design by including the appropriate header file and get identical results.

Applications : After testing both the designs, use them to solve some sample application problems, such as
balanced parentheses, evaluation of postfix expression, conversion of infix to postfix, evaluation of infix
expression, a simple editor with undo and redo operations, etc.

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 can be directly compiled by using the header file given above.

(a) Complete the definition of “stack_array.h”. Compile and execute the program “stackuse.C” with input from
the file, “stringinp”, also given to you. Manually validate the output generated using your knowledge of
functioning of a stack.

(b) If you want to create a stack of integers, 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
integers as input.

Required Files : “stack_array.h”, “stackuse.C” and “stringinp”.

Problem 2. The following program fragment is given to you.

• A file, “stack_linked.h” that contains a partial implementation of a stack using a linked list. 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.

Make exactly one change in the file, “stackuse.C”, by replacing the earlier included header file to the one
defined by you here. Compile and execute the program “stackuse.C” with the input from the file, “stringinp”,
also given to you. Manually validate the output generated using your knowledge of functioning of a stack and
compare the outputs of Problems 1 and 2.

Required Files : “stack_linked.h”, “stackuse.C” and “stringinp”.

CS232/DS Lab/Stack Experiment/Supratim/Sept 2024/1

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
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.
(a) Complete the skeleton given in the file, “balpar.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

(b) The output message of part (a) 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

Input Files : “parinp”, “parinp0”, “parinp1”, “parinp2”

Program : “balpar-incomplete.C”

CS232/DS Lab/Stack Experiment/Supratim/Sept 2024/2

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 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. Definition of an integer stack and an incomplete C++ program is
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 : “stack_array_int.h", “postfix_evaluation_incomplete.C”

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.
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 -
You are provided with an incomplete file, “infix2postfix-incomplete.C”. This program reads a file,
“operator-attrs.txt” which is to be supplied through command line argument (file contains the
associativity and precedence values of a few C++ operators). Program initializes an array of objects
binops[], each element of which is an object of class oprprop. A support function, find() is also defined
to search for an operator in binops[] and return its index, if found.
(a) You are required to complete the body of “infix2postfix-incomplete.C” so that the program
performs its intended task.
(b) Enhance the program of part (a) so that an input infix expression with parentheses {‘(‘, ‘)’}, nested
or otherwise, is processed and equivalent postfix expression without parentheses is generated.
Input Files : “infix_inp1”, “infix_inp2”, “infix_inp3”, “infix_inp4”, “operator-attrs.txt”
Program Files : “stack_array.h”, “infix2postfix-incomplete.C”

CS232/DS Lab/Stack Experiment/Supratim/Sept 2024/3

Take Home Assignment : 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.

APPENDIX : ATTRIBUTES OF C++ OPERATORS

Precedence Associa Arity Operator Function

tivity
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

CS232/DS Lab/Stack Experiment/Supratim/Sept 2024/4

Precedence Associa Arity Operator Function
tivity
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 Experiment on Stack ############

CS232/DS Lab/Stack Experiment/Supratim/Sept 2024/5