From ab3a0312247f1467cd1eee81f6b1d22b499a8715 Mon Sep 17 00:00:00 2001 From: Adrian Kummerlaender Date: Thu, 2 Oct 2014 19:59:48 +0200 Subject: Moved exception based syntax check into buildTree * invalid expressions typically cause the operator and operand stacks to become unbalanced ** this in turn causes a operator_exception instance to be thrown as soon as the shunting yard implementation in "buildTree" tries to modify the stack _too far_ ** this is not directly visible from the tree construction implementation * the compilation unit local helper methods "pop" and "top" now return "boost::optional" instances ** this enables the operator placement errors to be handled where they occur * as a side effect children assignment is now more obvious through correctly named variables * added missing default initialization in lexer implementation --- src/tree.cc | 116 ++++++++++++++++++++++++++++++++++++----------------------- src/utils.cc | 10 +++--- 2 files changed, 77 insertions(+), 49 deletions(-) (limited to 'src') diff --git a/src/tree.cc b/src/tree.cc index 419a05c..f8c17ae 100644 --- a/src/tree.cc +++ b/src/tree.cc @@ -1,6 +1,8 @@ #include "tree.h" #include "exceptions.h" +#include + #include #include #include @@ -10,19 +12,24 @@ namespace { using SimpleParser::Node; - inline Node* topNode(const std::stack& stack) { + inline boost::optional top(const std::stack stack) { if ( !stack.empty() ) { - return stack.top(); + return boost::make_optional( + stack.top() + ); } else { - throw SimpleParser::operator_exception(); + return boost::optional(); } } - inline Node* popNode(std::stack& stack) { - Node*const tmp = topNode(stack); - stack.pop(); + inline boost::optional pop(std::stack& stack) { + if ( boost::optional node{ top(stack) } ) { + stack.pop(); - return tmp; + return node; + } else { + return node; + } } } @@ -119,33 +126,44 @@ Node* Tree::buildTree(const std::string& term) { elementToken != TokenType::VALUE_IDENTIFIER && element.size() == 1 ) { if ( operators.empty() ) { - operators.push( + operators.emplace( this->addNode(elementToken) ); } else { - OperatorNode*const lastNode( - static_cast(topNode(operators)) - ); - - if ( precedence(elementToken) > precedence(lastNode->token()) ) { - operators.push( - this->addNode(elementToken) - ); + if ( boost::optional lastNode{ top(operators) } ) { + OperatorNode*const lastOperator{ + static_cast(*lastNode) + }; + + if ( precedence(elementToken) + > precedence(lastOperator->token()) ) { + operators.emplace( + this->addNode(elementToken) + ); + } else { + boost::optional currentOperator{ pop(operators) }; + boost::optional rightChild { pop(operands) }; + boost::optional leftChild { pop(operands) }; + + if ( currentOperator && + rightChild && + leftChild ) { + static_cast( + *currentOperator + )->setChildren( + *rightChild, + *leftChild + ); + + operands.emplace(*currentOperator); + + --elementIterator; + } else { + throw operator_exception(); + } + } } else { - OperatorNode*const currOperator( - static_cast( - popNode(operators) - ) - ); - - currOperator->setChildren( - popNode(operands), - popNode(operands) - ); - - operands.push(currOperator); - - --elementIterator; + throw operator_exception(); } } } else { @@ -157,7 +175,7 @@ Node* Tree::buildTree(const std::string& term) { switch ( determineToken(subElements.front()) ) { case TokenType::VALUE_NUMBER: case TokenType::OPERATOR_MINUS: { - operands.push( + operands.emplace( this->addNode( stringToDouble(subElements.front()) ) @@ -166,7 +184,7 @@ Node* Tree::buildTree(const std::string& term) { break; } case TokenType::VALUE_IDENTIFIER: { - operands.push( + operands.emplace( this->addNode( subElements.front(), this->constants_ @@ -180,7 +198,7 @@ Node* Tree::buildTree(const std::string& term) { } } } else { - operands.push( + operands.emplace( buildTree(element) ); } @@ -188,21 +206,31 @@ Node* Tree::buildTree(const std::string& term) { } while ( !operators.empty() ) { - OperatorNode*const currOperator( - static_cast( - popNode(operators) - ) - ); + boost::optional currentOperator{ pop(operators) }; + boost::optional rightChild { pop(operands) }; + boost::optional leftChild { pop(operands) }; - currOperator->setChildren( - popNode(operands), - popNode(operands) - ); + if ( currentOperator && + rightChild && + leftChild ) { + static_cast( + *currentOperator + )->setChildren( + *rightChild, + *leftChild + ); - operands.push(currOperator); + operands.emplace(*currentOperator); + } else { + throw operator_exception(); + } } - return popNode(operands); + if ( boost::optional rootNode{ pop(operands) } ) { + return *rootNode; + } else { + throw operator_exception(); + } } } diff --git a/src/utils.cc b/src/utils.cc index 256cad8..46617d8 100644 --- a/src/utils.cc +++ b/src/utils.cc @@ -66,13 +66,13 @@ PrecedenceLevel precedence(const TokenType token) { } std::vector lexer(const std::string& term) { - std::vector resultBuffer; + std::vector resultBuffer{}; - std::string levelBuffer; - std::string numberBuffer; - std::string identifierBuffer; + std::string levelBuffer{}; + std::string numberBuffer{}; + std::string identifierBuffer{}; - TokenType previousToken; + TokenType previousToken{}; uint32_t level{0}; for ( auto&& termIter = term.begin(); -- cgit v1.2.3