Data Structures
Data Structures
Data Structures
1 Stacks
A stack is an ordered collection of items into which new items may be inserted and
from which old items may be deleted at one end, called the top of the stack. The
most important attribute of a stack is, that the last element inserted into a stack
is the irst element deleted. For this reason a stack is sometimes called a last-in,
irst-out (or LIFO) list.
The two operations which can be made to a stack are given special names. When an
item is added to a stack, it is pushed onto the stack, and when an item is removed, it
is popped from the stack. Given a stack s, and an item i, performing the push(s,i)
operation adds the item i to the top of the stack s. Similarly, the operation pop(s)
removes the top elements and returns it as a function value.
struct stack {
int top;
int items[ stacksize ];
};
# endif // ! STACK_H
Listing 1: Stack.h
{
if (s.top == stacksize - 1)
{
std :: cout << "\ nStack overflow ";
return ;
}
s.items [++s.top] = x;
}
int pop(stack& s)
{
if ( is_empty (s))
{
std :: cout << "\ nStack underflow ";
return 0;
}
return s.items[s.top ];
}
Listing 2: Stack.cpp
int main ()
{
stack s;
init_stack (s);
int i;
push(s, 1);
push(s, 2);
push(s, 3);
push(s, 4);
push(s, 5);
push(s, 6);
push(s, 7);
push(s, 8);
push(s, 9);
push(s, 10);
push(s, 11);
i = pop(s); std :: cout << "\npop(s) = " << i;
i = pop(s); std :: cout << "\npop(s) = " << i;
i = pop(s); std :: cout << "\npop(s) = " << i;
i = pop(s); std :: cout << "\npop(s) = " << i;
i = pop(s); std :: cout << "\npop(s) = " << i;
i = pop(s); std :: cout << "\npop(s) = " << i;
i = pop(s); std :: cout << "\npop(s) = " << i;
push(s, 12);
push(s, 13);
i = stacktop (s); std :: cout << "\ nstacktop (s) = " << i;
return 0;
}
Listing 3: TestStack.cpp
where x is a string consisting of the binary digits 0 and 1, and where y is the reverse
of x(that is, if x=010110, y must equal 011010). At each point you may read only
the next character of the string.
Solution.
We read the input string character-by-character and push each character onto the
stack until a ’2’ is encountered, at which point we begin popping the elements off
the stack. If the element popped matches the next character read, the process con-
tinues until the end of string, else the string is marked invalid. If the stack is empty
at any time, before the end of the string, the string is marked invalid.
Additionally, I have modiied the push() and pop() routines to include overflow
and underflow lags.
# ifndef STACK_H
# define STACK_H
struct stack {
int top;
char items[ stacksize ];
};
# endif // ! STACK_H
Listing 4: Stack.h
if (s.top == stacksize - 1)
{
std :: cout << "\ nStack overflow ";
overflow = 1;
return ;
}
s.items [++s.top] = x;
}
return 0;
}
return s.items[s.top ];
}
int main ()
{
stack s;
init_stack (s);
int i, len = 0, valid = 0;
std :: cout << "\ns1: " << s1 << " is " << valid;
std :: cout << "\ns2: " << s2 << " is " << valid;
std :: cout << "\ns3: " << s3 << " is " << valid;
std :: cout << "\ns4: " << s4 << " is " << valid;
if ( mid_of_string_flag )
{
x = pop(s, underflow );
if (x != str[i] || underflow )
valid = 0;
}
else
{
if (str[i] == '2')
{
mid_of_string_flag = true;
continue ;
}
else
{
x = str[i];
push(s, x, overflow );
}
}
}
if (! is_empty (s))
valid = 0;
return valid;
}
Listing 6: TestValidString1.cpp
a 3 b 3 c 3...3 z
where each string a, b, . . . , z is of the form of the string deined in problem (1).
Thus, a string is in the proper form, if it consists of any number of such strings
separated by the character ’3’. At each point you may read only the next character
of the string.
Solution.
The above solution is modiied as follows. Each time the character ’3’ is read, the
stack must be empty. If the stack is not empty, the entire string is marked invalid.
int is_valid (char* str , int len)
{
stack s;
int overflow = 0, underflow = 0;
init_stack (s);
break ;
}
mid_of_string_flag = false ;
overflow = 0; underflow = 0;
continue ;
}
if ( mid_of_string_flag )
{
x = pop(s, underflow );
if (x != str[i] || underflow )
valid = 0;
}
else
{
if (str[i] == '2')
{
mid_of_string_flag = true;
continue ;
}
else
{
x = str[i];
push(s, x, overflow );
}
}
}
if (! is_empty (s))
valid = 0;
return valid;
}
Listing 7: TestValidString2.cpp
Problem 3. Design an algorithm that checks for a valid algebraic expression such
as {x + (y − [a + b]) ∗ c − [(d + e)]}/(h − (j − k − [l − n]))). If one or more scopes
that have been opened have not been closed, the string is invalid.
Solution.
A stack may be used to keep track of the types of scope encountered. Whenever a
scope is opened, it is pushed onto the stack. When a closing bracket is encountered,
1 Stacks 10
we pop the stack and check whether the popped item corresponds to the scope
ender. If a match occurs, we continue. If it does not, the string is invalid. When
the end of the string is reached, the stack must be empty; otherwise one or more
scopes have been opened which have not been closed, and the string is invalid.
# include <iostream >
# include " Stack .h"
# include <cstring >
int main ()
{
std :: cout << "\ nstring s1: " << s1 << "is " << valid;
std :: cout << "\ nstring s2: " << s2 << "is " << valid;
push(s, x, overflow );
if ( overflow ) { valid = 0; break ; }
}
if (! is_empty (s))
valid = 0;
return valid;
}
Listing 8: TestValidString3.cpp
Solution.
Each operator in a postix string refers to the previous two operands in the string.
(Of course, one of these two operands may itself be the result of applying a previous
operator.) Suppose that each time we read an operand we push it onto a stack.
When we reach an operator, its operands will be the top two elements on the stack.
We can then pop these two elements, perform the indicated operation on them,
and push the result on the stack, so that it will be available for use as an operand
of the next operator.
double evaluate_postfix (char* str , int len)
{
stack operand_stack ;
1 Stacks 12
init_stack ( operand_stack );
int overflow = 0, underflow = 0, valid =1;
int i = 0; char symbol ;
double operand1 = 0, operand2 = 0, result =0;
while (i<len)
{
/*1. Read the next symbol from the postfix expression
.*/
symbol = str[i];
if ( operator1 == '$')
priority1 = 3;
if ( operator2 == '$')
priority2 = 3;
if (prcd >= 0)
return true;
else
return false ;
}
Listing 10: ToPostFix.cpp
Note that at each point of the simulation, an operator on the stack has a lower
precedence than all the operators above it. This is because, the initially empty
stack trivially satisies this condition, and an operator is pushed onto the stack
only if the operator currently on top of the stack has a lower precendence than
the incoming operator. Intuitively, the highest precedence operator in an inix ex-
pression must irst be converted to postix, so that they can be treated as single
operands.
What modiication must be made to this algorithm to accomodate parentheses?
The answer is surprisingly little.