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)