Tag: recursive

Linked list – recursive functions

A linked list, is basically a list of elements that have a link attached to each one to the next. So for example if you have a structure like

struct List {
     string name;
     List *next;
};

then the List has a internals of a name which is of type string, and then a link (a pointer) to the next List in the list of linked List types. I have called it a Elem in the source code below because then it may make more sense, since it is kinder a element of the whole linked list.

So to create a I wrote a function to add a element (Elem) to the list already, since we are going to be altering the list then need to pass as a reference (&) so we actually alter the main variable and not just the functions variable and it is not passed back.

struct Elem {
	string name;
	Elem *next;
};
 
// inserts a Elem into a linked list
void setUpElem(Elem * & list, Elem *addnew)
{
	addnew->next = list;
	list = addnew;
}
 
.. 
int main()
{
    Elem *elem = NULL;
    Elem newElem;
    newElem.name = "bob";
 
    setUpElem(elem, &newElem);
}

with the function call setUpElem, I am passing the address of the newElem because that is the pointer (the address memory location).

So to start with the recursive functions, lets print out all of the elements,

// just print out the top element 
void printOutElem(Elem *elem)
{
	cout << "Name : " << elem->name << endl;
}
 
// recursive loop to print them all out
void printThemAllOut(Elem *list)
{
	if (list != NULL)
	{
		printOutElem(list);
		printThemAllOut(list->next);
	}
}

printOutElem will print out the element name associated with the parameter, and the cool recursive function called printThemAllOut, which just re-calls itself with the link to the next element to print out.. just a nice little function..

The next recursive that makes allot more sense, is when you are adding a element instead to the head of the list, but in the middle, like it is sorted, then if you was using loops you would require to keep hold of the previous element so that you can insert the new element into that previous elements -> next link and re-link the inserted element -> next to the current element in the list, hopefully the code helps to understand..

void insertIntoMiddle(Elem *&elem, Elem *midElem)
{
	Elem *cur, *pre= NULL;
 
	for (cur=elem; cur != NULL; cur= cur->next)
	{
		if (cur->name > midElem->name) break;
		// store where we was
		pre = cur;
	}
 
	// place the middle next element equal to where we are in the list
	midElem->next = cur;	
	// if the previous is not null, e.g. previous was somewhere in the list
	if (pre != NULL)
		pre->next = midElem;  // update the previous link to the middle element
	else
		elem = midElem;			// else probably is empty !!.. not good.. 
}

and here is a very nice recursive function that will do the same as above but just in recursive calls to itself with passing the previous link to itself so there is no need to keep a element of the previous link, very nice and allot more easier to debug since less code.

void insertIntoMiddleRecursive(Elem *&elem, Elem *midElem)
{
	if (elem == NULL || elem->name > midElem->name)
	{
		midElem->next = elem;
		elem = midElem;
	}
	else
		insertIntoMiddleRecursive(elem->next, midElem);
}

here is the full source code

#include <string>
#include <iostream>
 
using namespace std;
 
// the element structure, the name is the name of the person
// and the next is a link to next name
struct Elem {
	string name;
	Elem *next;
};
 
// inserts a Elem into a linked list
void setUpElem(Elem * & list, Elem *addnew)
{
	addnew->next = list;
	list = addnew;
}
 
// just print out the top element 
void printOutElem(Elem *elem)
{
	cout << "Name : " << elem->name << endl;
}
 
// recursive loop to print them all out
void printThemAllOut(Elem *list)
{
	if (list != NULL)
	{
		printOutElem(list);
		printThemAllOut(list->next);
	}
}
 
// you have to keep in contact with the current and previous 
// (since that is where we need to place the new element
void insertIntoMiddle(Elem *&elem, Elem *midElem)
{
	Elem *cur, *pre= NULL;
 
	for (cur=elem; cur != NULL; cur= cur->next)
	{
		if (cur->name > midElem->name) break;
		// store where we was
		pre = cur;
	}
 
	// place the middle next element equal to where we are in the list
	midElem->next = cur;	
	// if the previous is not null, e.g. previous was somewhere in the list
	if (pre != NULL)
		pre->next = midElem;  // update the previous link to the middle element
	else
		elem = midElem;			// else probably is empty !!.. not good.. 
}
 
// a far better way of doing this is to use recursive for inserting
// since the parameter is the previous link :)
// this is just a far nicer way of doing the above function
void insertIntoMiddleRecursive(Elem *&elem, Elem *midElem)
{
	if (elem == NULL || elem->name > midElem->name)
	{
		midElem->next = elem;
		elem = midElem;
	}
	else
		insertIntoMiddleRecursive(elem->next, midElem);
}
 
