aboutsummaryrefslogtreecommitdiff
path: root/src/tree.cc
diff options
context:
space:
mode:
authorAdrian Kummerlaender2014-10-02 19:59:48 +0200
committerAdrian Kummerlaender2014-10-02 19:59:48 +0200
commitab3a0312247f1467cd1eee81f6b1d22b499a8715 (patch)
tree875815935a92f75714dd301286c5dc35a30bfd96 /src/tree.cc
parent0840f434541b57fbd6d3c9d7b2a8b127cc680912 (diff)
downloadSimpleParser-ab3a0312247f1467cd1eee81f6b1d22b499a8715.tar
SimpleParser-ab3a0312247f1467cd1eee81f6b1d22b499a8715.tar.gz
SimpleParser-ab3a0312247f1467cd1eee81f6b1d22b499a8715.tar.bz2
SimpleParser-ab3a0312247f1467cd1eee81f6b1d22b499a8715.tar.xz
SimpleParser-ab3a0312247f1467cd1eee81f6b1d22b499a8715.zip
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<Node*>" 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
Diffstat (limited to 'src/tree.cc')
-rw-r--r--src/tree.cc116
1 files changed, 72 insertions, 44 deletions
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 <boost/optional.hpp>
+
#include <sstream>
#include <limits>
#include <stack>
@@ -10,19 +12,24 @@
namespace {
using SimpleParser::Node;
- inline Node* topNode(const std::stack<Node*>& stack) {
+ inline boost::optional<Node*> top(const std::stack<Node*> stack) {
if ( !stack.empty() ) {
- return stack.top();
+ return boost::make_optional<Node*>(
+ stack.top()
+ );
} else {
- throw SimpleParser::operator_exception();
+ return boost::optional<Node*>();
}
}
- inline Node* popNode(std::stack<Node*>& stack) {
- Node*const tmp = topNode(stack);
- stack.pop();
+ inline boost::optional<Node*> pop(std::stack<Node*>& stack) {
+ if ( boost::optional<Node*> 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<OperatorNode>(elementToken)
);
} else {
- OperatorNode*const lastNode(
- static_cast<OperatorNode*>(topNode(operators))
- );
-
- if ( precedence(elementToken) > precedence(lastNode->token()) ) {
- operators.push(
- this->addNode<OperatorNode>(elementToken)
- );
+ if ( boost::optional<Node*> lastNode{ top(operators) } ) {
+ OperatorNode*const lastOperator{
+ static_cast<OperatorNode*const>(*lastNode)
+ };
+
+ if ( precedence(elementToken)
+ > precedence(lastOperator->token()) ) {
+ operators.emplace(
+ this->addNode<OperatorNode>(elementToken)
+ );
+ } else {
+ boost::optional<Node*> currentOperator{ pop(operators) };
+ boost::optional<Node*> rightChild { pop(operands) };
+ boost::optional<Node*> leftChild { pop(operands) };
+
+ if ( currentOperator &&
+ rightChild &&
+ leftChild ) {
+ static_cast<OperatorNode*const>(
+ *currentOperator
+ )->setChildren(
+ *rightChild,
+ *leftChild
+ );
+
+ operands.emplace(*currentOperator);
+
+ --elementIterator;
+ } else {
+ throw operator_exception();
+ }
+ }
} else {
- OperatorNode*const currOperator(
- static_cast<OperatorNode*const>(
- 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<OperandNode>(
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<ConstantNode>(
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<OperatorNode*const>(
- popNode(operators)
- )
- );
+ boost::optional<Node*> currentOperator{ pop(operators) };
+ boost::optional<Node*> rightChild { pop(operands) };
+ boost::optional<Node*> leftChild { pop(operands) };
- currOperator->setChildren(
- popNode(operands),
- popNode(operands)
- );
+ if ( currentOperator &&
+ rightChild &&
+ leftChild ) {
+ static_cast<OperatorNode*const>(
+ *currentOperator
+ )->setChildren(
+ *rightChild,
+ *leftChild
+ );
- operands.push(currOperator);
+ operands.emplace(*currentOperator);
+ } else {
+ throw operator_exception();
+ }
}
- return popNode(operands);
+ if ( boost::optional<Node*> rootNode{ pop(operands) } ) {
+ return *rootNode;
+ } else {
+ throw operator_exception();
+ }
}
}