From aca18e1803b3d54e6c9d7444e8b9c1bf09d12f52 Mon Sep 17 00:00:00 2001 From: Adrian Kummerländer Date: Sat, 19 Oct 2013 14:49:03 +0200 Subject: Fixed undefined behavior of tree construction * Invalid input syntax led to undefined behavior when accessing the top element of an empty stack ** Fixed by introducing a new "topNodeFrom" function which throws an exeption in the case that the given std::stack reference is empty --- src/parser.h | 2 +- src/tree.cc | 24 ++++++++++++++++-------- 2 files changed, 17 insertions(+), 9 deletions(-) diff --git a/src/parser.h b/src/parser.h index 54e540a..89c0493 100644 --- a/src/parser.h +++ b/src/parser.h @@ -6,7 +6,7 @@ namespace SimpleParser { double calculate(std::string); -std::string exportTree(std::string); +std::string print(std::string); } diff --git a/src/tree.cc b/src/tree.cc index 45484c6..1dcfca6 100644 --- a/src/tree.cc +++ b/src/tree.cc @@ -96,6 +96,14 @@ Node* Tree::addOperator(Node** place, char oper) { return this->node_collection_.back().get(); } +Node* topNodeFrom(const std::stack& stack) { + if ( !stack.empty() ) { + return stack.top(); + } else { + throw operator_exception(); + } +} + Node* Tree::buildTree(std::string term) { std::stack operandStack; std::stack operatorStack; @@ -114,7 +122,7 @@ Node* Tree::buildTree(std::string term) { if ( priority != -1 && (*termIter).size() == 1 ) { if ( !operatorStack.empty() ) { OperatorNode* lastNode( - static_cast(operatorStack.top()) + static_cast(topNodeFrom(operatorStack)) ); if ( getPriority(lastNode->getFunction()) < priority ) { @@ -122,13 +130,13 @@ Node* Tree::buildTree(std::string term) { this->addOperator(nullptr, currTerm[0]) ); } else { - Node* currOperator = operatorStack.top(); + Node* currOperator = topNodeFrom(operatorStack); operatorStack.pop(); - currOperator->rightChild = operandStack.top(); + currOperator->rightChild = topNodeFrom(operandStack); operandStack.pop(); - currOperator->leftChild = operandStack.top(); + currOperator->leftChild = topNodeFrom(operandStack); operandStack.pop(); operandStack.push(currOperator); @@ -161,20 +169,20 @@ Node* Tree::buildTree(std::string term) { while ( !operatorStack.empty() ) { OperatorNode *currOperator( - static_cast(operatorStack.top()) + static_cast(topNodeFrom(operatorStack)) ); operatorStack.pop(); - currOperator->rightChild = operandStack.top(); + currOperator->rightChild = topNodeFrom(operandStack); operandStack.pop(); - currOperator->leftChild = operandStack.top(); + currOperator->leftChild = topNodeFrom(operandStack); operandStack.pop(); operandStack.push(currOperator); } - return operandStack.top(); + return topNodeFrom(operandStack); } } -- cgit v1.2.3