From cf2aa4c9d70fc8ed658c213b2c46bb48ee10e6f7 Mon Sep 17 00:00:00 2001 From: Adrian Kummerländer Date: Sun, 20 Oct 2013 00:10:54 +0200 Subject: Implemented constant identifier functionality * SimpleParser optionally acceps a pointer to an ConstantMap containing string keys mapping to values * Constants are handled in their own ConstantNode class derived from the standard Node class * Operator precedence is now determined separated from the TokenType using a new PrecedenceLevel enum ** Conversion between tokens and their PrecedenceLevel is possible using the new utility function getPrecedence * Added additional test cases for constant identifier resolutions --- src/exceptions.h | 7 +++++++ src/nodes.cc | 18 +++++++++++++++--- src/nodes.h | 7 +++++-- src/parser.h | 5 +++++ src/tree.cc | 18 ++++++++++++++---- src/tree.h | 12 ++++++++---- src/utils.cc | 34 +++++++++++++++++++++++++++++++--- src/utils.h | 29 +++++++++++++++++++---------- test.cc | 14 ++++++++++++++ 9 files changed, 118 insertions(+), 26 deletions(-) diff --git a/src/exceptions.h b/src/exceptions.h index cd76368..b17f424 100644 --- a/src/exceptions.h +++ b/src/exceptions.h @@ -24,6 +24,13 @@ class divide_exception: public std::exception { } }; +class identifier_exception: public std::exception { + virtual const char* what() const throw() + { + return "Identifier could not be correctly resolved."; + } +}; + } #endif // PARSER_SRC_EXCEPTIONS_H_ diff --git a/src/nodes.cc b/src/nodes.cc index 1ab1502..9ef0e6a 100644 --- a/src/nodes.cc +++ b/src/nodes.cc @@ -1,5 +1,6 @@ #include "nodes.h" #include "utils.h" +#include "tree.h" #include "exceptions.h" #include @@ -94,11 +95,22 @@ TokenType OperatorNode::getToken() { return this->operator_; } -ConstantNode::ConstantNode(std::string identifier): - identifier_(identifier) { } +ConstantNode::ConstantNode(std::string identifier, + const ConstantMap* constants): + identifier_(identifier), + constants_(constants) { } double ConstantNode::solve() { - + if ( this->constants_ != nullptr ) { + try { + return this->constants_->at(this->identifier_); + } + catch ( std::out_of_range &e ) { + throw identifier_exception(); + } + } else { + throw identifier_exception(); + } } NodeType ConstantNode::getType() { diff --git a/src/nodes.h b/src/nodes.h index 6783f3d..170b88f 100644 --- a/src/nodes.h +++ b/src/nodes.h @@ -1,11 +1,13 @@ #ifndef PARSER_SRC_NODES_H_ #define PARSER_SRC_NODES_H_ +#include #include namespace SimpleParser { -enum class TokenType : int8_t; +enum class TokenType; +typedef std::map ConstantMap; enum class NodeType { OPERAND, @@ -53,7 +55,7 @@ class OperandNode: public Node { class ConstantNode: public Node { public: - explicit ConstantNode(std::string); + explicit ConstantNode(std::string, const ConstantMap*); virtual double solve(); virtual NodeType getType(); @@ -61,6 +63,7 @@ class ConstantNode: public Node { private: std::string identifier_; + const ConstantMap* constants_; }; } diff --git a/src/parser.h b/src/parser.h index 89c0493..d3cdbe1 100644 --- a/src/parser.h +++ b/src/parser.h @@ -3,10 +3,15 @@ #include +#include "tree.h" + namespace SimpleParser { double calculate(std::string); +double calculate(std::string, const ConstantMap*); + std::string print(std::string); +std::string print(std::string, const ConstantMap*); } diff --git a/src/tree.cc b/src/tree.cc index f6d2282..7cc3fe8 100644 --- a/src/tree.cc +++ b/src/tree.cc @@ -18,7 +18,14 @@ Node* topNodeFrom(const std::stack& stack) { } Tree::Tree(std::string term): - term_(term) { + term_(term), + constants_(nullptr) { + this->root_node_ = this->buildTree(term); +} + +Tree::Tree(std::string term, const ConstantMap* constants): + term_(term), + constants_(constants) { this->root_node_ = this->buildTree(term); } @@ -114,7 +121,7 @@ Node* Tree::buildTree(std::string term) { static_cast(topNodeFrom(operatorStack)) ); - if ( token > lastNode->getToken() ) { + if ( getPrecedence(token) > getPrecedence(lastNode->getToken()) ) { operatorStack.push( this->addNode(nullptr, token) ); @@ -142,7 +149,8 @@ Node* Tree::buildTree(std::string term) { if ( tmpLexer.size() == 1 ) { switch ( getTokenType(tmpLexer[0][0]) ) { - case TokenType::VALUE_NUMBER: { + case TokenType::VALUE_NUMBER: + case TokenType::OPERATOR_MINUS: { double value; std::istringstream convertStream(tmpLexer[0]); convertStream >> value; @@ -155,7 +163,9 @@ Node* Tree::buildTree(std::string term) { } case TokenType::VALUE_IDENTIFIER: { operandStack.push( - this->addNode(nullptr, tmpLexer[0]) + this->addNode(nullptr, + tmpLexer[0], + this->constants_) ); break; diff --git a/src/tree.h b/src/tree.h index 68a31c1..0db1404 100644 --- a/src/tree.h +++ b/src/tree.h @@ -1,17 +1,20 @@ #ifndef PARSER_SRC_NODE_H_ #define PARSER_SRC_NODE_H_ -#include -#include #include +#include +#include #include "nodes.h" namespace SimpleParser { +typedef std::vector> NodeCollection; + class Tree { public: Tree(std::string); + Tree(std::string, const ConstantMap*); double solve(); std::string print(); @@ -21,9 +24,10 @@ class Tree { Node* addNode(Node**, Args&&... args); Node* buildTree(std::string); - std::vector> node_collection_; - Node* root_node_; std::string term_; + Node* root_node_; + NodeCollection node_collection_; + const ConstantMap* constants_; }; } diff --git a/src/utils.cc b/src/utils.cc index 4e2ed91..9a081f3 100644 --- a/src/utils.cc +++ b/src/utils.cc @@ -12,9 +12,9 @@ TokenType getTokenType(char tmp) { } else { switch ( tmp ) { case '-': - return TokenType::OPERATOR_PLUS; - case '+': return TokenType::OPERATOR_MINUS; + case '+': + return TokenType::OPERATOR_PLUS; case '/': return TokenType::OPERATOR_DIVIDE; case '*': @@ -33,6 +33,33 @@ TokenType getTokenType(char tmp) { } } +PrecedenceLevel getPrecedence(TokenType token) { + switch ( token ) { + case TokenType::VALUE_NUMBER: + case TokenType::VALUE_IDENTIFIER: { + return PrecedenceLevel::FIRST; + } + case TokenType::OPERATOR_MINUS: + case TokenType::OPERATOR_PLUS: { + return PrecedenceLevel::SECOND; + } + case TokenType::OPERATOR_DIVIDE: + case TokenType::OPERATOR_MULTIPLY: { + return PrecedenceLevel::THIRD; + } + case TokenType::OPERATOR_POWER: { + return PrecedenceLevel::FOURTH; + } + case TokenType::PARENTHESES_OPEN: + case TokenType::PARENTHESES_CLOSE: { + return PrecedenceLevel::FIFTH; + } + default: { + return PrecedenceLevel::FIRST; + } + } +} + std::vector lexer(std::string term) { std::string tmp; std::string tmpNumber; @@ -55,7 +82,8 @@ std::vector lexer(std::string term) { if ( level > 0 ) { tmp += *termIter; } else { - if ( token == TokenType::VALUE_NUMBER ) { + if ( token == TokenType::VALUE_NUMBER || + token == TokenType::OPERATOR_MINUS ) { tmpNumber += *termIter; } else if ( token == TokenType::VALUE_IDENTIFIER ) { tmpIdentifier += *termIter; diff --git a/src/utils.h b/src/utils.h index 9727d6a..0145065 100644 --- a/src/utils.h +++ b/src/utils.h @@ -8,19 +8,28 @@ namespace SimpleParser { -enum class TokenType : int8_t { - OPERATOR_PLUS = 10, - OPERATOR_MINUS = 11, - OPERATOR_DIVIDE = 20, - OPERATOR_MULTIPLY = 21, - OPERATOR_POWER = 30, - PARENTHESES_OPEN = 90, - PARENTHESES_CLOSE = 91, - VALUE_NUMBER = -1, - VALUE_IDENTIFIER = -2, +enum class PrecedenceLevel : uint8_t { + FIRST = 1, + SECOND = 2, + THIRD = 3, + FOURTH = 4, + FIFTH = 5, +}; + +enum class TokenType { + OPERATOR_PLUS, + OPERATOR_MINUS, + OPERATOR_DIVIDE, + OPERATOR_MULTIPLY, + OPERATOR_POWER, + PARENTHESES_OPEN, + PARENTHESES_CLOSE, + VALUE_NUMBER, + VALUE_IDENTIFIER, }; TokenType getTokenType(char); +PrecedenceLevel getPrecedence(TokenType); std::vector lexer(std::string); } diff --git a/test.cc b/test.cc index 0b6f36b..8e62ab0 100644 --- a/test.cc +++ b/test.cc @@ -15,6 +15,8 @@ TEST_F(ParserTest, BasicCalc) { TEST_F(ParserTest, OperatorPriority) { EXPECT_EQ(10, SimpleParser::calculate("2+2*4")); EXPECT_EQ(4, SimpleParser::calculate("2+4/2")); + EXPECT_EQ(60, SimpleParser::calculate("100/5*3")); + EXPECT_EQ(60, SimpleParser::calculate("100*3/5")); EXPECT_EQ(42, SimpleParser::calculate("5+10*4-3")); EXPECT_EQ(17, SimpleParser::calculate("10+20/2-3")); EXPECT_EQ(261, SimpleParser::calculate("5+2^8")); @@ -31,6 +33,18 @@ TEST_F(ParserTest, BracketCalc) { EXPECT_EQ(6.25, SimpleParser::calculate("2.5*(2+3-(3/2+1))")); } +TEST_F(ParserTest, ConstantCalc) { + SimpleParser::ConstantMap constants; + constants["pi"] = 3.1415926535; + constants["answer"] = 42; + constants["g"] = 9.81; + + EXPECT_EQ(3.1415926535, SimpleParser::calculate("pi", &constants)); + EXPECT_EQ(6.283185307, SimpleParser::calculate("2*pi*1", &constants)); + EXPECT_EQ(0, SimpleParser::calculate("2*3*7-answer", &constants)); + EXPECT_EQ(1347.58, SimpleParser::calculate("1/2*(g*(-1))*answer^2+10000", &constants)); +} + int main(int argc, char **argv) { testing::InitGoogleTest(&argc, argv); -- cgit v1.2.3