aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--Makefile4
-rw-r--r--main.cpp10
-rw-r--r--parser.cpp128
-rw-r--r--parser.h39
-rw-r--r--test.cpp44
-rw-r--r--tree.cpp158
-rw-r--r--tree.h85
7 files changed, 214 insertions, 254 deletions
diff --git a/Makefile b/Makefile
index ac857b2..bfc1768 100644
--- a/Makefile
+++ b/Makefile
@@ -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
diff --git a/main.cpp b/main.cpp
index d12119e..33788ae 100644
--- a/main.cpp
+++ b/main.cpp
@@ -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;
diff --git a/parser.cpp b/parser.cpp
index 0378a3f..683d26f 100644
--- a/parser.cpp
+++ b/parser.cpp
@@ -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;
}
diff --git a/parser.h b/parser.h
index e9cdde1..12d745a 100644
--- a/parser.h
+++ b/parser.h
@@ -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_
diff --git a/test.cpp b/test.cpp
index 2d0ef10..04837ee 100644
--- a/test.cpp
+++ b/test.cpp
@@ -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) {
diff --git a/tree.cpp b/tree.cpp
index 29dbab1..2fd5deb 100644
--- a/tree.cpp
+++ b/tree.cpp
@@ -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
+}
+
+}
diff --git a/tree.h b/tree.h
index f2a7017..4527095 100644
--- a/tree.h
+++ b/tree.h
@@ -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_