#include<iostream>
using namespace std;

int main()
{
    char s[30];            //initialize the string

    cout<<"Enter the first line of the address: "<<endl;
    cin.getline(s, 20);   //get 20 characters

    cout<<s;              //print the string.

    return 0;
}

#include<iostream>
#include<string>
using namespace std;

int main()
{
    string s;            //C++ string

    cout<<"Enter the first line of the address: "<<endl;
    getline(cin, s);   // get the line until a line break

    cout<<s;      

    return 0;
}

#include <iostream.h>
#include <iomanip.h>
#include <string.h>
#include <ctype.h>
#include <fstream.h>
#include <stdlib.h> // for exit(1)

//using namespace std;


const int
	keyLength = 20,
	NIL = 0;

struct recType {					// data about a stock
 char key[keyLength];				// First Name (ex: Dale)
 char lName[keyLength];				//Last Name
 char addString[40];
 char city[keyLength];				//City
 char state[2];						//Two letter state ID
 int zip;							//Zip Code
}; // recType

enum lastChange {ADD, DELETE, UPDATE};
	// what was the last change to the data?


//////////////////////
//    stack class   //
//////////////////////

struct operationType {
	recType lastInfo;						// the contents of the record that was changed
	lastChange lastChangeWas;		// the operation that was performed
}; // operationType

// Class to maintain a simple stack.
class stack {
	// Structure for one node of the stack.
	private:
		struct node {
			operationType item;
			node *next;         // Pointer to the next node of the stack
		};
		node *head;             // Pointer to the head node of the stack
	public:
		stack();                 // Constructor. Creates an empty stack
		~stack();                // Destructor.  Restores memory to the heap
		void push(operationType);  // Push one item to the stack
		bool pop(operationType &); // Pop one item from the stack
		bool empty();			 // Test whether the stack is empty
		void clearStack();		 // Removes all records from the stack
}; // class stack


//////////////////////
//    Tree Class    //
//////////////////////

class treeClass {
	// holds and manipulates a binary tree of records (recType)
	// recType must have a field named key which is type char*
	//		key must uniquely identify a record
	// conditions maintained in object:
	//	 record ordered by key
	//	 no repetitions
	public:
		treeClass();									// constructor
		~treeClass();								// destructor
		void addRec (recType rec);	// adds record if it does not exist
		void deleteRec (char code[keyLength]);
							// deletes record with code = key.
		void findRec (char code[keyLength], recType &rec);
							// returns record with key = code
		void updateRec (recType rec);
							// locates and replaces current entry with record
		bool allOK ();			// returns the value of ok, then resets it to true
		int howManyRec();			// returns the number of records
		void undo();					// undoes last insert/delete
		void storeToDisk (char name[]);	// stores records to the disk under name
		void fetchFromDisk (char name[]);
					// loads records from disk; appends to current records
					// makes no assumptions about the order of records in main memory
		void deleteAllRecords (); // deletes all records from the linked list
		void treeClass::inTraversal(); // prints out tree elements in order
		void treeClass::inLevels();//Prints out tree level data
		
private:
		struct node {
			recType item;     	// Data item. One record stored at each node
			node *left, *right;	// Pointer to the left and right branches of the tree
		}; // node
		node *root;           // Pointer to the root node of the tree
		bool ok;						// holds true until an operation fails
		int min;// Small tree level
		int max;// Large tree level
		int avg;//Avg tree level
		int levelcount;//Counter for average
		int rectotal; //Total # of records.  Used in How Many Records.
		void treeLevels(node *it);//Prints out largest and smallest tree levels
		stack changes;
		void inTraversalRecur(node *it); // used by inTraversal
		void recDeleteAllRecords(node *thisun);
}; // treeClass

/////////////////////////////////////
//    Tree Class Implementation    //
/////////////////////////////////////


void treeClass::storeToDisk (char name[]) {
// stores records in a textfile under name
	cout <<"In storeToDisk.  Not implemented." <<endl;
} // treeClass::storeToDisk


void treeClass::fetchFromDisk (char name[]) {
// loads records from disk; appends to current records
// makes no assumptions about the order of records in main memory
	recType record;
	ifstream inFile (name, ios::in);
	if (!inFile) 			// file failed to open?
		ok= false;
	else {
		ok= true;
		int size= sizeof (recType);
		while (!inFile.eof()) {
			inFile.read ((char *) &record, size);
			addRec (record);
		} // while
		inFile.close();
		ok= true;
	} // if
} // treeClass::fetchFromDisk

