From a0f0c005a39ddaf693c7de84d6ab1c380a93dca2 Mon Sep 17 00:00:00 2001
From: Adrian Kummerländer
Date: Thu, 26 Sep 2013 20:41:37 +0200
Subject: 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

---
 src/tree.cc | 93 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++---
 1 file changed, 89 insertions(+), 4 deletions(-)

(limited to 'src/tree.cc')

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();
+}
+
 }
-- 
cgit v1.2.3