Inital commit

6 files changed, 467 insertions, 0 deletions

diff --git a/Makefile b/Makefile
new file mode 100644
index 0000000..7d9d894
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,8 @@
+LIB_FILES = tree.cpp parser.cpp
+PROG_FILES = main.cpp
+
+all: parser
+
+parser:	$(PROG_FILES) $(LIB_FILES)
+	g++ -g -o parser $(PROG_FILES) $(LIB_FILES) 
+
diff --git a/main.cpp b/main.cpp
new file mode 100644
index 0000000..2bc682a
--- /dev/null
+++ b/main.cpp
@@ -0,0 +1,23 @@
+#include <iostream>
+
+#include "parser.h"
+
+int main(int argc, char *argv[])
+{
+	string inputTerm;
+	
+	std::cin >> inputTerm; // Example: 2.5*(2+3-(3/2+1))
+	
+	Parser *parser = new Parser();
+	
+	try {
+		std::cout << parser->calculate(inputTerm, false).result << std::endl;
+	}
+	catch ( exception &e )
+	{
+		std::cerr << e.what() << std::endl;
+		std::exit(1);
+	}
+
+	return 0;
+}
diff --git a/parser.cpp b/parser.cpp
new file mode 100644
index 0000000..47516b3
--- /dev/null
+++ b/parser.cpp
@@ -0,0 +1,192 @@
+#include "parser.h"
+
+int Parser::getPriority(char tmp)
+{
+	switch ( tmp ) {
+		case '-':
+			return 10;
+		case '+':
+			return 10;
+		case '/':
+			return 20;
+		case '*':
+			return 20;
+		case '^':
+			return 30;
+		case '(':
+			return 90;
+		case ')':
+			return 90;	
+		case ',':
+			return -1;
+		default:
+			return -1;
+	}
+}
+
+vector<string>* Parser::lexer(string term)
+{
+	int priority = 0;
+	int last_priority = 0;
+	int level = 0;
+	string tmp, tmp_num;
+	
+	vector<string> *output = new vector<string>();
+	
+	string::iterator termIter;
+	
+	for ( termIter = term.begin(); termIter != term.end(); termIter++ ) {
+		priority = this->getPriority( *termIter );
+		
+		if ( priority == -1 ) {
+			if ( level > 0 ) {
+				tmp += *termIter;
+			}
+			else {
+				tmp_num += *termIter;
+			}
+		}
+		else {
+			if ( last_priority == -1 && level == 0 ) {
+				output->push_back( tmp_num );
+				tmp_num = "";
+			}
+			
+			switch ( *termIter ) {
+				case '(': {
+					if ( level > 0 ) {
+						tmp += *termIter;
+					}
+					
+					level++;
+					break;
+				}
+				case ')': {
+					level--;
+					
+					if ( level == 0 ) {
+						output->push_back( tmp );
+						tmp = "";
+					}
+					else {
+						tmp += *termIter;
+					}
+					break;
+				}
+				default: {				
+					if ( level == 0 ) {
+						output->push_back( boost::lexical_cast<string>(*termIter) );
+					}
+					else {
+						tmp += *termIter;
+					}
+					break;
+				}
+			}
+		}
+		
+		last_priority = priority;	
+	}
+	
+	if ( last_priority == -1 ) {
+		output->push_back( tmp_num );
+	}
+	else if ( last_priority != 90 ) {
+		throw operator_exception();
+	}
+	
+	if (level != 0) {
+		throw parenthese_exception();
+	}
+	
+	return output;
+}
+
+Node* Parser::buildTree(Tree **tree, string term)
+{
+	stack<Node*> *operandStack = new stack<Node*>();
+	stack<Node*> *operatorStack = new stack<Node*>();
+	
+	int priority;
+	Node *newNode;
+	
+	vector<string> *tmpLexer;
+	
+	vector<string> *lexerOutput = lexer(term);
+	
+	for ( vector<string>::iterator termIter = lexerOutput->begin(); termIter != lexerOutput->end(); termIter++ ) {
+		priority = this->getPriority( (*termIter)[0] );
+		
+		if ( priority != -1 ) {
+			if ( !operatorStack->empty() ) {
+				OperatorNode *lastNode = static_cast<OperatorNode*>( operatorStack->top() );
+			
+				if ( this->getPriority( lastNode->function ) < priority ) {
+					newNode = (*tree)->addOperator( NULL, (*termIter)[0] );
+					operatorStack->push( newNode );
+				}
+				else {
+					Node *currOperator = operatorStack->top();
+					operatorStack->pop();
+					
+					currOperator->rightChild = operandStack->top();
+					operandStack->pop();
+					
+					currOperator->leftChild = operandStack->top();
+					operandStack->pop();
+					
+					operandStack->push( currOperator );
+					
+					termIter--;
+				}
+			}
+			else {
+				newNode = (*tree)->addOperator( NULL, (*termIter)[0] );
+				operatorStack->push( newNode );
+			}
+		}
+		else {
+			tmpLexer = lexer( *termIter );
+			
+			if ( tmpLexer->size() == 1 ) {
+				newNode = (*tree)->addOperand( NULL, boost::lexical_cast<double>(*termIter) );
+				operandStack->push( newNode );
+			}
+			else if ( tmpLexer->size() > 1 ) {
+				newNode = buildTree(tree, *termIter);
+				operandStack->push( newNode );
+			}
+		}
+	}
+	
+	while ( !operatorStack->empty() ) {
+		OperatorNode *currOperator = static_cast<OperatorNode*>( operatorStack->top() );
+		operatorStack->pop();
+					
+		currOperator->rightChild = operandStack->top();
+		operandStack->pop();
+					
+		currOperator->leftChild = operandStack->top();
+		operandStack->pop();
+				
+		operandStack->push( currOperator );
+	}
+	
+	return operandStack->top();
+}
+
+ParserResult Parser::calculate(string term, bool getTreeAsDot)
+{
+	Tree *termTree = new Tree();
+	termTree->root = buildTree(&termTree, term);
+	
+	ParserResult returnVal;
+	
+	returnVal.result = termTree->root->solve();
+	
+	if ( getTreeAsDot ) {
+		returnVal.tree = termTree->print(term);
+	}
+	
+	return returnVal;
+}
diff --git a/parser.h b/parser.h
new file mode 100644
index 0000000..e4299dc
--- /dev/null
+++ b/parser.h
@@ -0,0 +1,40 @@
+#include <stack>
+#include <string>
+#include <sstream>
+#include <exception>
+#include <boost/lexical_cast.hpp>
+
+#include "tree.h"
+
+struct ParserResult 
+{
+	double result;
+	string tree;	
+};
+
+class Parser
+{
+	public:
+		ParserResult calculate(string, bool);
+	
+	private:
+	 	int getPriority(char);
+	 	vector<string>* lexer(string);
+	 	Node* buildTree(Tree**, string);
+};
+
+class parenthese_exception: public exception
+{
+	virtual const char* what() const throw()
+	{
+		return "Invalid parenthesized expression - check your input term.";
+	}
+};
+
+class operator_exception: public exception
+{
+	virtual const char* what() const throw()
+	{
+		return "Unexpected operator placement - check your input term.";
+	}
+};
diff --git a/tree.cpp b/tree.cpp
new file mode 100644
index 0000000..3a44833
--- /dev/null
+++ b/tree.cpp
@@ -0,0 +1,140 @@
+#include "tree.h"
+#include <math.h>
+
+#include <boost/lexical_cast.hpp>
+
+Node::Node()
+{
+
+}
+
+double Node::solve()
+{
+	switch (this->type) {
+		case OPERAND_NODE: {
+			OperandNode *tmp = static_cast<OperandNode*>( this );
+			return tmp->solve();
+		}
+		case OPERATOR_NODE: {
+			OperatorNode *tmp = static_cast<OperatorNode*>( this );
+			return tmp->solve();
+		}
+	}
+}
+
+OperandNode::OperandNode()
+{
+	this->type = OPERAND_NODE;
+}
+
+double OperandNode::solve()
+{
+	return this->value;
+}
+
+OperatorNode::OperatorNode()
+{
+	this->type = OPERATOR_NODE;
+}
+
+double OperatorNode::solve()
+{
+	switch (this->function) {
+		case '*':
+			return this->leftChild->solve() * this->rightChild->solve();
+		case '/': {
+			double rightChild = this->rightChild->solve();
+			
+			if ( rightChild != 0 ) {
+				return this->leftChild->solve() / rightChild;
+			}
+			else {
+				throw divide_exception();
+			}
+		}
+		case '+':
+			return this->leftChild->solve() + this->rightChild->solve();
+		case '-':
+			return this->leftChild->solve() - this->rightChild->solve();
+		case '^':
+			return pow( this->leftChild->solve(), this->rightChild->solve() );
+	}
+}
+
+
+Tree::Tree()
+{
+	this->nodeCollection = new vector<Node*>();
+}
+
+Node* Tree::addOperand(Node **place, double value)
+{
+	OperandNode *newNode = new OperandNode();
+	
+	newNode = new OperandNode();
+	newNode->value = value;
+	
+	this->nodeCollection->push_back( newNode ); 
+	
+	if (place != NULL) {
+		*place = this->nodeCollection->back();
+	}
+	
+	return newNode;
+}
+
+Node* Tree::addOperator(Node **place, char oper)
+{	
+	OperatorNode *newNode = new OperatorNode();
+	
+	newNode = new OperatorNode();
+	newNode->function = oper;
+	
+	this->nodeCollection->push_back( newNode ); 
+	
+	if (place != NULL) {
+		*place = this->nodeCollection->back();
+	}
+	
+	return newNode;
+}
+
+string Tree::print(string term)
+{
+	std::stringstream out;
+	
+	out << "digraph \"" << term << "\"" << endl << "{" << endl << "node [shape = box];" << endl;
+	
+	int i = 0;
+	
+	for ( vector<Node*>::iterator it = this->nodeCollection->begin(); it != this->nodeCollection->end(); ++it ) {
+    	switch ( (*it)->type ) {
+			case OPERAND_NODE: {
+				OperandNode *tmp = static_cast<OperandNode*>( *it );
+				out << "node" << i << " [ label = \"" << boost::lexical_cast<string>(tmp->value) << "\"];" << endl;
+				break;
+			}
+			case OPERATOR_NODE: {
+				OperatorNode *tmp = static_cast<OperatorNode*>( *it );
+				out << "node" << i << " [ label = \"" << boost::lexical_cast<string>(tmp->function) << "\"];" << endl;
+				
+				for ( vector<Node*>::iterator iter = this->nodeCollection->begin(); iter != this->nodeCollection->end(); ++iter ) {
+					if ( *iter == (*it)->leftChild ) {
+						out << "\"node" << i << "\" -> \"node" << (iter - this->nodeCollection->begin()) << "\";" << endl;
+					}
+					if ( *iter == (*it)->rightChild ) {
+						out << "\"node" << i << "\" -> \"node" << (iter - this->nodeCollection->begin()) << "\";" << endl;
+					}
+				}
+				
+				break;
+			}
+		}
+		
+		i++;
+	}
+	
+	out << "}" << endl;
+	
+	return out.str();
+}
\ No newline at end of file
diff --git a/tree.h b/tree.h
new file mode 100644
index 0000000..48f4de1
--- /dev/null
+++ b/tree.h
@@ -0,0 +1,64 @@
+#include <vector>
+#include <string>
+#include <stdlib.h>
+
+using namespace std;
+
+enum NodeType 
+{
+	OPERAND_NODE,
+	OPERATOR_NODE,
+};
+
+class Node
+{
+	public:
+		Node();
+		double solve();
+		
+		Node *leftChild;
+		Node *rightChild;
+
+		NodeType type;		
+};
+
+class OperatorNode: public Node 
+{
+	public:
+		OperatorNode();
+		double solve();
+		char function;
+};
+
+
+class OperandNode: public Node
+{
+	public:
+		OperandNode();
+		double solve();
+		double value;
+};
+
+class Tree
+{
+	public:
+		Tree();
+		
+		Node *root;
+		
+		Node* addOperand(Node**, double);
+		Node* addOperator(Node**, char);
+		
+		string print(string);
+		
+	private:
+		vector<Node*> *nodeCollection;
+};
+
+class divide_exception: public exception
+{
+	virtual const char* what() const throw()
+	{
+		return "A divison through zero had to be prevented by the parser - check your input term.";
+	}
+};
\ No newline at end of file