diff options
author | Adrian Kummerländer | 2013-09-26 20:41:37 +0200 |
---|---|---|
committer | Adrian Kummerländer | 2013-09-26 20:41:37 +0200 |
commit | a0f0c005a39ddaf693c7de84d6ab1c380a93dca2 (patch) | |
tree | 53b6c57a9226b2cc67bd577cca169ace199483a0 /src/tree.cc | |
parent | b765b57739463d0aa3b833a70e0ea87bca68e82e (diff) | |
download | SimpleParser-a0f0c005a39ddaf693c7de84d6ab1c380a93dca2.tar SimpleParser-a0f0c005a39ddaf693c7de84d6ab1c380a93dca2.tar.gz SimpleParser-a0f0c005a39ddaf693c7de84d6ab1c380a93dca2.tar.bz2 SimpleParser-a0f0c005a39ddaf693c7de84d6ab1c380a93dca2.tar.lz SimpleParser-a0f0c005a39ddaf693c7de84d6ab1c380a93dca2.tar.xz SimpleParser-a0f0c005a39ddaf693c7de84d6ab1c380a93dca2.tar.zst SimpleParser-a0f0c005a39ddaf693c7de84d6ab1c380a93dca2.zip |
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
Diffstat (limited to 'src/tree.cc')
-rw-r--r-- | src/tree.cc | 93 |
1 files changed, 89 insertions, 4 deletions
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 <sstream> #include <limits> +#include <stack> + +#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<double>::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<Node*> operandStack; + std::stack<Node*> operatorStack; + + std::vector<std::string> tmpLexer; + std::vector<std::string> 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<OperatorNode*>(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<OperatorNode*>(operatorStack.top()) + ); + operatorStack.pop(); + + currOperator->rightChild = operandStack.top(); + operandStack.pop(); + + currOperator->leftChild = operandStack.top(); + operandStack.pop(); + + operandStack.push(currOperator); + } + + return operandStack.top(); +} + } |