Assignment 1 Solution

The solution for the first assignment can be obtained from here

Priority Queue

The code for the priority queue can be obtained from here.

Recursion

The code of all the recursion functions can be obtained from here:

Converting Infix Expression to Postfix

This is a pseudocode of the program that can covert an Infix expression to postfix expression. The same pseudocode is given in your course book as well, but I have written it in a way that it is more understandable. The code has a precedence() function that returns true or false, depending on the precedence of the operators. so if it is precedence('*', '+'), it will return true and also true for precedence('*', '*'). You must keep in mind that for precedence('$', '$'), the return value is false.

Get expression from user //Say A*B+C or A+B*C$D$E
initialize operatorStack as empty //A stack for only storing operators +,-,*,/,$
initialize postfixString //The created postfix string

char Symbol;
char topSymbol;

//While loop will run till the end is reached
while(!endOfExpression())
{
Symbol = getCharacterFromExpression()
if(SymbolIsOperand())
{
add Symbol to postfixString;
}
else
{
while(!operatorStack.isEmpty() && precedance(operatorStack.getTop(), Symbol))
{
topSymbol = operatorStack.pop();
add topSymbol to postfixString;
}
operatorStack.push(Symbol);
}
}

while(!operatorStack.isEmpty())
{
topSymbol = operatorStack.pop();
add topSymbol to postfixString;
}

One of the problems that came up during the assignment was the class redefinition error as both the stack and the queue classes were using the same Car.h header file. One way of avoiding that problem is to make 2 different projects and work in them. Another way is to do a bit of programming.

You can use macros to keep check of the files that might be redefined and thus you avoid the error altogether and do not need to make two separate projects. So, you will define your car.h file like this:

#ifndef CAR_H //This checks if the header file was defined
#define CAR_H //If it was not defined, it will define it

class Car
{
private:
int milage;
int passengers;
int model;
char* name;
public:
Car();
void setmilage(int);
int getmilage();

void setpassengers(int);
int getpassengers();

void setmodel(int);
int getmodel();

void setname(char* );
char* getname();
};


#endif /* CAR Seen */

Infix, Prefix and Postfix notations

The next lecture id going to be about infix, postfix and prefix notations. After explaining the three notations, I will go and explain the algorithm for implementing and calculating postfix notation while using a stack. You can read about the postfix notation here. you can also read about it in the book, Data Structures using C and C++ by Tenenbaum on page 95. I created a working program using the pseudo code as given in the Tenenbaum book in Visual C++. You can get it from here. You should see how I have created the entire project, declared the header files, the cpp files and how I used one of the classes as static, to use its functionality. I will be explaining this in class as well. The assignments that you submit should be similarly done. I also hope that you will get to learn Visual C++ IDE and debugging as you proceed.

Lab No. 3

A stack is exactly what it means, like a stack of books, a stack of cards and in such a stack, it is known that the item that is readily available is the top most item. Thus, when we add an item, we add it to the top and when we remove an item, we remove it from the top. This way of accessing data, earns it the name of a LIFO data structure. The implementation of the stack is as follows:
#include
class Stack
{
private:
char* data; //character pointer
int head; //index counter
int maxSize; //maximum array size
public:
Stack(int);
void push(char);
char pop();
};

Stack::Stack(int num)//Constructor
{
head = -1; //setting head to -1;
maxSize = num;
data = new char[maxSize]; //declaring the stack size
for(int i = 0; i < maxSize ;i++) //initialising all values to NULL
{
data[i] = '\0'; //putting NULL values in the data array
}
}

void Stack::push(char c)//Adding a value
{
if(head == -1)
{
head++;
data[head] = c;
}
else if(head < maxSize - 1)
{
head++;
data[head] = c;
}
else
{
cout<<"Stack is full.";
}
}
char Stack::pop()
{
char c;
if(head==-1)
{
cout<<"Stack is empty.";
}
else
{
c = data[head];
head--;
}
return c;
}

Circular Queue:
In a queue, the item that is added first is removed first, thus it is commonly known as a FIFO data structure. A common example of a queue is when you join a line in front of a cinema to buy tickets. Circular queue is a bounded queue. It is better than a normal queue because in this we can effectively utilize the memory space. The implementation of the circular queue is as following:

#include
typedef int bool;
const int false = 0;
const int true = 1;

class CircularQueue
{
private:
int head;
int tail;
int maxSize;
char* data;
public:
CircularQueue(int);
~CircularQueue();
bool isFull();
void push(char);
void pop();
};


CircularQueue::CircularQueue(int num)
{
head = tail = -1;
maxSize = num;
data = new char[num];
}
CircularQueue::~CircularQueue()
{
delete[] data;
}


bool CircularQueue::isFull()
{
return(head == tail+1 || (head == 0 && tail == maxSize-1) );
}


void CircularQueue::push(char c)
{
if(!isFull())
{
if(tail == -1 || tail == maxSize-1)
{
tail = 0;
data[tail] = c;
if(head == -1)
{
head = 0;
}
}
else
{
tail++;
data[tail] = c;
}
cout<<"\nPushed " ;}
else
{
cout<<"\nQueue is Full.\n";
}
}


void CircularQueue::pop()
{
char temp;
temp = data[head];


if(head == -1 && tail == -1)
{
cout<<"\nStack is Empty\n";
}
else
{
if(head == tail)
{
head = tail = -1;
}
else if(head == maxSize-1)
{
head = 0;
}
else
{
head++;
}
cout<<"\nPopped "; }
}

Lab Tasks:

1) Write a program to create a stack of books in a library. Modify the code of stack class given in the handout so that it works for strings and verify the methods of the stack class. (Hint: You can create a structure which stores the name of the book and then create an array of that structure to implement stack)

Linked lists and Stack

This is the place where all the pointers, objects and structures come together. A pointer can be used to point towards a memory location. That memory location can hold a pointer, a variable, a structure an array of structure and so on. Once we have pointers that start pointing towards structures, the C++ starts to become both interesting and complicated. Again, if you do not forget how the pointers work, you will have no problem in understanding the concept of linked lists.

We start off by defining a very basic structure called "node" which holds the data that we want to store and a pointer that helps in pointing towards other nodes. This structure can be defined as this:

struct node

{

char data;

node* next;

};

Now, we define our interface for the stack class that we are going to create, like this:

class stack

{

private:

node* head;

public:

stack();

~stack();

void push(char c);

char pop();

};

if you remember the stack implementation through arrays, you will see that the class looks almost the same, with slight differences. The real differences come when you start to implement the various functions. In order to understand how these functions work, attending the classes should do you good. The code that lets you make a stack is as following:

stack::stack()

{

head = NULL;

}

stack::~stack()

{

}

void stack::push(char c)

{

if(head == NULL)

{

head = new node;

head->data = c;

head->next = NULL;

}

else

{

node* temp = new node;

temp->data = c;

temp->next = head;

head = temp;

temp = NULL;

}

}

char stack::pop()

{

char c = '\0';

if(head == NULL)

{

cout<<"\nStack Empty";

return c;

}

else

{

node* temp = head;

head = head->next;

c = temp->data;

delete temp;

temp = NULL;

}

return c;

}

I have made and performed this code myself, so there does not seem to be any problem. You can now try the code yourself and see how the stack works by using nodes. Once you learn this, going through queues and trees is going to be a lot of fun.