From e3081360c65eb4994e7e8042898cec72de0d560b Mon Sep 17 00:00:00 2001 From: Adrian Kummerländer Date: Sat, 5 Jan 2013 22:04:23 +0100 Subject: Folder structure change; Further improvements of parser code --- src/parser.cpp | 190 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/parser.h | 36 +++++++++++ src/tree.cpp | 127 ++++++++++++++++++++++++++++++++++++++ src/tree.h | 80 ++++++++++++++++++++++++ 4 files changed, 433 insertions(+) create mode 100644 src/parser.cpp create mode 100644 src/parser.h create mode 100644 src/tree.cpp create mode 100644 src/tree.h (limited to 'src') 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 + +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 Parser::lexer(std::string term) +{ + std::string tmp; + std::string tmpNum; + std::string::iterator termIter; + std::vector 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 operandStack; + std::stack operatorStack; + + std::vector tmpLexer; + std::vector 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(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(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 +#include +#include + +#include "tree.h" + +namespace SimpleParser { + +class Parser { + public: + double calculate(std::string); + + private: + int8_t getPriority(char); + std::vector 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 + +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::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::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 +#include +#include +#include +#include + +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> 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_ -- cgit v1.2.3