int main()
{
	Elem *elem = NULL;
 
	Elem newElem;
	newElem.name = "steve";
	setUpElem(elem, &newElem);
	Elem nextElem;
	nextElem.name = "genux";
	setUpElem(elem, &nextElem);
 
	printThemAllOut(elem);
 
	// now lets insert into the middle of the linked list
	Elem midElem;
	midElem.name = "henry";
	insertIntoMiddle(elem, &midElem);
 
	cout << "after the insert of \"henry\" into the middle" << endl;
	printThemAllOut(elem);
 
	Elem newMidElem;
	newMidElem.name = "janet";
	insertIntoMiddleRecursive(elem, &newMidElem);
 
	cout << "after the insert of \"janet\" into the middle - using recursive :) " << endl;
	printThemAllOut(elem);
 
 
 
    return 0;
}

and here is the output

Name : genux
Name : steve
after the insert of "henry" into the middle
Name : genux
Name : henry
Name : steve
after the insert of "janet" into the middle - using recursive :)
Name : genux
Name : henry
Name : janet
Name : steve

Warm up recursive problems

This is all about recursive problems and the part 1 of this assignment is warm up problems.

There are two warm up problems, one is Balancing parentheses and the second is Evaluating expressions, so lets start with the Balancing parentheses.

Balancing parentheses

To make sure that a there is opening and closing brackets within a string, the three brackets that we need to search for is {}, () and [] and if they are present in the string basically remove them and then recheck the string until it reaches “” (a empty state). If there is a non empty state of the string then return false, which means that the string is not balanced, here is a example taken from the assignment PDF file,

For example, the string “[(){}]” is shown to be balanced by the following chain of calls:
IsBalanced(“[(){}]”)
IsBalanced(“[{}]”)
IsBalanced(“[]”)
IsBalanced(“”) true

and here is the recursive code that I did come up with, the start is the empty string (str.size() == 0), else it tries to find the any one of the three strings in a for loop (breaks from the for loop if found) and if one is found then recall the IsBalanced function.

bool IsBalanced(string str)
{
	int strPos=-1;
	if (str.size() == 0)
		return true;
	string findStr[] = {"()", "[]", "{}"};
	for (int i =0; i < 3; i++)
	{
		strPos = str.find(findStr[i]);
		if (strPos >=0) 
			break;
	}
	if (strPos >=0)
		return IsBalanced(str.substr(0, strPos) + str.substr(strPos+2));	
	return false;
}

Evaluating expressions

Evaluating expressions is when you have a mathematical equation that you need to equate, so for example as taken from the PDF assignment file

EvalInfixExp(“3”) = 3
EvalInfixExp(“(4 + 8)”) = 12
EvalInfixExp(“(25 – (2 * 10))”) = 5

Where the EvalInfixExp is the function that we call recursive, the way that I thought about this is that if there is no spaces then return the value (e.g. base case) and if there is no brackets in the string then it must be a maths query, which get the two values and the mathematical function (/,+,-,*) and equate them returning that value, but then if there is a “(” at the start, since all equations are valid, then equate inside that ( .. ) brackets, but if there is any ( … ) inside that main ( … ) then figure them out first, which is why I using the first_last_of “(” function to find the the end ( .. ) to equate and then the associated “)”, which in turn we just need to recall the function EvalInfixExp to figure out the value inside the string.

To think about it, what is happening is that is works from the inside to the out finding the values of the ( .. ) to reinsert them back into the string (the result of them that is), so in the end all we do is equate the last mathematical equation.

Here is the cpp recursive function.

int EvalInfixExp(string expString)
{
	// so if the first character is ( then do else do other
	int brackPos1, brackPos2, returnValue =0;
	// try and find the outter ()
	if (expString[0] == '(')
	{
		brackPos1 = expString.find_last_of("(");
		brackPos2 = expString.find_first_of(")", brackPos1);
		// find the value within the () and replace with the new value
		if (brackPos1 >= 0 && brackPos2 >=0)
		{
			brackPos1++;
			returnValue = EvalInfixExp(expString.substr(brackPos1, brackPos2 - brackPos1));
			// need to replace the () with the value 
			brackPos1--;
			expString.replace(brackPos1, brackPos2 - (brackPos1-1), IntegerToString(returnValue));
		}
		return EvalInfixExp(expString);
	}
	else
	{	// find out the actual value of the maths function
		if (expString.find_first_of(" ") < 0 || expString.find_first_of(" ") > expString.size())
			return StringToInteger(expString);
		Scanner theExpScanner;
		theExpScanner.setInput(expString);
		theExpScanner.setSpaceOption(theExpScanner.IgnoreSpaces);
		int firstValue = StringToInteger(theExpScanner.nextToken());
		string op = theExpScanner.nextToken();
		string last;
		while (theExpScanner.hasMoreTokens())
			last += theExpScanner.nextToken();
		int secondValue = StringToInteger(last);
		if (op == "+")
			returnValue = firstValue + secondValue;
		if (op == "-")
			returnValue = firstValue - secondValue;
		if (op == "*")
			returnValue = firstValue * secondValue;
		if (op == "/")
			returnValue = firstValue / secondValue;
		return returnValue;
	}
}

I have attached the full source code and also the PDF assignment code.