Write a C++ program to validate computer user-ids and passwords. A list of valid
ID: 3839406 • Letter: W
Question
Write a C++ program to validate computer user-ids and passwords. A list of valid ids and passwords (unsorted) is read from a file and stored in a Binary Search Tree (BST) of UserInfo objects. When user-ids and passwords are entered during execution, this BST is searched to determine whether they are legal.
Input (file): UserInfo records for valid users
Input (keyboard): Ids and passwords of users logging in
Output (screen): Messages indicating whether user-ids and passwords are valid, as well as an alphabetical listing of all valid ids and passwords at the end of the run.
Note: you will need to overload >>, <<, ==, and < operators in the UserInfo class in order to accomplish this task.
#include <iostream>
using namespace std;
#ifndef BINARY_SEARCH_TREE
#define BINARY_SEARCH_TREE
template <typename DataType>
class BST
{
public:
BST();
bool empty() const;
bool search(const DataType & item) const;
void insert(const DataType & item);
void emove(const DataType & item);
void inorder(ostream & out) const;
private:
class BinNode
{
public:
DataType data;
BinNode * left;
BinNode * right;
BinNode()
{
left = 0;
right = 0;}
// Explicit Value -- data part contains item; both links are null.
BinNode(DataType item)
{
data = item;
left = 0;
right = 0;
}
};// end of class BinNode declaration
typedef BinNode * BinNodePointer;
/***** Private Function Members *****/
void search2(const DataType & item, bool & found,
BinNodePointer & locptr, BinNodePointer & parent) const;
void inorderAux(ostream & out,
BinNodePointer subtreePtr) const;
/***** Data Members *****/
BinNodePointer myRoot;
}; // end of class template declaration
//--- Definition of constructor
template <typename DataType>
inline BST<DataType>::BST()
{myRoot = 0;}
//--- Definition of empty()
template <typename DataType>
inline bool BST<DataType>::empty() const
{ return myRoot == 0; }
//--- Definition of search()
template <typename DataType>
bool BST<DataType>::search(const DataType & item) const
{
BinNodePointer locptr = myRoot;
bool found = false;
while (!found && locptr != 0)
{
if (item < locptr->data) // descend left
locptr = locptr->left;
else if (locptr->data < item) // descend right
locptr = locptr->right;
else // item found
found = true;
}
return found;
}
//--- Definition of insert()
template <typename DataType>
inline void BST<DataType>::insert(const DataType & item)
{
BinNodePointer
locptr = myRoot, // search pointer
parent = 0; // pointer to parent of current node
bool found = false; // indicates if item already in BST
while (!found && locptr != 0)
{
parent = locptr;
if (item < locptr->data) // descend left
locptr = locptr->left;
else if (locptr->data < item) // descend right
locptr = locptr->right;
else // item found
found = true;
}
if (!found)
{ // construct node containing item
locptr = new BinNode(item);
if (parent == 0) // empty tree
myRoot = locptr;
else if (item < parent->data ) // insert to left of parent
parent->left = locptr;
else // insert to right of parent
parent->right = locptr;
}
else
cout << "Item already in the tree ";
}
//--- Definition of remove()
template <typename DataType>
void BST<DataType>::remove(const DataType & item)
{
bool found; // signals if item is found
BinNodePointer
x, // points to node to be deleted
parent; // " " parent of x and xSucc
search2(item, found, x, parent);
if (!found)
{
cout << "Item not in the BST ";
return;
}
//else
if (x->left != 0 && x->right != 0)
{ // node has 2 children
// Find x's inorder successor and its parent
BinNodePointer xSucc = x->right;
parent = x;
while (xSucc->left != 0) // descend left
{
parent = xSucc;
xSucc = xSucc->left;
}
x->data = xSucc->data;
x = xSucc;
} // end if node has 2 children
// Now proceed with case where node has 0 or 2 child
BinNodePointer
subtree = x->left; // pointer to a subtree of x
if (subtree == 0)
subtree = x->right;
if (parent == 0) // root being removed
myRoot = subtree;
else if (parent->left == x) // left child of parent
parent->left = subtree;
else // right child of parent
parent->right = subtree;
delete x;
}
//--- Definition of inorder()
template <typename DataType>
inline void BST<DataType>::inorder(ostream & out) const
{
inorderAux(out, myRoot);
}
//--- Definition of search2()
template <typename DataType>
void BST<DataType>::search2(const DataType & item, bool & found,
BinNodePointer & locptr,
BinNodePointer & parent) const
{
locptr = myRoot;
parent = 0;
found = false;
while (!found && locptr != 0)
{
if (item < locptr->data) // descend left
{
parent = locptr;
locptr = locptr->left;
}
else if (locptr->data < item) // descend right
{
parent = locptr;
locptr = locptr->right;
}
else // item found
found = true;
}
}
//--- Definition of inorderAux()
template <typename DataType>
void BST<DataType>::inorderAux(ostream & out,
BinNodePointer subtreeRoot) const
{
if (subtreeRoot != 0)
{
inorderAux(out, subtreeRoot->left); // L operation
out << subtreeRoot->data << " "; // V operation
inorderAux(out, subtreeRoot->right); // R operation
}
}
#endif
Explanation / Answer
Following is the required code. We have BST.cpp, BST.h and a file userInfo with input of usernames and passwords.
//BST.cpp
#include "BST.h"
#include <fstream>
#include <string>
using namespace std;
class UserInfo{
string userId, password;
public:
UserInfo(){
userId = "";
password = "";
}
UserInfo( string UserId, string Password ){
userId = UserId;
password = Password;
}
const string get_userId() const{ return userId; }
const string get_password() const{ return password; }
void set_userId( string UserId ){ userId = UserId; }
void set_password( string Password ){ password = Password; }
};
const bool operator <( const UserInfo& u1, const UserInfo& u2 ){
if( u1.get_userId() < u2.get_userId() ){
return true;
};
if( (u1.get_userId() == u2.get_userId()) and (u1.get_password() < u2.get_password())){
return true;
};
return false;
};
bool operator ==( const UserInfo& u1, const UserInfo& u2 ){
return ((u1.get_userId() == u2.get_userId()) and
(u1.get_password() == u2.get_password()) );
};
ostream &operator <<( ostream &output, const UserInfo& u ){
output << u.get_userId() << " " << u.get_password() << endl;
return output;
}
istream &operator >>( istream &input, UserInfo& u ){
string userId,password;
input >> userId >> password;
u.set_userId( userId );
u.set_password( password );
return input;
}
int main(){
string line;
ifstream in("./userInfo.txt");
BST<UserInfo> binaryTree;
UserInfo newInfo;
while( in >> newInfo ){
binaryTree.insert( newInfo );
}
//read the input from file
string userName,password;
cout << "Enter user name : ";
cin >> userName;
cout << "Enter password : ";
cin >> password;
UserInfo input( userName, password );
cout << endl;
if( binaryTree.search( input ) ){
cout << "The input is valid" << endl;
}
else{
cout << "Invalid user name or password" << endl;
}
//listing of all usernames and passwords
//use inorder one
cout << endl << "LISTING" << endl;
binaryTree.inorder( cout );
}
//BST.h
#include <iostream>
using namespace std;
#ifndef BINARY_SEARCH_TREE
#define BINARY_SEARCH_TREE
template <typename DataType>
class BST
{
public:
BST();
bool empty() const;
bool search(const DataType & item) const;
void insert(const DataType & item);
void remove(const DataType & item);
void inorder(ostream & out) const;
private:
class BinNode
{
public:
DataType data;
BinNode * left;
BinNode * right;
BinNode()
{
left = 0;
right = 0;}
// Explicit Value -- data part contains item; both links are null.
BinNode(DataType item)
{
data = item;
left = 0;
right = 0;
}
};// end of class BinNode declaration
typedef BinNode * BinNodePointer;
/***** Private Function Members *****/
void search2(const DataType & item, bool & found,
BinNodePointer & locptr, BinNodePointer & parent) const;
void inorderAux(ostream & out,
BinNodePointer subtreePtr) const;
/***** Data Members *****/
BinNodePointer myRoot;
}; // end of class template declaration
//--- Definition of constructor
template <typename DataType>
inline BST<DataType>::BST()
{myRoot = 0;}
//--- Definition of empty()
template <typename DataType>
inline bool BST<DataType>::empty() const
{ return myRoot == 0; }
//--- Definition of search()
template <typename DataType>
bool BST<DataType>::search(const DataType & item) const
{
BinNodePointer locptr = myRoot;
bool found = false;
while (!found && locptr != 0)
{
if (item < locptr->data) // descend left
locptr = locptr->left;
else if (locptr->data < item) // descend right
locptr = locptr->right;
else // item found
found = true;
}
return found;
}
//--- Definition of insert()
template <typename DataType>
inline void BST<DataType>::insert(const DataType & item)
{
BinNodePointer
locptr = myRoot, // search pointer
parent = 0; // pointer to parent of current node
bool found = false; // indicates if item already in BST
while (!found && locptr != 0)
{
parent = locptr;
if (item < locptr->data) // descend left
locptr = locptr->left;
else if (locptr->data < item) // descend right
locptr = locptr->right;
else // item found
found = true;
}
if (!found)
{ // construct node containing item
locptr = new BinNode(item);
if (parent == 0) // empty tree
myRoot = locptr;
else if (item < parent->data ) // insert to left of parent
parent->left = locptr;
else // insert to right of parent
parent->right = locptr;
}
else
cout << "Item already in the tree ";
}
//--- Definition of remove()
template <typename DataType>
void BST<DataType>::remove(const DataType & item)
{
bool found; // signals if item is found
BinNodePointer
x, // points to node to be deleted
parent; // " " parent of x and xSucc
search2(item, found, x, parent);
if (!found)
{
cout << "Item not in the BST ";
return;
}
//else
if (x->left != 0 && x->right != 0)
{ // node has 2 children
// Find x's inorder successor and its parent
BinNodePointer xSucc = x->right;
parent = x;
while (xSucc->left != 0) // descend left
{
parent = xSucc;
xSucc = xSucc->left;
}
x->data = xSucc->data;
x = xSucc;
} // end if node has 2 children
// Now proceed with case where node has 0 or 2 child
BinNodePointer
subtree = x->left; // pointer to a subtree of x
if (subtree == 0)
subtree = x->right;
if (parent == 0) // root being removed
myRoot = subtree;
else if (parent->left == x) // left child of parent
parent->left = subtree;
else // right child of parent
parent->right = subtree;
delete x;
}
//--- Definition of inorder()
template <typename DataType>
inline void BST<DataType>::inorder(ostream & out) const
{
inorderAux(out, myRoot);
}
//--- Definition of search2()
template <typename DataType>
void BST<DataType>::search2(const DataType & item, bool & found,
BinNodePointer & locptr,
BinNodePointer & parent) const
{
locptr = myRoot;
parent = 0;
found = false;
while (!found && locptr != 0)
{
if (item < locptr->data) // descend left
{
parent = locptr;
locptr = locptr->left;
}
else if (locptr->data < item) // descend right
{
parent = locptr;
locptr = locptr->right;
}
else // item found
found = true;
}
}
//--- Definition of inorderAux()
template <typename DataType>
void BST<DataType>::inorderAux(ostream & out,
BinNodePointer subtreeRoot) const
{
if (subtreeRoot != 0)
{
inorderAux(out, subtreeRoot->left); // L operation
out << subtreeRoot->data << " "; // V operation
inorderAux(out, subtreeRoot->right); // R operation
}
}
#endif
//userInfo.txt ( sample )
user1 pass1
user2 pass2
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.