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/parser.cc | 217 ----------------------------------------------------------
src/parser.h | 11 ++-
src/tree.cc | 93 +++++++++++++++++++++++--
src/tree.h | 12 ++--
src/utils.cc | 115 +++++++++++++++++++++++++++++++
src/utils.h | 16 +++++
6 files changed, 232 insertions(+), 232 deletions(-)
delete mode 100644 src/parser.cc
create mode 100644 src/utils.cc
create mode 100644 src/utils.h
(limited to 'src')
diff --git a/src/parser.cc b/src/parser.cc
deleted file mode 100644
index 25ffc14..0000000
--- a/src/parser.cc
+++ /dev/null
@@ -1,217 +0,0 @@
-#include "parser.h"
-#include "exceptions.h"
-
-#include <stack>
-#include <sstream>
-
-namespace SimpleParser {
-
-double calculate(std::string term) {
- Tree termTree;
- termTree.setRoot(
- buildTree(&termTree, term)
- );
-
- return termTree.solve();
-}
-
-std::string exportTree(std::string term) {
- Tree termTree;
- termTree.setRoot(
- buildTree(&termTree, term)
- );
-
- return termTree.print(term);
-}
-
-namespace {
-
-int8_t getPriority(char tmp) {
- switch ( tmp ) {
- case '-':
- return 10;
- case '+':
- return 10;
- case '/':
- return 20;
- case '*':
- return 20;
- case '^':
- return 30;
- case '(':
- return 90;
- case ')':
- return 90;
- case ',':
- return -1;
- default:
- return -1;
- }
-}
-
-std::vector<std::string> lexer(std::string term) {
- std::string tmp;
- std::string tmpNum;
- std::vector<std::string> output;
-
- int8_t priority = 0;
- int8_t lastPriority = 0;
- uint32_t level = 0;
-
- for ( auto termIter = term.begin();
- termIter != term.end();
- termIter++ ) {
- priority = getPriority(*termIter);
-
- if ( priority == -1 || ( termIter == term.begin() &&
- priority == 10 ) ) {
- if ( level > 0 ) {
- tmp += *termIter;
- } else {
- tmpNum += *termIter;
- }
- } else {
- if ( lastPriority == -1 && level == 0 ) {
- output.push_back(tmpNum);
- tmpNum.clear();
- }
-
- switch ( *termIter ) {
- case '(': {
- if ( level > 0 ) {
- tmp += *termIter;
- }
-
- level++;
-
- break;
- }
- case ')': {
- level--;
-
- if ( level == 0 ) {
- output.push_back(tmp);
- tmp.clear();
- } else {
- tmp += *termIter;
- }
-
- break;
- }
- default: {
- if ( level == 0 ) {
- std::string helper;
- helper = *termIter;
-
- output.push_back(helper);
- } else {
- tmp += *termIter;
- }
-
- break;
- }
- }
- }
-
- lastPriority = priority;
- }
-
- if ( lastPriority == -1 ) {
- output.push_back(tmpNum);
- } else if ( lastPriority != 90 ) {
- throw operator_exception();
- }
-
- if (level != 0) {
- throw parenthese_exception();
- }
-
- if ( lastPriority == 90 && output.size() == 1 ) {
- output = lexer(output[0]);
- }
-
- return output;
-}
-
-Node* buildTree(Tree *tree, 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(
- tree->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(
- tree->addOperator(nullptr, currTerm[0])
- );
- }
- } else {
- tmpLexer = lexer(*termIter);
-
- if ( tmpLexer.size() == 1 ) {
- double value;
- std::istringstream convertStream(tmpLexer[0]);
- convertStream >> value;
-
- operandStack.push(
- tree->addOperand(nullptr,value)
- );
- } else if ( tmpLexer.size() > 1 ) {
- operandStack.push(buildTree(tree, *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();
-}
-
-}
-
-}
diff --git a/src/parser.h b/src/parser.h
index 677717a..a27d1c0 100644
--- a/src/parser.h
+++ b/src/parser.h
@@ -8,13 +8,12 @@
namespace SimpleParser {
-double calculate(std::string);
-std::string exportTree(std::string);
+double calculate(std::string term) {
+ return Tree(term).solve();
+}
-namespace {
- int8_t getPriority(char);
- std::vector<std::string> lexer(std::string);
- Node* buildTree(Tree*, std::string);
+std::string exportTree(std::string term) {
+ return Tree(term).print();
}
}
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();
+}
+
}
diff --git a/src/tree.h b/src/tree.h
index da611c7..5beec87 100644
--- a/src/tree.h
+++ b/src/tree.h
@@ -11,17 +11,19 @@ namespace SimpleParser {
class Tree {
public:
- void setRoot(Node*);
+ Tree(std::string);
+
double solve();
+ std::string print();
+ private:
Node* addOperand(Node**, double);
Node* addOperator(Node**, char);
+ Node* buildTree(std::string);
- std::string print(std::string);
-
- private:
- Node* root_node_;
std::vector<std::unique_ptr<Node>> node_collection_;
+ Node* root_node_;
+ std::string term_;
};
}
diff --git a/src/utils.cc b/src/utils.cc
new file mode 100644
index 0000000..7457ae2
--- /dev/null
+++ b/src/utils.cc
@@ -0,0 +1,115 @@
+#include "utils.h"
+#include "exceptions.h"
+
+#include "tree.h"
+
+namespace SimpleParser {
+
+int8_t getPriority(char tmp) {
+ switch ( tmp ) {
+ case '-':
+ return 10;
+ case '+':
+ return 10;
+ case '/':
+ return 20;
+ case '*':
+ return 20;
+ case '^':
+ return 30;
+ case '(':
+ return 90;
+ case ')':
+ return 90;
+ case ',':
+ return -1;
+ default:
+ return -1;
+ }
+}
+
+std::vector<std::string> lexer(std::string term) {
+ std::string tmp;
+ std::string tmpNum;
+ std::vector<std::string> output;
+
+ int8_t priority = 0;
+ int8_t lastPriority = 0;
+ uint32_t level = 0;
+
+ for ( auto termIter = term.begin();
+ termIter != term.end();
+ termIter++ ) {
+ priority = getPriority(*termIter);
+
+ if ( priority == -1 || ( termIter == term.begin() &&
+ priority == 10 ) ) {
+ if ( level > 0 ) {
+ tmp += *termIter;
+ } else {
+ tmpNum += *termIter;
+ }
+ } else {
+ if ( lastPriority == -1 && level == 0 ) {
+ output.push_back(tmpNum);
+ tmpNum.clear();
+ }
+
+ switch ( *termIter ) {
+ case '(': {
+ if ( level > 0 ) {
+ tmp += *termIter;
+ }
+
+ level++;
+
+ break;
+ }
+ case ')': {
+ level--;
+
+ if ( level == 0 ) {
+ output.push_back(tmp);
+ tmp.clear();
+ } else {
+ tmp += *termIter;
+ }
+
+ break;
+ }
+ default: {
+ if ( level == 0 ) {
+ std::string helper;
+ helper = *termIter;
+
+ output.push_back(helper);
+ } else {
+ tmp += *termIter;
+ }
+
+ break;
+ }
+ }
+ }
+
+ lastPriority = priority;
+ }
+
+ if ( lastPriority == -1 ) {
+ output.push_back(tmpNum);
+ } else if ( lastPriority != 90 ) {
+ throw operator_exception();
+ }
+
+ if (level != 0) {
+ throw parenthese_exception();
+ }
+
+ if ( lastPriority == 90 && output.size() == 1 ) {
+ output = lexer(output[0]);
+ }
+
+ return output;
+}
+
+}
diff --git a/src/utils.h b/src/utils.h
new file mode 100644
index 0000000..f71c835
--- /dev/null
+++ b/src/utils.h
@@ -0,0 +1,16 @@
+#ifndef PARSER_SRC_UTILS_H_
+#define PARSER_SRC_UTILS_H_
+
+#include <string>
+#include <vector>
+
+#include "nodes.h"
+
+namespace SimpleParser {
+
+int8_t getPriority(char);
+std::vector<std::string> lexer(std::string);
+
+}
+
+#endif // PARSER_SRC_UTILS_H_
--
cgit v1.2.3