http://www.hackerschool.org/HS_Boards/zboard.php?id=QNA_ETC&no=405 [º¹»ç]
Áú¹® ³»¿ë :
Áö±Ý ÀÌÁø »ê¼ú Æ®¸®¸¦ ±¸ÇöÇÏ°í Àִµ¥¿ä, ¿¡·¯°¡ ¸¹ÀÌ ¶ß³×¿ä. ¿©±â ÀÖ´Â test5.exeó·³ ³ª¿Àµµ·Ï ±¸ÇöÇÏ°í ½Í½À´Ï´Ù.
test5.cppÆÄÀÏÀº
<test5.cpp>
//--------------------------------------------------------------------
//
// Laboratory 5 test5.cpp
//
// Test program for the operations in the Expression Tree ADT
//--------------------------------------------------------------------
#include <iostream.h>
#include <stdio.h>
#include <assert.h>
#include <ctype.h> // isdigit(), toupper()
#include <process.h> // system, exit
#include <time.h> // clock(), clock_t
#include <fstream.h> // open(), close(), eof()
#include <windows.h>
const HANDLE hConsole = GetStdHandle(STD_OUTPUT_HANDLE); // Çڵ鰪
//-----------------------------------------------------
void textColor(int color_number) {
SetConsoleTextAttribute(hConsole, color_number);
}
#define etreeData char
#include "etree.h"
#include "etree.cpp"
#define empty_message "etree is empty..."
#define leftempty_message "No left subtree..."
#define rightempty_message "No right subtree..."
typedef char Message[80];
//--------------------< sleep >----------------------//
// Pauses for a specified number of milliseconds.
void sleep( clock_t wait ) {
clock_t goal;
goal = wait + clock();
while( goal > clock() )
;
}
//----------------< displayMessage>------------------//
void displayMessage (Message msg) {
cout << msg << endl ;
sleep( (clock_t)2 * CLOCKS_PER_SEC ); // delay 2 seconds
}
//--------------------< menu >-----------------------
// ¸í·É¾î¿¡ ´ëÇÑ µµ¿ò¸»À» º¸ÀδÙ.
void menu() {
system("cls");
cout << endl << "command:" << endl;
cout << " R filename : read from file => build tree" << endl;
cout << " B : keyboard input => Build etree" << endl;
cout << " - : remvoe current subtree" << endl;
cout << " =x : update current data with x" << endl;
cout << " < : goto left child" << endl;
cout << " > : goto right child" << endl;
cout << " [ : goto root" << endl;
cout << " P : goto parent node" << endl;
cout << " E : Tree empty?" << endl;
cout << " F : etreeExpression + etreeEval" << endl;
cout << " C : clear" << endl;
cout << " S : swap" << endl;
cout << " X : postfix Expression: homeWork 092" << endl;
cout << " H : height: homeWork 092" << endl;
cout << " ? : help" << endl;
cout << " Q : Quit the test program" << endl;
cout << endl;
system("pause");
system("cls");
}
//--------------------------------------------------------------------
void main()
{
char cmd; // Input command
etree T; // Test Tree
etreeData testData; // input data
char FileName[25]; // R ¸í·É¾î 󸮽ÃÀÇ ÈÀϸí
ifstream input_file; // input file stream
system("chcp 437"); system("cls"); // ¿µ¹®:437, ÇѱÛ:949
menu();
cout << endl << "Command: "; // Read command
cin >> cmd;
do
{
if ( cmd == '=' )
cin >> testData;
else if ( toupper(cmd) == 'R' )
cin >> FileName;
switch ( toupper(cmd) )
{
case 'B':
cout << endl << "Enter prefix expression : ";
T.build();
break;
case 'R' :
input_file.open(FileName, ios::nocreate, 0) ;
if ( !input_file ) {
cout << "can not open file" << endl;
exit(1);
}
else {
T.read( input_file );
input_file.close() ;
}
break;
case '-':
if ( T.empty() )
displayMessage (empty_message);
else
T.removeSubtree();
break;
case '=':
if ( T.empty() )
displayMessage (empty_message);
else
{
T.updateData(testData);
}
break;
case '[':
if ( T.empty())
displayMessage (empty_message);
else
T.gotoRoot();
break;
case '<':
if ( T.empty() )
displayMessage (empty_message);
else if ( T.leftEmpty() )
displayMessage (leftempty_message);
else
T.gotoLeft();
break;
case '>':
if ( T.empty() )
displayMessage (empty_message);
else if ( T.rightEmpty() )
displayMessage (rightempty_message);
else
T.gotoRight();
break;
case 'P':
if ( T.empty() )
displayMessage (empty_message);
else if ( T.atRoot() )
displayMessage ( "Root has no parent..." );
else
T.gotoParent();
break;
case 'E':
if ( T.empty() )
displayMessage (empty_message);
else
displayMessage ( "Tree is not empty!" );
break;
case 'F':
if ( T.empty() )
displayMessage (empty_message);
else
{
T.expression();
cout << " = " << T.evaluate() << endl << endl;
}
break;
case 'S':
if ( T.empty())
displayMessage (empty_message);
else
T.swap();
break;
case 'C':
if ( T.empty())
displayMessage (empty_message);
else
T.clear();
break;
case 'X': // °úÁ¦ 092
if ( T.empty())
displayMessage (empty_message);
else
{
T.expression();
cout << " ==> " ;
T.postfix() ;
cout << endl << endl;
}
break;
case 'H': // °úÁ¦ 092
printf("Height of Tree : %3d\n\n", T.height());
break;
case '?' : // Command Help
menu();
break;
case 'Q' : // Quit test program
exit(0);
break;
default : // Invalid command
displayMessage("invalid command.");
} // switch
cout << "\n\n\n";
T.showStructure(); // Output tree
if ( !(T.empty()) ) {
testData = T.getData();
cout << "Current node: " << testData << endl;
}
cout << endl << "Command: "; // Read command
cin >> cmd;
system("cls");
} // do
while ( toupper(cmd) != 'Q' );
}
À̰ű¸¿ä,
etree.hÆÄÀÏÀº
<etree.h>
//--------------------------------------------------------------------
//
// Laboratory 5 etree.h
//
// Class declarations for the linked implementation of the
// Expression Tree ADT -- including the recursive partners of the
// public member functions
//
//--------------------------------------------------------------------
class etree;
class etreeNode // Facilitator class for the etree class
{
private:
// Constructor
etreeNode ();
// Data members
etreeData data; // Expression tree element
etreeNode *left, // Pointer to the left child
*right; // Pointer to the right child
friend class etree;
};
typedef etreeNode *enodePtr;
//--------------------------------------------------------------------
class etree
{
public:
// Constructor
etree ();
// Destructor
~etree ();
// Expression tree manipulation functions
void build (); // Build tree from prefix expression
void read ( ifstream ); // Read in expression from file and build the tree
void expression (); // Output expression in infix form
float evaluate () ; // Evaluate expression
void clear (); // Clear tree
etreeData getData () ; // Get current node data
enodePtr getCurrent(); // Get current address
void updateData( etreeData ) ; // Update current data
void updateCurrent(enodePtr) ; // Update current address
void gotoRoot() ; // Move to root node
void gotoLeft() ; // Move to lefy child
void gotoRight() ; // Move to right child
void gotoParent ();
void removeSubtree ();
// Expression tree status function
int empty () ; // Expression tree is empty
int leftEmpty () ; // Left Subtree is empty
int rightEmpty () ; // RightSubtree is empty
int atRoot() ; // is current == root ?
// Output the tree structure -- used in testing/debugging
void showStructure () ;
void swap (); // swap all subexpr.
void postfix(); // °úÁ¦: ÈÄÀ§Ç¥±â½Ä
int height (); // °úÁ¦: Æ®¸®ÀÇ ³ôÀÌ
private:
// Recursive partners of the public member functions
enodePtr buildSub (); // ¹æ¹ý 1
//void buildSub ( enodePtr &p ); // ¹æ¹ý 2
enodePtr readSub ( ifstream );
void exprSub ( enodePtr p ) ;
float evaluateSub ( enodePtr p ) ;
void clearSub ( enodePtr p );
void showSub ( enodePtr p, int level ) ;
void swapSub ( enodePtr p );
void parentSub( enodePtr p, int *found);
void postfixSub( enodePtr p );
int heightSub( enodePtr p ); Æ®¸®ÀÇ ³ôÀÌ
// Data member
enodePtr root, // Pointer to the root node
current; // Pointer to the current node
};
À̱¸¿ä, Á¦°¡ ±¸ÇöÇÒ ºÎºÐÀº
<etree.cpp>
// linked binary tree structure¸¦ ÀÌ¿ëÇÏ¿© ÀÌÁø »ê¼úÆ®¸® ±¸Çö
//
//
#define SWAP(x, y, t) (t=x, x=y, y=t)
etreeNode:: etreeNode ( )
{}
etree:: etree ()
{
root = 0;
}
etree:: ~etree ()
{
clear();
}
void etree:: build ()
{
root = buildSub();
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
enodePtr etree:: buildSub ()
{
etreeData ch;
eNodePtr p;
cin>>ch;
p = new etreeNode();
p -> data = ch;
p -> left = 0;
p -> right = 0;
updateCurrent(p);
if(isDigit(p->data))
{
p -> left = buildSub();
p -> right = buildSub();
}
void etree:: read (ifstream input_file)
{
root = readSub( input_file );
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
enodePtr etree:: readSub ( ifstream input_file )
{
etreeData ch;
enodePtr p;
input_file>>ch;
}
void etree:: gotoRoot()
{
current = root;
}
void etree:: gotoLeft()
{
current = current -> data;
}
void etree:: gotoRight()
{
current = current -> right;
}
int etree:: empty ()
{
return (root ==0 );
}
int etree:: leftEmpty ()
{
return (current -> left == 0);
}
int etree:: rightEmpty ()
{
return (current -> right == 0);
}
int etree:: atRoot ()
{
return (root == current);
}
etreeData etree:: getData()
{
return (current -> data);
}
enodePtr etree:: getCurrent()
{
return current;
}
void etree:: updateData ( etreeData newData )
{
current -> data = newData;
}
void etree:: updateCurrent(enodePtr newPtr)
{
current = newPtr;
}
void etree:: expression ()
{
exprSub(root); //¸ðµç ³ëµå 󸮸¦ À§ÇØ
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
void etree:: exprSub ( enodePtr p )
{
if(p)
{
if(isDigit(p->data)
cout<<'c';
exprSub (p->left);
cout << p -> data;
exprSub (p-> right);
if(!isDigit(p-> data))
}
float etree:: evaluate ()
{
assert ( root != 0 ); // Æ®¸®ÀÇ °ø¹é ¿©ºÎ È®ÀÎ
return evaluateSub(root);
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
float etree:: evaluateSub ( enodePtr p )
{
float l, r,
result;
if(isDigit(p->data))
result = (float)(p->data = '0');
{
l = evaluateSub(p->data);
r = evaluateSub(p->right);
switch(p->data)
{
case'*':
result = l*r;
case'+':
result = l+r;
}
return result;
}
void etree:: clear ()
{
clearSub(root);
root = 0;
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
void etree:: clearSub ( enodePtr p )
{
if(p) // p°¡ nullÀÌ ¾Æ´Ï¸é
{
clearSub(p->left); // pÀÇ left Àç±ÍÇÔ¼ö
clearSub(p->right); // pÀÇ right Àç±ÍÇÔ¼ö
delet p;
}
void etree:: gotoParent ()
{
int found = 0;
parentSub( root, &found );
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
void etree:: parentSub( enodePtr p, int *found)
{
if(atRoot())
{
if(p-> left == current || p ->right == current)
{
*found = 2;
updateCurrent(p);
}
else
{
if(p->left)
parentSub(p->left, found);
}
}
void etree:: removeSubtree ()
{
enodePtr p;
if(atRoot())
clear();
else
{
p=getCurrent()
gotoParent();
if(current -> left == p)
currenbt-> left=0;
else
current -> right == 0;
clearSub(p);
}
void etree:: swap ()
{
swapSub(root);
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
void etree:: swapSub ( enodePtr p )
{
enodePtr temp;
if(p)
{
swapSub(p->left);
swapSub(p->right);
swapSub(p->left, p->right, temp);
}
}
void etree:: postfix()
{
postfixSub(root);
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
void etree:: postfixSub( enodePtr p )
{
}
int etree:: height ()
{
return heightSub(root);
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
int etree:: heightSub( enodePtr p )
{
int l, r, height;
if ( p == NULL )
height = 0;
else
{
l = heightSub( p->left );
r = heightSub( p->right );
if ( l > r )
height = l + 1;
else
height = r + 1;
}
return height;
}
//--------------------------------------------------------------------
void etree:: showStructure ()
{
if ( root == 0 )
cout << "Empty tree" << endl;
else
{
cout << endl;
showSub(root,1);
cout << endl;
}
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
void etree:: showSub ( enodePtr p, int level )
{
int j;
if ( p != 0 )
{
showSub(p->right,level+1); // R : Output right subtree
for ( j = 0 ; j < level ; j++ ) // level º°·Î tab Ãâ·Â
putchar ('\t');
if (p == current)
{
textColor(12); // »¡°£»ö
printf(" %c",p->data); // D
textColor(7); // Èò»ö
}
else
printf(" %c",p->data);
// ¿¬°áÀÚ Ãâ·Â
if ( ( p->left != 0 ) && ( p->right != 0 ) ) // ¾çÂÊ ÀÚ½Ä? < Ãâ·Â
putchar ('<');
else if ( p->right != 0 ) // ¿ÞÂÊ Àڽĸ¸? / Ãâ·Â
putchar ('/');
else if ( p->left != 0 ) // ¿À¸¥ÂÊ Àڽĸ¸? \ Ãâ·Â
putchar ('\\');
putchar ('\n');
showSub(p->left,level+1); // L : Output left subtree
}
}
¿©±â±îÁö ÀÔ´Ï´Ù.
¼¼°¡Áö ÆÄÀÏÀ» ÇÑ ¿öÅ© ½ºÆäÀ̽º¿¡ ³Ö°í test5.cpp·Î ÄÄÆÄÀÏ ÇÏ¸é ¿¡·¯°¡ ¸¹ÀÌ ¶ß³×¿ä.
¾à°£¾¿ »©¸ÔÀº °Ô ÀÖ´Â °Í °°Àºµ¥ ¿¡·¯°¡ Àß ¾ÈÀâÈ÷³×¿ä.
÷ºÎÆÄÀÏ¿¡ ÀÖ´Â exe ÆÄÀÏó·³ ³ª¿À·Á¸é ¾î¶»°Ô ÇؾßÇÏ´ÂÁö,,, ¾Ë·ÁÁÖ¼¼¿ä..
|
Hit : 4153 Date : 2011/10/17 11:11
|