int treeClass::howManyRec() {	// returns the number of records in the tree
	return (rectotal);
} // portfolio::howManyRec();


treeClass::treeClass() {
	ok= true;
	root= NIL; // indicates an empty list
	rectotal=0;
} // treeClass::treeClass()

treeClass::~treeClass() {			// destructor
 	deleteAllRecords ();
} // treeClass::~treeClass


void treeClass::deleteAllRecords () {
// deletes all records from the linked list
	node *thisun=root;
	recDeleteAllRecords(thisun);
	rectotal=0;
	changes.clearStack();			// removes previous changes from stack
} // treeClass::deleteAllRecords

void treeClass::recDeleteAllRecords(node *thisun){//Most likely not most efficient method, but it works.  Deletes all records by leaf
if (thisun != NIL) {//If value is found
	if(thisun->right==NIL && thisun->left==NIL){//if leaf, delete
		deleteRec(thisun->item.key);
	}
	else{//continue down tree
		recDeleteAllRecords (thisun->right);
		recDeleteAllRecords (thisun->left);
	}
	if(thisun->right==NIL && thisun->left==NIL){//after traversal, checks again to delete
		deleteRec(thisun->item.key);
	}
	} 
}



void treeClass::addRec (recType rec) {	// adds record if it does not exist
	node *newnode,          // Pointer to the new node to be added to the list
		 *current= root,    // Pointer to the current node during search
		 *previous;			// Pointer to parent of current

	newnode = new node;     // Allocate heap memory for one new node
	if (newnode==NIL) 			// Test whether memory allocation was successful
		ok= false;
	else {
		newnode->item = rec;            // Copy new name to the new node
		newnode->left= NIL;
		newnode->right= NIL;

		if (root==NIL)
			root= newnode;
		else {
			previous = NIL;                       // There is no node before the root

			// Loop until insertion spot located, or duplicate is found
			while (current!=NIL && strcmp(current->item.key, rec.key) != 0) {
				previous= current;
				if (strcmp(current->item.key, rec.key) > 0) {
					current = current->left;
				} else {
					current = current->right;
				}
			} // while

			// If a matching name is found, cancel the insertion, delete new node
			if (current!=NIL && strcmp(current->item.key, rec.key)==0) {
				delete newnode;
				ok= false;
			} else {
				if (strcmp(previous->item.key, rec.key) > 0)
					previous->left= newnode;
				else
					previous->right= newnode;
			} // inner if
		} // middle if
	} // outer if
	if (ok==true) {
		operationType operation;
		operation.lastInfo= rec;
		operation.lastChangeWas= ADD;
		changes.push(operation);
	} // if
} // treeClass::addRec

void treeClass::deleteRec (char code[keyLength]) {
// deletes record with code = key if it exists

	node *current,           // Pointer to the current node
			 *previous;         // Pointer to the previous node
	current = root;          // Set current node to the head of the list
	bool wentRight;
	recType r;

	findRec (code, r);
	if (!allOK()) {
		ok= false;
		return;
	}
	ok= true;

	// Search the tree for the code to be deleted
	previous = NIL;                       // There is no node before the root

	// Loop until record is found
	while (current!=NIL && strcmp(current->item.key, code) != 0) {
		previous= current;
		if (strcmp(current->item.key, code) > 0) {
			current = current->left;
			wentRight= false;
		} else {
			current = current->right;
			wentRight= true;
		}
	} // while

	if (current->right == NIL) {//deletion conditions
		if (previous == NIL)
			root= current->left;
		else if (wentRight)
			previous->right= current->left;
		else
			previous->left= current->left;
	} else if (current->left == NIL) {
		if (previous == NIL)
			root= current->right;
		else if (wentRight)
			previous->right= current->right;
		else
			previous->left= current->right;
	} else {
	// has 2 children
		node *tempCurr, *tempPrev;
		tempPrev= NIL;

		// move to left sub-tree
		tempCurr= current->left;

		// find largest node in left sub-tree
		while (tempCurr->right != NIL) {
			tempPrev= tempCurr;
			tempCurr= tempCurr->right;
		}

		if (previous == NIL)
			root= tempCurr;
		else if (wentRight)
			previous->right= tempCurr;
		else
			previous->left= tempCurr;
		tempCurr->right= current->right;
		if (tempPrev != NIL) {
			tempPrev->right= tempCurr->left;
			tempCurr->left= tempPrev;
		}
	} // else if

	// update for undo
	operationType operation;
	operation.lastInfo= current->item;
	operation.lastChangeWas= DELETE;
	changes.push(operation);
	
	delete current;
} // treeClass::deleteRec

