From 9db4e054627eb30b4e5a7333405c423df5a8d490 Mon Sep 17 00:00:00 2001 From: Adrian Kummerländer Date: Tue, 4 Mar 2014 17:02:24 +0100 Subject: Did some refactoring to improve readability * now using range for-loops during Tree printing * inroduced popNode helper method which helps to simplify the Tree construction implementation --- src/nodes.cc | 8 +-- src/nodes.h | 12 ++-- src/tree.cc | 195 +++++++++++++++++++++++++++++------------------------------ src/tree.h | 4 +- src/utils.cc | 15 ++++- src/utils.h | 6 +- 6 files changed, 123 insertions(+), 117 deletions(-) diff --git a/src/nodes.cc b/src/nodes.cc index 9ef0e6a..e75c02b 100644 --- a/src/nodes.cc +++ b/src/nodes.cc @@ -16,7 +16,7 @@ double OperandNode::solve() { return this->value_; } -NodeType OperandNode::getType() { +NodeType OperandNode::type() { return NodeType::OPERAND; } @@ -64,7 +64,7 @@ double OperatorNode::solve() { } } -NodeType OperatorNode::getType() { +NodeType OperatorNode::type() { return NodeType::OPERATOR; } @@ -91,7 +91,7 @@ std::string OperatorNode::print() { } } -TokenType OperatorNode::getToken() { +TokenType OperatorNode::token() { return this->operator_; } @@ -113,7 +113,7 @@ double ConstantNode::solve() { } } -NodeType ConstantNode::getType() { +NodeType ConstantNode::type() { return NodeType::CONSTANT; } diff --git a/src/nodes.h b/src/nodes.h index 170b88f..2581a2d 100644 --- a/src/nodes.h +++ b/src/nodes.h @@ -20,9 +20,9 @@ class Node { virtual ~Node() {}; virtual double solve() = 0; - virtual NodeType getType() = 0; + virtual NodeType type() = 0; virtual std::string print() = 0; - + Node* leftChild; Node* rightChild; }; @@ -32,10 +32,10 @@ class OperatorNode: public Node { explicit OperatorNode(TokenType); virtual double solve(); - virtual NodeType getType(); + virtual NodeType type(); virtual std::string print(); - TokenType getToken(); + TokenType token(); private: TokenType operator_; @@ -46,7 +46,7 @@ class OperandNode: public Node { explicit OperandNode(double); virtual double solve(); - virtual NodeType getType(); + virtual NodeType type(); virtual std::string print(); private: @@ -58,7 +58,7 @@ class ConstantNode: public Node { explicit ConstantNode(std::string, const ConstantMap*); virtual double solve(); - virtual NodeType getType(); + virtual NodeType type(); virtual std::string print(); private: diff --git a/src/tree.cc b/src/tree.cc index 7cc3fe8..e377c95 100644 --- a/src/tree.cc +++ b/src/tree.cc @@ -9,7 +9,7 @@ namespace SimpleParser { -Node* topNodeFrom(const std::stack& stack) { +inline Node* topNode(const std::stack& stack) { if ( !stack.empty() ) { return stack.top(); } else { @@ -17,6 +17,13 @@ Node* topNodeFrom(const std::stack& stack) { } } +inline Node* popNode(std::stack& stack) { + Node*const tmp = topNode(stack); + stack.pop(); + + return tmp; +} + Tree::Tree(std::string term): term_(term), constants_(nullptr) { @@ -38,52 +45,55 @@ std::string Tree::print() { out.precision(std::numeric_limits::digits10); out << "digraph \"" - << this->term_ - << "\"" - << std::endl; - out << "{" << std::endl; - out << "node [shape = box];" << std::endl; + << this->term_ + << "\"" + << std::endl + << "{" << std::endl + << "node [shape = box];" + << std::endl; - int i = 0; + size_t i{}; - for ( auto it = this->node_collection_.begin(); - it != this->node_collection_.end(); - ++it ) { + for ( auto&& node : this->node_collection_ ) { out << "node" - << i - << " [ label = \"" - << (*it)->print() - << "\"];" - << std::endl; - - if ( (*it)->getType() == NodeType::OPERATOR ) { - for ( auto iter = this->node_collection_.begin(); - iter != this->node_collection_.end(); - ++iter ) { - if ( (*iter).get() == (*it)->leftChild ) { + << i + << " [ label = \"" + << node->print() + << "\"];" + << std::endl; + + if ( node->type() == NodeType::OPERATOR ) { + size_t j{}; + + for ( auto&& child : this->node_collection_ ) { + if ( child.get() == node->leftChild ) { out << "\"node" - << i - << "\" -> \"node" - << (iter - this->node_collection_.begin()) - << "\";" - << std::endl; + << i + << "\" -> \"node" + << j + << "\";" + << std::endl; } - if ( (*iter).get() == (*it)->rightChild ) { + + if ( child.get() == node->rightChild ) { out << "\"node" - << i - << "\" -> \"node" - << (iter - this->node_collection_.begin()) - << "\";" - << std::endl; + << i + << "\" -> \"node" + << j + << "\";" + << std::endl; } + + ++j; } } - i++; + ++i; } - - out << "}" << std::endl; - + + out << "}" + << std::endl; + return out.str(); } @@ -101,72 +111,63 @@ Node* Tree::addNode(Node** place, Args&&... args) { } Node* Tree::buildTree(std::string term) { - std::stack operandStack; - std::stack operatorStack; - - std::vector tmpLexer; - std::vector lexerOutput = lexer(term); - - for ( auto termIter = lexerOutput.begin(); - termIter != lexerOutput.end(); - termIter++ ) { - const std::string& currTerm = (*termIter); - const TokenType token = getTokenType(currTerm[0]); - - if ( token != TokenType::VALUE_NUMBER && - token != TokenType::VALUE_IDENTIFIER && - (*termIter).size() == 1 ) { - if ( !operatorStack.empty() ) { - OperatorNode* lastNode( - static_cast(topNodeFrom(operatorStack)) + std::stack operands; + std::stack operators; + + std::vector topElements(lexer(term)); + + for ( auto elementIterator = topElements.begin(); + elementIterator != topElements.end(); + ++elementIterator ) { + const std::string& element = *elementIterator; + const TokenType elementToken = determineToken(element[0]); + + if ( elementToken != TokenType::VALUE_NUMBER && + elementToken != TokenType::VALUE_IDENTIFIER && + element.size() == 1 ) { + if ( operators.empty() ) { + operators.push( + this->addNode(nullptr, elementToken) + ); + } else { + OperatorNode*const lastNode( + static_cast(topNode(operators)) ); - if ( getPrecedence(token) > getPrecedence(lastNode->getToken()) ) { - operatorStack.push( - this->addNode(nullptr, token) + if ( precedence(elementToken) > precedence(lastNode->token()) ) { + operators.push( + this->addNode(nullptr, elementToken) ); } else { - Node* currOperator = topNodeFrom(operatorStack); - operatorStack.pop(); - - currOperator->rightChild = topNodeFrom(operandStack); - operandStack.pop(); - - currOperator->leftChild = topNodeFrom(operandStack); - operandStack.pop(); + Node*const currOperator = popNode(operators); + currOperator->rightChild = popNode(operands); + currOperator->leftChild = popNode(operands); - operandStack.push(currOperator); + operands.push(currOperator); - termIter--; + --elementIterator; } - } else { - operatorStack.push( - this->addNode(nullptr, token) - ); } } else { - tmpLexer = lexer(*termIter); + std::vector subElements(lexer(element)); - if ( tmpLexer.size() == 1 ) { - switch ( getTokenType(tmpLexer[0][0]) ) { + if ( subElements.size() == 1 ) { + switch ( determineToken(subElements[0][0]) ) { case TokenType::VALUE_NUMBER: case TokenType::OPERATOR_MINUS: { - double value; - std::istringstream convertStream(tmpLexer[0]); - convertStream >> value; - - operandStack.push( - this->addNode(nullptr, value) - ); + operands.push(this->addNode( + nullptr, + doubleToString(subElements[0]) + )); break; } case TokenType::VALUE_IDENTIFIER: { - operandStack.push( - this->addNode(nullptr, - tmpLexer[0], - this->constants_) - ); + operands.push(this->addNode( + nullptr, + subElements[0], + this->constants_ + )); break; } @@ -175,29 +176,25 @@ Node* Tree::buildTree(std::string term) { } } } else { - operandStack.push( - buildTree(*termIter) + operands.push( + buildTree(element) ); } } } - while ( !operatorStack.empty() ) { - OperatorNode *currOperator( - static_cast(topNodeFrom(operatorStack)) + while ( !operators.empty() ) { + OperatorNode*const currOperator( + static_cast(popNode(operators)) ); - operatorStack.pop(); - - currOperator->rightChild = topNodeFrom(operandStack); - operandStack.pop(); - currOperator->leftChild = topNodeFrom(operandStack); - operandStack.pop(); + currOperator->rightChild = popNode(operands); + currOperator->leftChild = popNode(operands); - operandStack.push(currOperator); + operands.push(currOperator); } - return topNodeFrom(operandStack); + return popNode(operands); } } diff --git a/src/tree.h b/src/tree.h index 31d661c..9dfc4a3 100644 --- a/src/tree.h +++ b/src/tree.h @@ -9,8 +9,6 @@ namespace SimpleParser { -typedef std::vector> NodeCollection; - class Tree { public: explicit Tree(std::string); @@ -26,7 +24,7 @@ class Tree { std::string term_; Node* root_node_; - NodeCollection node_collection_; + std::vector> node_collection_; const ConstantMap* constants_; }; diff --git a/src/utils.cc b/src/utils.cc index 9a081f3..62c3af9 100644 --- a/src/utils.cc +++ b/src/utils.cc @@ -3,10 +3,11 @@ #include "exceptions.h" #include +#include namespace SimpleParser { -TokenType getTokenType(char tmp) { +TokenType determineToken(char tmp) { if ( std::isalpha(tmp) ) { return TokenType::VALUE_IDENTIFIER; } else { @@ -33,7 +34,7 @@ TokenType getTokenType(char tmp) { } } -PrecedenceLevel getPrecedence(TokenType token) { +PrecedenceLevel precedence(TokenType token) { switch ( token ) { case TokenType::VALUE_NUMBER: case TokenType::VALUE_IDENTIFIER: { @@ -73,7 +74,7 @@ std::vector lexer(std::string term) { for ( auto termIter = term.begin(); termIter != term.end(); termIter++ ) { - token = getTokenType(*termIter); + token = determineToken(*termIter); if ( token == TokenType::VALUE_NUMBER || token == TokenType::VALUE_IDENTIFIER || @@ -160,4 +161,12 @@ std::vector lexer(std::string term) { return output; } +double doubleToString(const std::string& str) { + double value; + std::istringstream convertStream(str); + convertStream >> value; + + return value; +} + } diff --git a/src/utils.h b/src/utils.h index 0145065..ca2c77f 100644 --- a/src/utils.h +++ b/src/utils.h @@ -28,10 +28,12 @@ enum class TokenType { VALUE_IDENTIFIER, }; -TokenType getTokenType(char); -PrecedenceLevel getPrecedence(TokenType); +TokenType determineToken(char); +PrecedenceLevel precedence(TokenType); std::vector lexer(std::string); +double doubleToString(const std::string&); + } #endif // PARSER_SRC_UTILS_H_ -- cgit v1.2.3