Code:
//This is the header file "binary_tree.h"
//===========================/=/=/=/=/=/=/=========================//
// STRUCTURES //
//===========================/=/=/=/=/=/=/=========================//
#ifndef BINARY_TREE_H
#define BINARY_TREE_H
struct BinaryTree{ //contains the neccessary functions and data for a functioning binary expression tree
BinaryTree(); //Default constructor
//Precondition: Object has been declared with no arguments
//Postcondition: The left and right pointers have been set to NULL
~BinaryTree(); //Destructor
//Precondition: The object exists, and has been deleted by "delete"
//Postcondition: The left and right pointers' memory are sent back to the heap
char data; //node data (can be either a digit or an operator)
BinaryTree *left; //pointer to a left subtree
BinaryTree *right; //pointer to a right subtree
}; //end struct BinaryTree
#endif
Code:
//===========================/=/=/=/=/=/=/=========================//
// INCLUDES //
//===========================/=/=/=/=/=/=/=========================//
#include <iostream> //for the insertion operators, cout, and cin
#include <conio> //for the color functions and clrscr()
#include <ctype> //for the isdigit() and tolower() functions
#include <cstdlib> //for the exit() function
#include <cmath> //for the pow function
#include "binary_tree.h" //contains the struct for the binary tree
using namespace std;
//===========================/=/=/=/=/=/=/=========================//
// FUNCTION PROTOTYPES //
//===========================/=/=/=/=/=/=/=========================//
BinaryTree* buildTree(char *infix, int &pos);
//Precondition: infix has been given an infix equation string by the user, and
//pos has been given a value (to begin with, it is 1)
//Postcondition: A binary expression tree is created, returning the root from
//a fully parenthesized expression given through infix. It stores digits under
//left and right nodes, and if a parentheses is encountered, it will branch
//off into a new subtree and populate the node with data. The roots of the subtrees
//are operators, with digits (or a new operator possessing more children) for children.
void preOrderTraverse(BinaryTree *root);
//Precondition: root points to a populated binary expression tree
//Postcondition: Traverses the list recursively and outputs the prefix form of the
//infix expression
void postOrderTraverse(BinaryTree *root);
//Precondition: root points to a populated binary expression tree
//Postcondition: Traverses the list recursively and outputs the postfix
//form of the infix expression
void inOrderTraverse(BinaryTree *root);
//Precondition: root points to a populated binary expression tree
//Postcondition: Traverses the list recursively and outputs the infix
//form of the infix expression, but it will be in order (order of operations will not
//apply here since it's outputted in the order of evaluation).
double evaluate(BinaryTree *root);
//Precondition: root points to a populated binary expression tree
//Postcondition: The solution to the calculation of the data in the binary
//tree is returned recursively
bool isOperator(char ch);
//Precondition: ch has been given a value
//Postcondition: returns true if ch is either +, -, *, /, or ^
void changecolor(char* word, int color);
//precondition: word has been given a string value, and color has been given a number
//postcondition: conio function textcolor() has been called within function changecolor,
//changing the char* word into the color given by the int color.
void flushin();
//Postcondition: input buffer cleared to avoid unwanted input values
//===========================/=/=/=/=/=/=/=========================//
// IMPLEMENTATION //
//===========================/=/=/=/=/=/=/=========================//
int main(){
char infix[50], yesOrNo;
int pos; //index variable
BinaryTree *tree; //our binary tree! Everyone say hi!
do{
clrscr();
pos = 0; //to be used as the index variable for infix. 0 is the start of a string
changecolor("Binary Expression Tree\r\n\r\n", LIGHTGREEN);
cout << "Give me a <fully> parenthesized infix equation: \n";
changecolor("\r\nInfix Expression: ", WHITE);
cin.getline(infix, '\n');
cout << endl << endl;
tree = buildTree(infix, pos); //inserts infix expression into a binary tree
cout << "Prefix form of infix (preorder traversal): \n\t";
preOrderTraverse(tree);
cout << "\n\nPostfix form of infix (postorder traversal): \n\t";
postOrderTraverse(tree);
cout << "\n\nInfix form of infix (inorder traversal, read from left to right): \n\t";
inOrderTraverse(tree); //outputs infix form of infix, but from the tree! Amazing!
changecolor("\r\n\r\nEvaluation of tree: ", LIGHTBLUE);
cout << evaluate(tree); //outputs the solution to the infix equation from the tree
delete tree; //returns the memory to the heap
cout << "\n\n\nAgain? ";
do{
cin.get(yesOrNo);
}while((tolower(yesOrNo) != 'y') && (tolower(yesOrNo) != 'n')); //repeats if user doesn't enter y or n
flushin(); //clear input buffer
}while(tolower(yesOrNo) == 'y'); //continues the program as long as they say 'y'
return 0;
} //end main
/*struct BinaryTree function definitions*/
BinaryTree::BinaryTree(){
left = NULL;
right = NULL;
} //end BinaryTree default constructor
BinaryTree::~BinaryTree(){
if (left != NULL) //if the pointer is being used
delete left; //return it to the heap
if (left != NULL) //if the pointer is being used
delete right; //return it to the heap
} //end BinaryTree destructor
/*driver file function definitions*/
BinaryTree* buildTree(char *infix, int &pos){
BinaryTree *temp_root = new BinaryTree; //allocates memory
pos++; //advance one character (either a ( or a digit)
if (infix[pos] == '(') //if you encounter a parenthese
temp_root -> left = buildTree(infix, pos); //recursive call: creates a subtree to the left
else{
temp_root -> left = new BinaryTree; //allocate memory
temp_root -> left -> data = infix[pos]; //assigns data unit
}
pos++; //so we are able to get the next character of infix
temp_root -> data = infix[pos]; //assigns the operator to the root's data character
pos++; //so we are able to get the next character of infix
if (infix[pos] == '(') //if a nested parenthese arises
temp_root -> right = buildTree(infix, pos); //recursive call: creates a subtree to the right!
else{
temp_root -> right = new BinaryTree; //allocate memory
temp_root -> right -> data = infix[pos]; //assigns data unit
}
pos++; //skip over the ending ) bracket
return temp_root;
} //end buildTree()
void preOrderTraverse(BinaryTree *root){
cout << (root -> data); //output the data of the root
if (root -> left != NULL)
preOrderTraverse(root -> left); //traverse down to the left side of the tree
if (root -> right != NULL)
preOrderTraverse(root -> right); //traverse down to the right side of the tree
} //end preOrderTraverse()
void postOrderTraverse(BinaryTree *root){
if (root -> left != NULL)
postOrderTraverse(root -> left); //traverse down to the left side of the tree
if (root -> left != NULL)
postOrderTraverse(root -> right); //traverse down to the right side of the tree
cout << (root -> data); //output the data of the root
} //end postOrderTraverse()
void inOrderTraverse(BinaryTree *root){
if (root -> left != NULL)
inOrderTraverse(root -> left); //traverse down to the left side of the tree
cout << (root -> data); //output the data of the root
if (root -> left != NULL)
inOrderTraverse(root -> right); //traverse down to the right side of the tree
} //end inOrderTraverse()
double evaluate(BinaryTree *root){
double temp, divisor;
if (isdigit(root -> data)) //if the data character is a number
temp = (root -> data) - 48; //convert char to the respective int/double value (48 is the ascii offset)
if (isOperator(root -> data)){ //if the data character is an operator
switch (root -> data){ //apply the operator to the left and right values using recursive traversal
case '+':
temp = evaluate(root -> left) + evaluate(root -> right);
break;
case '-':
temp = evaluate(root -> left) - evaluate(root -> right);
break;
case '*':
temp = evaluate(root -> left) * evaluate(root -> right);
break;
case '/':
divisor = evaluate(root -> right);
if (divisor == 0){ //in math, you cannot divide by 0
cout << "\nDivide by 0 error.\n";
exit(1);
}
else //it's not 0, we can divide by it
temp = evaluate(root -> left) / divisor;
break;
case '^':
temp = pow(evaluate(root -> left), evaluate(root -> right)); //raises the first arg to the second arg
break;
default:
cout << "\nError, operator unknown\n";
break;
}
}
return temp;
} //end evaluate()
bool isOperator(char ch){
string acceptedOperators = "+-*/^";
if(acceptedOperators.find(ch, 0) != string::npos) //if ch can't be found in the string
return true;
else
return false;
} //end isOperator()
void changecolor(char* word, int color){
textcolor(color); //changes text to the color given through the argument
cprintf("%s", word); //outputs the string in the given color
textcolor(LIGHTGRAY); //change color back to the default light gray
} //end changecolor()
void flushin(){
while (cin.get() != '\n'){} //clear the input buffer
} //end flushin()
My finished code.
It works for the most part. Unfortunately, it doesn't like equations like "(((3+4)*6)/7)" even though it should. Anyone able to spot why?