void treeClass::findRec (char code[keyLength], recType &rec) {
// returns record with key = code
	node *current;
	current=root;

	// Loop until record located, or is not found
	while (current!=NIL && strcmp(current->item.key, code) != 0)
		if (strcmp(current->item.key, code) > 0)
			current = current->left;
		else
			current = current->right;

	if (current == NIL)
		ok= false;
	else {
		ok= true;
		rec= current->item;
	}
} // treeClass::findRec

void treeClass::updateRec (recType rec) {
// locates and replaces current entry with rec
	recType temp;
	operationType operation;
	findRec (rec.key, temp);
	if (ok) {
		deleteRec(rec.key);
		changes.pop(operation);
		if (ok) {
			addRec(rec);
			changes.pop(operation);
			operation.lastInfo= temp;
			operation.lastChangeWas= UPDATE;
			changes.push(operation);
		} // if
	} // outer if
} // treeClass::updateRec

void treeClass::undo() {
// undoes the most recent operation
	operationType operation;
	if (changes.pop(operation)) {
		switch (operation.lastChangeWas) {
			case ADD: deleteRec(operation.lastInfo.key); break;
			case DELETE: addRec (operation.lastInfo); break;
			case UPDATE: updateRec (operation.lastInfo); break;
			default: {
				cerr <<"Program error.  Failure in undo." <<endl;
				exit(1);
			} // default
		} // switch
		changes.pop(operation);	// remove the record on stack from undo operation
	} else
		ok= false;
} // treeClass::undo



bool treeClass::allOK () {	// returns value of ok, then resets it to true
	bool temp= ok;
	ok= true;
	return temp;
} // treeClass::allOK


void treeClass::inTraversal () {
// outputs the binary tree in 'sideways' tree form
	rectotal=0;
	inTraversalRecur (root);
	cout <<endl;
} // treeClass::inTraversal


void treeClass::inTraversalRecur(node *it) {
// private- used by inTraversal
	static int level= 0;
	int ctr;
	if (it != NIL) {
		rectotal++;
		level++;
		inTraversalRecur (it->right);
		for (ctr=1; ctr<level; ctr++)
			cout <<"\t";
		cout <<it->item.key <<endl;
		inTraversalRecur (it->left);
		level--;
	}
} // gtreeClass::inTraversalRecur

void treeClass::inLevels(){//Initializes values to track tree levels & prints them
	double averaged;
	max=0;
	min=-1;
	avg=0;
	levelcount=0;
	treeLevels(root);//calls level tracker
	averaged=((double)avg/(double)levelcount);//finds average
	if(root!=NIL){
	cout<<endl<<"Min level: "<<min<<"  Avg level: "<<averaged<<"  Max level: "<<max<<endl;//prints
	}
	else{
		cout<<endl<<"Min level: 0"<<"  Avg level: 0"<<"  Max level: 0"<<endl;
	}

}

void treeClass::treeLevels(node *it){//Prints out largest and smallest tree levels
		static int level= 0;
		
		
	int ctr;
	if (it != NIL) {
		level++;
		if(level>max){//Keeps track of max level
			max=level;
			if(it->left==NIL && it->right==NIL && min==-1){//If min isn't set yet, and at end of a branch, sets it
				min=level;
			}
		}
		else if(level<min && it->left==NIL && it->right == NIL){//If min is set and lower value is found, sets it
			min=level;
		}
		if(it->right==NIL && it->left==NIL){//Gets average
			avg+=level;
			levelcount++;
		}
		//Continue on down the tree, and decrement level to backtrack when done.
		treeLevels (it->right);
		treeLevels (it->left);
		level--;
		
}
	
}

/////////////////////////////////////
//    stack class implementation   //
/////////////////////////////////////

