From a0f0c005a39ddaf693c7de84d6ab1c380a93dca2 Mon Sep 17 00:00:00 2001 From: Adrian Kummerländer Date: Thu, 26 Sep 2013 20:41:37 +0200 Subject: Code restructuring of tree and parsing logic * Enabled tree to generate itself ** Main work is now done during tree construction * Moved lexer and getPriority utility functions into separate compilation unit --- Makefile | 2 +- src/parser.cc | 217 ---------------------------------------------------------- src/parser.h | 11 ++- src/tree.cc | 93 +++++++++++++++++++++++-- src/tree.h | 12 ++-- src/utils.cc | 115 +++++++++++++++++++++++++++++++ src/utils.h | 16 +++++ 7 files changed, 233 insertions(+), 233 deletions(-) delete mode 100644 src/parser.cc create mode 100644 src/utils.cc create mode 100644 src/utils.h diff --git a/Makefile b/Makefile index 4fd4faf..09fdd49 100644 --- a/Makefile +++ b/Makefile @@ -1,4 +1,4 @@ -LIB_FILES = src/nodes.cc src/tree.cc src/parser.cc +LIB_FILES = src/nodes.cc src/tree.cc src/utils.cc PROG_FILES = main.cc TEST_FILES = test.cc diff --git a/src/parser.cc b/src/parser.cc deleted file mode 100644 index 25ffc14..0000000 --- a/src/parser.cc +++ /dev/null @@ -1,217 +0,0 @@ -#include "parser.h" -#include "exceptions.h" - -#include -#include - -namespace SimpleParser { - -double calculate(std::string term) { - Tree termTree; - termTree.setRoot( - buildTree(&termTree, term) - ); - - return termTree.solve(); -} - -std::string exportTree(std::string term) { - Tree termTree; - termTree.setRoot( - buildTree(&termTree, term) - ); - - return termTree.print(term); -} - -namespace { - -int8_t 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; - } -} - -std::vector lexer(std::string term) { - std::string tmp; - std::string tmpNum; - std::vector output; - - int8_t priority = 0; - int8_t lastPriority = 0; - uint32_t level = 0; - - for ( auto termIter = term.begin(); - termIter != term.end(); - termIter++ ) { - priority = getPriority(*termIter); - - if ( priority == -1 || ( termIter == term.begin() && - priority == 10 ) ) { - if ( level > 0 ) { - tmp += *termIter; - } else { - tmpNum += *termIter; - } - } else { - if ( lastPriority == -1 && level == 0 ) { - output.push_back(tmpNum); - tmpNum.clear(); - } - - switch ( *termIter ) { - case '(': { - if ( level > 0 ) { - tmp += *termIter; - } - - level++; - - break; - } - case ')': { - level--; - - if ( level == 0 ) { - output.push_back(tmp); - tmp.clear(); - } else { - tmp += *termIter; - } - - break; - } - default: { - if ( level == 0 ) { - std::string helper; - helper = *termIter; - - output.push_back(helper); - } else { - tmp += *termIter; - } - - break; - } - } - } - - lastPriority = priority; - } - - if ( lastPriority == -1 ) { - output.push_back(tmpNum); - } else if ( lastPriority != 90 ) { - throw operator_exception(); - } - - if (level != 0) { - throw parenthese_exception(); - } - - if ( lastPriority == 90 && output.size() == 1 ) { - output = lexer(output[0]); - } - - return output; -} - -Node* buildTree(Tree *tree, std::string term) { - std::stack operandStack; - std::stack operatorStack; - - std::vector tmpLexer; - std::vector lexerOutput = lexer(term); - - int8_t priority; - - for ( auto termIter = lexerOutput.begin(); - termIter != lexerOutput.end(); - termIter++ ) { - std::string& currTerm = (*termIter); - priority = getPriority(currTerm[0]); - - if ( priority != -1 && (*termIter).size() == 1 ) { - if ( !operatorStack.empty() ) { - OperatorNode* lastNode( - static_cast(operatorStack.top()) - ); - - if ( getPriority(lastNode->getFunction()) < priority ) { - operatorStack.push( - tree->addOperator(nullptr, currTerm[0]) - ); - } else { - Node* currOperator = operatorStack.top(); - operatorStack.pop(); - - currOperator->rightChild = operandStack.top(); - operandStack.pop(); - - currOperator->leftChild = operandStack.top(); - operandStack.pop(); - - operandStack.push(currOperator); - - termIter--; - } - } else { - operatorStack.push( - tree->addOperator(nullptr, currTerm[0]) - ); - } - } else { - tmpLexer = lexer(*termIter); - - if ( tmpLexer.size() == 1 ) { - double value; - std::istringstream convertStream(tmpLexer[0]); - convertStream >> value; - - operandStack.push( - tree->addOperand(nullptr,value) - ); - } else if ( tmpLexer.size() > 1 ) { - operandStack.push(buildTree(tree, *termIter)); - } - } - } - - 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(); -} - -} - -} diff --git a/src/parser.h b/src/parser.h index 677717a..a27d1c0 100644 --- a/src/parser.h +++ b/src/parser.h @@ -8,13 +8,12 @@ namespace SimpleParser { -double calculate(std::string); -std::string exportTree(std::string); +double calculate(std::string term) { + return Tree(term).solve(); +} -namespace { - int8_t getPriority(char); - std::vector lexer(std::string); - Node* buildTree(Tree*, std::string); +std::string exportTree(std::string term) { + return Tree(term).print(); } } diff --git a/src/tree.cc b/src/tree.cc index 5c47a50..868183d 100644 --- a/src/tree.cc +++ b/src/tree.cc @@ -3,11 +3,15 @@ #include #include +#include + +#include "utils.h" namespace SimpleParser { -void Tree::setRoot(Node* root) { - this->root_node_ = root; +Tree::Tree(std::string term): + term_(term) { + this->root_node_ = this->buildTree(term); } double Tree::solve() { @@ -38,12 +42,12 @@ Node* Tree::addOperator(Node** place, char oper) { return this->node_collection_.back().get(); } -std::string Tree::print(std::string term) { +std::string Tree::print() { std::stringstream out; out.precision(std::numeric_limits::digits10); out << "digraph \"" - << term + << this->term_ << "\"" << std::endl; out << "{" << std::endl; @@ -92,4 +96,85 @@ std::string Tree::print(std::string term) { return out.str(); } +Node* Tree::buildTree(std::string term) { + std::stack operandStack; + std::stack operatorStack; + + std::vector tmpLexer; + std::vector lexerOutput = lexer(term); + + int8_t priority; + + for ( auto termIter = lexerOutput.begin(); + termIter != lexerOutput.end(); + termIter++ ) { + std::string& currTerm = (*termIter); + priority = getPriority(currTerm[0]); + + if ( priority != -1 && (*termIter).size() == 1 ) { + if ( !operatorStack.empty() ) { + OperatorNode* lastNode( + static_cast(operatorStack.top()) + ); + + if ( getPriority(lastNode->getFunction()) < priority ) { + operatorStack.push( + this->addOperator(nullptr, currTerm[0]) + ); + } else { + Node* currOperator = operatorStack.top(); + operatorStack.pop(); + + currOperator->rightChild = operandStack.top(); + operandStack.pop(); + + currOperator->leftChild = operandStack.top(); + operandStack.pop(); + + operandStack.push(currOperator); + + termIter--; + } + } else { + operatorStack.push( + this->addOperator(nullptr, currTerm[0]) + ); + } + } else { + tmpLexer = lexer(*termIter); + + if ( tmpLexer.size() == 1 ) { + double value; + std::istringstream convertStream(tmpLexer[0]); + convertStream >> value; + + operandStack.push( + this->addOperand(nullptr,value) + ); + } else if ( tmpLexer.size() > 1 ) { + operandStack.push( + buildTree(*termIter) + ); + } + } + } + + 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(); +} + } diff --git a/src/tree.h b/src/tree.h index da611c7..5beec87 100644 --- a/src/tree.h +++ b/src/tree.h @@ -11,17 +11,19 @@ namespace SimpleParser { class Tree { public: - void setRoot(Node*); + Tree(std::string); + double solve(); + std::string print(); + private: Node* addOperand(Node**, double); Node* addOperator(Node**, char); + Node* buildTree(std::string); - std::string print(std::string); - - private: - Node* root_node_; std::vector> node_collection_; + Node* root_node_; + std::string term_; }; } diff --git a/src/utils.cc b/src/utils.cc new file mode 100644 index 0000000..7457ae2 --- /dev/null +++ b/src/utils.cc @@ -0,0 +1,115 @@ +#include "utils.h" +#include "exceptions.h" + +#include "tree.h" + +namespace SimpleParser { + +int8_t 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; + } +} + +std::vector lexer(std::string term) { + std::string tmp; + std::string tmpNum; + std::vector output; + + int8_t priority = 0; + int8_t lastPriority = 0; + uint32_t level = 0; + + for ( auto termIter = term.begin(); + termIter != term.end(); + termIter++ ) { + priority = getPriority(*termIter); + + if ( priority == -1 || ( termIter == term.begin() && + priority == 10 ) ) { + if ( level > 0 ) { + tmp += *termIter; + } else { + tmpNum += *termIter; + } + } else { + if ( lastPriority == -1 && level == 0 ) { + output.push_back(tmpNum); + tmpNum.clear(); + } + + switch ( *termIter ) { + case '(': { + if ( level > 0 ) { + tmp += *termIter; + } + + level++; + + break; + } + case ')': { + level--; + + if ( level == 0 ) { + output.push_back(tmp); + tmp.clear(); + } else { + tmp += *termIter; + } + + break; + } + default: { + if ( level == 0 ) { + std::string helper; + helper = *termIter; + + output.push_back(helper); + } else { + tmp += *termIter; + } + + break; + } + } + } + + lastPriority = priority; + } + + if ( lastPriority == -1 ) { + output.push_back(tmpNum); + } else if ( lastPriority != 90 ) { + throw operator_exception(); + } + + if (level != 0) { + throw parenthese_exception(); + } + + if ( lastPriority == 90 && output.size() == 1 ) { + output = lexer(output[0]); + } + + return output; +} + +} diff --git a/src/utils.h b/src/utils.h new file mode 100644 index 0000000..f71c835 --- /dev/null +++ b/src/utils.h @@ -0,0 +1,16 @@ +#ifndef PARSER_SRC_UTILS_H_ +#define PARSER_SRC_UTILS_H_ + +#include +#include + +#include "nodes.h" + +namespace SimpleParser { + +int8_t getPriority(char); +std::vector lexer(std::string); + +} + +#endif // PARSER_SRC_UTILS_H_ -- cgit v1.2.3