aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/parser.cpp190
-rw-r--r--src/parser.h36
-rw-r--r--src/tree.cpp127
-rw-r--r--src/tree.h80
4 files changed, 433 insertions, 0 deletions
diff --git a/src/parser.cpp b/src/parser.cpp
new file mode 100644
index 0000000..3aaf7e2
--- /dev/null
+++ b/src/parser.cpp
@@ -0,0 +1,190 @@
+#include "parser.h"
+
+#include <sstream>
+
+namespace SimpleParser {
+
+int8_t Parser::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> Parser::lexer(std::string term)
+{
+ std::string tmp;
+ std::string tmpNum;
+ std::string::iterator termIter;
+ std::vector<std::string> output;
+
+ int8_t priority = 0;
+ int8_t lastPriority = 0;
+ uint32_t level = 0;
+
+ for ( termIter = term.begin(); termIter != term.end(); termIter++ ) {
+ priority = this->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* Parser::buildTree(Tree *tree, std::string term) {
+ std::stack<Node*> operandStack;
+ std::stack<Node*> operatorStack;
+
+ std::vector<std::string> tmpLexer;
+ std::vector<std::string> lexerOutput = this->lexer(term);
+
+ int8_t priority;
+
+ for ( auto termIter = lexerOutput.begin(); termIter != lexerOutput.end(); termIter++ ) {
+ std::string& currTerm = (*termIter);
+ priority = this->getPriority(currTerm[0]);
+
+ if ( priority != -1 && (*termIter).size() == 1 ) {
+ if ( !operatorStack.empty() ) {
+ OperatorNode *lastNode = static_cast<OperatorNode*>(operatorStack.top());
+
+ if ( this->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 = this->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();
+}
+
+double Parser::calculate(std::string term) {
+ Tree termTree;
+ termTree.setRoot(this->buildTree(&termTree, term));
+
+ return termTree.solve();
+}
+
+}
diff --git a/src/parser.h b/src/parser.h
new file mode 100644
index 0000000..12d745a
--- /dev/null
+++ b/src/parser.h
@@ -0,0 +1,36 @@
+#ifndef PARSER_PARSER_H_
+#define PARSER_PARSER_H_
+
+#include <vector>
+#include <stack>
+#include <exception>
+
+#include "tree.h"
+
+namespace SimpleParser {
+
+class Parser {
+ public:
+ double calculate(std::string);
+
+ private:
+ int8_t getPriority(char);
+ std::vector<std::string> lexer(std::string);
+ Node* buildTree(Tree*, std::string);
+};
+
+class parenthese_exception: public std::exception {
+ virtual const char* what() const throw() {
+ return "Invalid parenthesized expression - check your input term.";
+ }
+};
+
+class operator_exception: public std::exception {
+ virtual const char* what() const throw() {
+ return "Unexpected operator placement - check your input term.";
+ }
+};
+
+}
+
+#endif // PARSER_PARSER_H_
diff --git a/src/tree.cpp b/src/tree.cpp
new file mode 100644
index 0000000..c8f0aac
--- /dev/null
+++ b/src/tree.cpp
@@ -0,0 +1,127 @@
+#include "tree.h"
+
+#include <limits>
+
+namespace SimpleParser {
+
+OperandNode::OperandNode(double val) {
+ this->value_ = val;
+}
+
+double OperandNode::solve() {
+ return this->value_;
+}
+
+NodeType OperandNode::getType() {
+ return OPERAND_NODE;
+}
+
+std::string OperandNode::print() {
+ std::stringstream convertStream;
+ convertStream.precision(std::numeric_limits<double>::digits10);
+
+ convertStream << this->value_;
+
+ return convertStream.str();
+}
+
+OperatorNode::OperatorNode(char op) {
+ this->function_ = op;
+}
+
+double OperatorNode::solve() {
+ switch ( this->function_ ) {
+ case '*':
+ return this->leftChild->solve() * this->rightChild->solve();
+ case '/': {
+ double rightChild = this->rightChild->solve();
+
+ if ( rightChild != 0 ) {
+ return this->leftChild->solve() / rightChild;
+ }
+ else {
+ throw divide_exception();
+ }
+ }
+ case '+':
+ return this->leftChild->solve() + this->rightChild->solve();
+ case '-':
+ return this->leftChild->solve() - this->rightChild->solve();
+ case '^':
+ return std::pow( this->leftChild->solve(), this->rightChild->solve() );
+ }
+}
+
+NodeType OperatorNode::getType() {
+ return OPERATOR_NODE;
+}
+
+std::string OperatorNode::print() {
+ return std::string(1, this->function_);
+}
+
+char OperatorNode::getFunction() {
+ return this->function_;
+}
+
+void Tree::setRoot(Node* root) {
+ this->root_node_ = root;
+}
+
+double Tree::solve() {
+ return this->root_node_->solve();
+}
+
+Node* Tree::addOperand(Node** place, double value) {
+ this->node_collection_.emplace_back(new OperandNode(value));
+
+ if ( place != nullptr ) {
+ *place = this->node_collection_.back().get();
+ }
+
+ return this->node_collection_.back().get();
+}
+
+Node* Tree::addOperator(Node** place, char oper) {
+ this->node_collection_.emplace_back(new OperatorNode(oper));
+
+ if ( place != nullptr ) {
+ *place = this->node_collection_.back().get();
+ }
+
+ return this->node_collection_.back().get();
+}
+
+std::string Tree::print(std::string term) {
+ std::stringstream out;
+ out.precision(std::numeric_limits<double>::digits10);
+
+ out << "digraph \"" << term << "\"" << std::endl
+ << "{" << std::endl
+ << "node [shape = box];" << std::endl;
+
+ int i = 0;
+
+ for ( auto it = this->node_collection_.begin(); it != this->node_collection_.end(); ++it ) {
+ out << "node" << i << " [ label = \"" << (*it)->print() << "\"];" << std::endl;
+
+ if ( (*it)->getType() == OPERATOR_NODE ) {
+ for ( auto iter = this->node_collection_.begin(); iter != this->node_collection_.end(); ++iter ) {
+ if ( (*iter).get() == (*it)->leftChild ) {
+ out << "\"node" << i << "\" -> \"node" << (iter - this->node_collection_.begin()) << "\";" << std::endl;
+ }
+ if ( (*iter).get() == (*it)->rightChild ) {
+ out << "\"node" << i << "\" -> \"node" << (iter - this->node_collection_.begin()) << "\";" << std::endl;
+ }
+ }
+ }
+
+ i++;
+ }
+
+ out << "}" << std::endl;
+
+ return out.str();
+}
+
+}
diff --git a/src/tree.h b/src/tree.h
new file mode 100644
index 0000000..4177098
--- /dev/null
+++ b/src/tree.h
@@ -0,0 +1,80 @@
+#ifndef PARSER_NODE_H_
+#define PARSER_NODE_H_
+
+#include <vector>
+#include <string>
+#include <sstream>
+#include <memory>
+#include <cmath>
+
+namespace SimpleParser {
+
+enum NodeType {
+ OPERAND_NODE,
+ OPERATOR_NODE,
+};
+
+class Node {
+ public:
+ virtual ~Node() {};
+
+ virtual double solve() = 0;
+ virtual NodeType getType() = 0;
+ virtual std::string print() = 0;
+
+ Node* leftChild;
+ Node* rightChild;
+};
+
+class OperatorNode: public Node {
+ public:
+ explicit OperatorNode(char);
+
+ virtual double solve();
+ virtual NodeType getType();
+ virtual std::string print();
+
+ char getFunction();
+
+ private:
+ char function_;
+};
+
+
+class OperandNode: public Node {
+ public:
+ explicit OperandNode(double);
+
+ virtual double solve();
+ virtual NodeType getType();
+ virtual std::string print();
+
+ private:
+ double value_;
+};
+
+class Tree {
+ public:
+ void setRoot(Node*);
+ double solve();
+
+ Node* addOperand(Node**, double);
+ Node* addOperator(Node**, char);
+
+ std::string print(std::string);
+
+ private:
+ Node* root_node_;
+ std::vector<std::unique_ptr<Node>> node_collection_;
+};
+
+class divide_exception: public std::exception {
+ virtual const char* what() const throw()
+ {
+ return "A divison through zero had to be prevented by the parser - check your input term.";
+ }
+};
+
+}
+
+#endif // PARSER_NODE_H_