stack::stack() {
		head = NIL;
} // stack::stack

stack::~stack() {
	clearStack();
} // stack::~stack

void stack::clearStack() {
	node *previous;
	while (head!=NIL) {
		previous = head;
		head = head->next;
		delete previous;
	} // while
} // stack::clearStack

void stack::push(operationType value) {
    node *newnode;
    newnode = new node;
		if (newnode==NIL) {
				cerr << "out of memory in stack::push!" << endl;
        exit (1);
		}
    newnode->item = value;
    newnode->next = head;
		head = newnode;
} // stack::push

bool stack::pop(operationType &olditem) {
		node *oldnode= head;
		if (empty())
			return false;
		olditem = head->item;
		head = head->next;
    delete oldnode;
		return true;
} // stack::pop

bool stack::empty() {
	if (head==NIL)
		return true;
	else
		return false;
} // stack::empty

	 ///////////////////////////
	//  Test Driver Program //
 //////////////////////////

// prototypes
void menuResponse(char &ch);
void runMenu (treeClass &p);

int main () {
	treeClass portfolio; // a portfolio of stocks
	recType s;	// one record; holds information about 1 stock

	portfolio.inTraversal();
	portfolio.inLevels();
	runMenu (portfolio);
	
	cin.get();

	return(0);
} // main


void runMenu (treeClass &p) {
// operates a menu for the stock portfolio
	char recName[keyLength];
	char ch;
	recType s;	// one record; holds information about 1 stock
	do {
		menuResponse (ch);
		switch (ch) {
			case 'A': // add a record
				cout <<"First Name: ";
				cin >>s.key;
				cout <<"Last Name: ";
				cin >>s.lName;
				cout<<"Street Address: ";
				cin.getline(s.addString, 39);//Just picks up trash, no input even allowed.
				p.addRec (s);
				break;
			case 'D': // delete a record
				cout <<"Stock key to delete: ";
				cin >>recName;
				p.deleteRec(recName);
				break;
			case 'F': // find a record
				cout <<"Stock to find: ";
				cin >>recName;
				p.findRec (recName, s);
				cout <<s.key <<' ' <<s.lName <<endl <<s.addString<<endl;
				cout <<endl;
				break;
			case 'H': // how many record
				cout <<"There are "<<p.howManyRec() <<" stocks." <<endl;
				break;
			case 'L':	// load records from disk
				p.fetchFromDisk ("c:/temp/trash.dat");
				break;
			case 'N': // undo last add, delete, update
				p.undo();
				break;
			case 'P': // update record
				cout <<"First Name: ";
				cin >>s.key;
				cout <<"Last Name: ";
				cin >>s.lName;
				cout<<"Street Address: ";
				cin.getline(s.addString, 39);//Same problem, garbage, no input opportunity
				p.updateRec (s);
				break;
			case 'R': // removes all records
				p.deleteAllRecords ();
				break;
			case 'S':	// store all records to disk
				p.storeToDisk ("c:/temp/trash.dat");
				break;
		} // switch
		if (!p.allOK())
			cout <<"Process failed." <<endl;
		p.inTraversal();
		p.inLevels();

	} while (ch != 'Q');
} // runMenu

void menuResponse (char &ch) {
	cout
		<<endl
		<<"Choose a letter:\n"
		<<"   (A)dd a record         u(N)do last add/delete/update\n"
		<<"   (D)elete a record      u(P)date a record\n"
		<<"   (F)ind a record         (Q)uit\n"
		<<"   (H)ow many records?     (R)emove all records\n"
		<<"   (L)oad from disk        (S)tore to disk"
		<<endl;
	cin >>ch;
	ch= toupper(ch);
	//error trapping goes here
} // menuResponse

void menuResponse (char &ch) {
	cout
		<<endl
		<<"Choose a letter:\n"
		<<"   (A)dd a record         u(N)do last add/delete/update\n"
		<<"   (D)elete a record      u(P)date a record\n"
		<<"   (F)ind a record         (Q)uit\n"
		<<"   (H)ow many records?     (R)emove all records\n"
		<<"   (L)oad from disk        (S)tore to disk"
		<<endl;
	cin >>ch;
	ch= toupper(ch);
	//error trapping goes here
} // menuResponse

char menuResponse()