From 64c34a42ce96c8368b8dc0636e8a452def6f8ea5 Mon Sep 17 00:00:00 2001 From: Adrian Kummerländer Date: Fri, 18 Nov 2011 21:29:51 +0100 Subject: Inital commit --- Makefile | 8 +++ main.cpp | 23 ++++++++ parser.cpp | 192 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ parser.h | 40 +++++++++++++ tree.cpp | 140 ++++++++++++++++++++++++++++++++++++++++++++ tree.h | 64 +++++++++++++++++++++ 6 files changed, 467 insertions(+) create mode 100644 Makefile create mode 100644 main.cpp create mode 100644 parser.cpp create mode 100644 parser.h create mode 100644 tree.cpp create mode 100644 tree.h 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 + +#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* Parser::lexer(string term) +{ + int priority = 0; + int last_priority = 0; + int level = 0; + string tmp, tmp_num; + + vector *output = new vector(); + + 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(*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 *operandStack = new stack(); + stack *operatorStack = new stack(); + + int priority; + Node *newNode; + + vector *tmpLexer; + + vector *lexerOutput = lexer(term); + + for ( vector::iterator termIter = lexerOutput->begin(); termIter != lexerOutput->end(); termIter++ ) { + priority = this->getPriority( (*termIter)[0] ); + + if ( priority != -1 ) { + if ( !operatorStack->empty() ) { + OperatorNode *lastNode = static_cast( 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(*termIter) ); + operandStack->push( newNode ); + } + else if ( tmpLexer->size() > 1 ) { + newNode = buildTree(tree, *termIter); + operandStack->push( newNode ); + } + } + } + + while ( !operatorStack->empty() ) { + OperatorNode *currOperator = static_cast( 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 +#include +#include +#include +#include + +#include "tree.h" + +struct ParserResult +{ + double result; + string tree; +}; + +class Parser +{ + public: + ParserResult calculate(string, bool); + + private: + int getPriority(char); + vector* 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 + +#include + +Node::Node() +{ + +} + +double Node::solve() +{ + switch (this->type) { + case OPERAND_NODE: { + OperandNode *tmp = static_cast( this ); + return tmp->solve(); + } + case OPERATOR_NODE: { + OperatorNode *tmp = static_cast( 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* 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::iterator it = this->nodeCollection->begin(); it != this->nodeCollection->end(); ++it ) { + switch ( (*it)->type ) { + case OPERAND_NODE: { + OperandNode *tmp = static_cast( *it ); + out << "node" << i << " [ label = \"" << boost::lexical_cast(tmp->value) << "\"];" << endl; + break; + } + case OPERATOR_NODE: { + OperatorNode *tmp = static_cast( *it ); + out << "node" << i << " [ label = \"" << boost::lexical_cast(tmp->function) << "\"];" << endl; + + for ( vector::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 +#include +#include + +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 *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 -- cgit v1.2.3