diff options
| -rw-r--r-- | Makefile | 4 | ||||
| -rw-r--r-- | main.cpp | 10 | ||||
| -rw-r--r-- | parser.cpp | 128 | ||||
| -rw-r--r-- | parser.h | 39 | ||||
| -rw-r--r-- | test.cpp | 44 | ||||
| -rw-r--r-- | tree.cpp | 158 | ||||
| -rw-r--r-- | tree.h | 85 |
7 files changed, 214 insertions, 254 deletions
@@ -5,9 +5,9 @@ TEST_FILES = test.cpp all: parser test parser: $(PROG_FILES) $(LIB_FILES) - g++ -O2 -g -o bin/parser $(PROG_FILES) $(LIB_FILES) + g++ -std=c++11 -g -o bin/parser $(PROG_FILES) $(LIB_FILES) test: $(LIB_FILES) $(TEST_FILES) - g++ -o bin/test -lgtest $(LIB_FILES) $(TEST_FILES) + g++ -std=c++11 -O3 -o bin/test -lgtest $(LIB_FILES) $(TEST_FILES) ./bin/test @@ -4,22 +4,22 @@ int main(int argc, char *argv[]) { - string inputTerm; + std::string inputTerm; std::cin >> inputTerm; // Example: 2.5*(2+3-(3/2+1)) - Parser parser; + SimpleParser::Parser parser; try { typedef std::numeric_limits<double> dbl; std::cout.precision(dbl::digits10); - std::cout << parser.calculate(inputTerm, false).result << std::endl; + std::cout << parser.calculate(inputTerm) << std::endl; } - catch ( exception &e ) + catch ( std::exception &e ) { std::cerr << e.what() << std::endl; - exit(1); + return 1; } return 0; @@ -1,6 +1,10 @@ #include "parser.h" -int Parser::getPriority(char tmp) +#include <sstream> + +namespace SimpleParser { + +int8_t Parser::getPriority(char tmp) { switch ( tmp ) { case '-': @@ -24,32 +28,30 @@ int Parser::getPriority(char tmp) } } -vector<string> Parser::lexer(string term) +std::vector<std::string> Parser::lexer(std::string term) { - int priority = 0; - int last_priority = 0; - int level = 0; - string tmp, tmp_num; - - vector<string> output; + std::string tmp; + std::string tmpNum; + std::string::iterator termIter; + std::vector<std::string> output; - string::iterator termIter; + int8_t priority = 0; + int8_t lastPriority = 0; + uint32_t level = 0; for ( termIter = term.begin(); termIter != term.end(); termIter++ ) { - priority = this->getPriority( *termIter ); + priority = this->getPriority(*termIter); if ( priority == -1 || ( termIter == term.begin() && priority == 10 ) ) { if ( level > 0 ) { tmp += *termIter; + } else { + tmpNum += *termIter; } - else { - tmp_num += *termIter; - } - } - else { - if ( last_priority == -1 && level == 0 ) { - output.push_back( tmp_num ); - tmp_num = ""; + } else { + if ( lastPriority == -1 && level == 0 ) { + output.push_back(tmpNum); + tmpNum.clear(); } switch ( *termIter ) { @@ -65,8 +67,8 @@ vector<string> Parser::lexer(string term) level--; if ( level == 0 ) { - output.push_back( tmp ); - tmp = ""; + output.push_back(tmp); + tmp.clear(); } else { tmp += *termIter; @@ -75,10 +77,10 @@ vector<string> Parser::lexer(string term) } default: { if ( level == 0 ) { - string helper; + std::string helper; helper = *termIter; - output.push_back( helper ); + output.push_back(helper); } else { tmp += *termIter; @@ -88,13 +90,12 @@ vector<string> Parser::lexer(string term) } } - last_priority = priority; + lastPriority = priority; } - if ( last_priority == -1 ) { - output.push_back( tmp_num ); - } - else if ( last_priority != 90 ) { + if ( lastPriority == -1 ) { + output.push_back(tmpNum); + } else if ( lastPriority != 90 ) { throw operator_exception(); } @@ -102,37 +103,35 @@ vector<string> Parser::lexer(string term) throw parenthese_exception(); } - if ( last_priority == 90 && output.size() == 1 ) { + if ( lastPriority == 90 && output.size() == 1 ) { output = lexer(output[0]); } return output; } -Node* Parser::buildTree(Tree *tree, string term) -{ - stack<Node*> operandStack; - stack<Node*> operatorStack; - - int priority; +Node* Parser::buildTree(Tree *tree, std::string term) { + std::stack<Node*> operandStack; + std::stack<Node*> operatorStack; - vector<string> tmpLexer; + std::vector<std::string> tmpLexer; + std::vector<std::string> lexerOutput = this->lexer(term); - vector<string> lexerOutput = this->lexer(term); + int8_t priority; - for ( vector<string>::iterator termIter = lexerOutput.begin(); termIter != lexerOutput.end(); termIter++ ) { - priority = this->getPriority( (*termIter)[0] ); + 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() ); + OperatorNode *lastNode = static_cast<OperatorNode*>(operatorStack.top()); - if ( this->getPriority( lastNode->function ) < priority ) { + if ( this->getPriority(lastNode->getFunction()) < priority ) { operatorStack.push( - tree->addOperator( NULL, (*termIter)[0] ) + tree->addOperator(nullptr, currTerm[0]) ); - } - else { + } else { Node *currOperator = operatorStack.top(); operatorStack.pop(); @@ -146,33 +145,27 @@ Node* Parser::buildTree(Tree *tree, string term) termIter--; } + } else { + operatorStack.push(tree->addOperator(nullptr, currTerm[0])); } - else { - operatorStack.push( - tree->addOperator( NULL, (*termIter)[0] ) - ); - } - } - else { - tmpLexer = this->lexer( *termIter ); + } else { + tmpLexer = this->lexer(*termIter); if ( tmpLexer.size() == 1 ) { - operandStack.push( - tree->addOperand( NULL, - strtod( tmpLexer[0].c_str(), NULL ) - ) - ); + 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) - ); + operandStack.push(buildTree(tree, *termIter)); } } } while ( !operatorStack.empty() ) { - OperatorNode *currOperator = static_cast<OperatorNode*>( operatorStack.top() ); + OperatorNode *currOperator = static_cast<OperatorNode*>(operatorStack.top()); operatorStack.pop(); currOperator->rightChild = operandStack.top(); @@ -181,24 +174,17 @@ Node* Parser::buildTree(Tree *tree, string term) currOperator->leftChild = operandStack.top(); operandStack.pop(); - operandStack.push( currOperator ); + operandStack.push(currOperator); } return operandStack.top(); } -ParserResult Parser::calculate(string term, bool getTreeAsDot) -{ +double Parser::calculate(std::string term) { Tree termTree; termTree.root = this->buildTree(&termTree, term); - ParserResult returnVal; - - returnVal.result = termTree.root->solve(); - - if ( getTreeAsDot ) { - returnVal.tree = termTree.print(term); - } + return termTree.root->solve(); +} - return returnVal; } @@ -1,37 +1,36 @@ -#include <stdlib.h> +#ifndef PARSER_PARSER_H_ +#define PARSER_PARSER_H_ + +#include <vector> #include <stack> #include <exception> + #include "tree.h" -struct ParserResult -{ - double result; - string tree; -}; +namespace SimpleParser { -class Parser -{ +class Parser { public: - ParserResult calculate(string, bool); + double calculate(std::string); private: - int getPriority(char); - vector<string> lexer(string); - Node* buildTree(Tree*, string); + int8_t getPriority(char); + std::vector<std::string> lexer(std::string); + Node* buildTree(Tree*, std::string); }; -class parenthese_exception: public exception -{ - virtual const char* what() const throw() - { +class parenthese_exception: public std::exception { + virtual const char* what() const throw() { return "Invalid parenthesized expression - check your input term."; } }; -class operator_exception: public exception -{ - virtual const char* what() const throw() - { +class operator_exception: public std::exception { + virtual const char* what() const throw() { return "Unexpected operator placement - check your input term."; } }; + +} + +#endif // PARSER_PARSER_H_ @@ -6,35 +6,35 @@ class ParserTest : public ::testing::Test { }; TEST_F(ParserTest, BasicCalc) { - Parser p; + SimpleParser::Parser p; - EXPECT_EQ(4, p.calculate("2+2", false).result); - EXPECT_EQ(0, p.calculate("2-2", false).result); - EXPECT_EQ(42, p.calculate("21*2", false).result); - EXPECT_EQ(21, p.calculate("42/2", false).result); + EXPECT_EQ(4, p.calculate("2+2")); + EXPECT_EQ(0, p.calculate("2-2")); + EXPECT_EQ(42, p.calculate("21*2")); + EXPECT_EQ(21, p.calculate("42/2")); } TEST_F(ParserTest, OperatorPriority) { - Parser p; - - EXPECT_EQ(10, p.calculate("2+2*4", false).result); - EXPECT_EQ(4, p.calculate("2+4/2", false).result); - EXPECT_EQ(42, p.calculate("5+10*4-3", false).result); - EXPECT_EQ(17, p.calculate("10+20/2-3", false).result); - EXPECT_EQ(261, p.calculate("5+2^8", false).result); - EXPECT_EQ(32768, p.calculate("2*2^16/4", false).result); - EXPECT_EQ(32772, p.calculate("2*2^16/4+4", false).result); + SimpleParser::Parser p; + + EXPECT_EQ(10, p.calculate("2+2*4")); + EXPECT_EQ(4, p.calculate("2+4/2")); + EXPECT_EQ(42, p.calculate("5+10*4-3")); + EXPECT_EQ(17, p.calculate("10+20/2-3")); + EXPECT_EQ(261, p.calculate("5+2^8")); + EXPECT_EQ(32768, p.calculate("2*2^16/4")); + EXPECT_EQ(32772, p.calculate("2*2^16/4+4")); } TEST_F(ParserTest, BracketCalc) { - Parser p; - - EXPECT_EQ(16, p.calculate("(2+2)*4", false).result); - EXPECT_EQ(10, p.calculate("2+(2*4)", false).result); - EXPECT_EQ(10, p.calculate("(10-5)*(5-3)", false).result); - EXPECT_EQ(4, p.calculate("((((2))*((2))))", false).result); - EXPECT_EQ(37, p.calculate("(((5))*(((((3+2*2)))))+2)", false).result); - EXPECT_EQ(6.25, p.calculate("2.5*(2+3-(3/2+1))", false).result); + SimpleParser::Parser p; + + EXPECT_EQ(16, p.calculate("(2+2)*4")); + EXPECT_EQ(10, p.calculate("2+(2*4)")); + EXPECT_EQ(10, p.calculate("(10-5)*(5-3)")); + EXPECT_EQ(4, p.calculate("((((2))*((2))))")); + EXPECT_EQ(37, p.calculate("(((5))*(((((3+2*2)))))+2)")); + EXPECT_EQ(6.25, p.calculate("2.5*(2+3-(3/2+1))")); } int main(int argc, char **argv) { @@ -1,47 +1,36 @@ #include "tree.h" + #include <limits> -Node::Node() -{ +namespace SimpleParser { +OperandNode::OperandNode(double val) { + this->value_ = val; } -template <class T> -double Node::castSolve (Node *node) { - T *tmp = static_cast<T*>( node ); - return tmp->solve(); +double OperandNode::solve() { + return this->value_; } -double Node::solve() -{ - switch (this->type) { - case OPERAND_NODE: { - return this->castSolve<OperandNode>( this ); - } - case OPERATOR_NODE: { - return this->castSolve<OperatorNode>( this ); - } - } +NodeType OperandNode::getType() { + return OPERAND_NODE; } -OperandNode::OperandNode() -{ - this->type = OPERAND_NODE; -} +std::string OperandNode::print() { + std::stringstream convertStream; + convertStream.precision(std::numeric_limits<double>::digits10); -double OperandNode::solve() -{ - return this->value; + convertStream << this->value_; + + return convertStream.str(); } -OperatorNode::OperatorNode() -{ - this->type = OPERATOR_NODE; +OperatorNode::OperatorNode(char op) { + this->function_ = op; } -double OperatorNode::solve() -{ - switch (this->function) { +double OperatorNode::solve() { + switch ( this->function_ ) { case '*': return this->leftChild->solve() * this->rightChild->solve(); case '/': { @@ -59,95 +48,72 @@ double OperatorNode::solve() case '-': return this->leftChild->solve() - this->rightChild->solve(); case '^': - return pow( this->leftChild->solve(), this->rightChild->solve() ); + return std::pow( this->leftChild->solve(), this->rightChild->solve() ); } } - -Tree::Tree() -{ - this->nodeCollection = new vector<Node*>(); +NodeType OperatorNode::getType() { + return OPERATOR_NODE; } -Tree::~Tree() -{ - for ( vector<Node*>::iterator it = this->nodeCollection->begin(); it != this->nodeCollection->end(); it++ ) - { - delete *it; - } +std::string OperatorNode::print() { + return std::string(1, this->function_); +} - delete this->nodeCollection; +char OperatorNode::getFunction() { + return this->function_; } -Node* Tree::addOperand(Node **place, double value) -{ - OperandNode *newNode = new OperandNode(); - - newNode->value = value; - - this->nodeCollection->push_back( newNode ); - - if (place != NULL) { - *place = this->nodeCollection->back(); +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 newNode; + + return this->node_collection_.back().get(); } -Node* Tree::addOperator(Node **place, char oper) -{ - OperatorNode *newNode = new OperatorNode(); - - newNode->function = oper; - - this->nodeCollection->push_back( newNode ); - - if (place != NULL) { - *place = this->nodeCollection->back(); +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 newNode; + + return this->node_collection_.back().get(); } -string Tree::print(string term) -{ +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; - typedef std::numeric_limits<double> dbl; - out.precision(dbl::digits10); - - out << "digraph \"" << term << "\"" << endl << "{" << endl << "node [shape = box];" << endl; - int i = 0; - - for ( vector<Node*>::iterator it = this->nodeCollection->begin(); it != this->nodeCollection->end(); ++it ) { - switch ( (*it)->type ) { - case OPERAND_NODE: { - OperandNode *tmp = static_cast<OperandNode*>( *it ); - out << "node" << i << " [ label = \"" << tmp->value << "\"];" << endl; - break; - } - case OPERATOR_NODE: { - OperatorNode *tmp = static_cast<OperatorNode*>( *it ); - out << "node" << i << " [ label = \"" << tmp->function << "\"];" << endl; - - for ( vector<Node*>::iterator iter = this->nodeCollection->begin(); iter != this->nodeCollection->end(); ++iter ) { - if ( *iter == (*it)->leftChild ) { - out << "\"node" << i << "\" -> \"node" << (iter - this->nodeCollection->begin()) << "\";" << endl; - } - if ( *iter == (*it)->rightChild ) { - out << "\"node" << i << "\" -> \"node" << (iter - this->nodeCollection->begin()) << "\";" << endl; - } + + 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; } - - break; } } - + i++; } - out << "}" << endl; + out << "}" << std::endl; return out.str(); -}
\ No newline at end of file +} + +} @@ -1,69 +1,78 @@ +#ifndef PARSER_NODE_H_ +#define PARSER_NODE_H_ + #include <vector> #include <string> #include <sstream> -#include <math.h> +#include <memory> +#include <cmath> -using namespace std; +namespace SimpleParser { -enum NodeType -{ +enum NodeType { OPERAND_NODE, OPERATOR_NODE, }; -class Node -{ +class Node { public: - Node(); - double solve(); + virtual ~Node() {}; - template <class T> - double castSolve(Node*); + virtual double solve() = 0; + virtual NodeType getType() = 0; + virtual std::string print() = 0; - Node *leftChild; - Node *rightChild; - - NodeType type; + Node* leftChild; + Node* rightChild; }; -class OperatorNode: public Node -{ +class OperatorNode: public Node { public: - OperatorNode(); - double solve(); - char function; + explicit OperatorNode(char); + + virtual double solve(); + virtual NodeType getType(); + virtual std::string print(); + + char getFunction(); + + private: + char function_; }; -class OperandNode: public Node -{ +class OperandNode: public Node { public: - OperandNode(); - double solve(); - double value; + explicit OperandNode(double); + + virtual double solve(); + virtual NodeType getType(); + virtual std::string print(); + + private: + double value_; }; -class Tree -{ +class Tree { public: - Tree(); - ~Tree(); - - Node *root; - + Node* root; + Node* addOperand(Node**, double); Node* addOperator(Node**, char); - - string print(string); - + + std::string print(std::string); + private: - vector<Node*> *nodeCollection; + std::vector<std::unique_ptr<Node>> node_collection_; }; -class divide_exception: public exception -{ +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."; } -};
\ No newline at end of file +}; + +} + +#endif // PARSER_NODE_H_ |