aboutsummaryrefslogtreecommitdiffstatshomepage
diff options
context:
space:
mode:
authorEgor Tensin <Egor.Tensin@gmail.com>2019-12-30 13:06:13 +0300
committerEgor Tensin <Egor.Tensin@gmail.com>2019-12-31 19:43:25 +0300
commit372064af20a456989c2a9ea2fda6e535d74dbafd (patch)
tree9cc9039586252bda5ef44a68db9f53627a87ce4b
parentadd .dockerignore (diff)
downloadmath-server-372064af20a456989c2a9ea2fda6e535d74dbafd.tar.gz
math-server-372064af20a456989c2a9ea2fda6e535d74dbafd.zip
support the power (^) operator
It doesn't work with the unary minus currently (as is reflected in the tests), it should have a higher precedence.
-rw-r--r--server/lexer/token_type.cpp1
-rw-r--r--server/lexer/token_type.hpp1
-rw-r--r--server/parser/operator.hpp27
-rw-r--r--server/parser/parser.hpp12
-rw-r--r--test/unit_tests/lexer.cpp10
-rw-r--r--test/unit_tests/parser.cpp8
6 files changed, 58 insertions, 1 deletions
diff --git a/server/lexer/token_type.cpp b/server/lexer/token_type.cpp
index cafb403..6a42a3d 100644
--- a/server/lexer/token_type.cpp
+++ b/server/lexer/token_type.cpp
@@ -35,6 +35,7 @@ private:
{Type::MINUS, "-"},
{Type::ASTERISK, "*"},
{Type::SLASH, "/"},
+ {Type::CARET, "^"},
{Type::LEFT_PAREN, "("},
{Type::RIGHT_PAREN, ")"},
{Type::NUMBER, "number"},
diff --git a/server/lexer/token_type.hpp b/server/lexer/token_type.hpp
index fba2abb..2040d28 100644
--- a/server/lexer/token_type.hpp
+++ b/server/lexer/token_type.hpp
@@ -18,6 +18,7 @@ enum class Type {
MINUS,
ASTERISK,
SLASH,
+ CARET,
LEFT_PAREN,
RIGHT_PAREN,
NUMBER,
diff --git a/server/parser/operator.hpp b/server/parser/operator.hpp
index f1c24de..86b9eb1 100644
--- a/server/parser/operator.hpp
+++ b/server/parser/operator.hpp
@@ -10,6 +10,8 @@
#include "../lexer/token.hpp"
#include "../lexer/token_type.hpp"
+#include <cmath>
+
namespace math::server::parser {
class BinaryOp {
@@ -23,6 +25,7 @@ public:
case Type::MINUS:
case Type::ASTERISK:
case Type::SLASH:
+ case Type::CARET:
return true;
default:
@@ -49,25 +52,49 @@ public:
case Type::SLASH:
return min_precedence() + 1;
+ case Type::CARET:
+ return min_precedence() + 2;
+
default:
throw ParserError{"internal: undefined operator precedence"};
}
}
+ bool is_right_associative() const {
+ switch (m_type) {
+ case Type::CARET:
+ return true;
+
+ default:
+ return false;
+ }
+ }
+
+ bool is_left_associative() const {
+ return !is_right_associative();
+ }
+
double exec(double lhs, double rhs) const {
switch (m_type) {
case Type::PLUS:
return lhs + rhs;
+
case Type::MINUS:
return lhs - rhs;
+
case Type::ASTERISK:
return lhs * rhs;
+
case Type::SLASH:
// Trapping the CPU would be better?
if (rhs == 0.) {
throw ParserError{"division by zero"};
}
return lhs / rhs;
+
+ case Type::CARET:
+ return std::pow(lhs, rhs);
+
default:
throw ParserError{"internal: unsupported operator"};
}
diff --git a/server/parser/parser.hpp b/server/parser/parser.hpp
index ac87fbe..596f84f 100644
--- a/server/parser/parser.hpp
+++ b/server/parser/parser.hpp
@@ -45,7 +45,17 @@ private:
m_lexer.drop_token();
auto rhs = exec_primary();
- for (op = peek_operator(); op.has_value() && op->get_precedence() > lhs_op.get_precedence(); op = peek_operator()) {
+ for (op = peek_operator(); op.has_value(); op = peek_operator()) {
+ const auto op_prec = op->get_precedence();
+ const auto lhs_prec = lhs_op.get_precedence();
+ const auto ok_left_assoc = op->is_left_associative() && op_prec > lhs_prec;
+ const auto ok_right_assoc = op->is_right_associative() && op_prec == lhs_prec;
+ const auto ok = ok_left_assoc || ok_right_assoc;
+
+ if (!ok) {
+ break;
+ }
+
rhs = exec_expr(rhs, op->get_precedence());
}
diff --git a/test/unit_tests/lexer.cpp b/test/unit_tests/lexer.cpp
index aa4011c..0f65979 100644
--- a/test/unit_tests/lexer.cpp
+++ b/test/unit_tests/lexer.cpp
@@ -53,6 +53,7 @@ BOOST_AUTO_TEST_CASE(test_parse_const_token) {
// parse_* functions only consume a single token:
BOOST_TEST(details::parse_const_token("+/*").value() == Type::PLUS);
BOOST_TEST(details::parse_const_token("-").value() == Type::MINUS);
+ BOOST_TEST(details::parse_const_token("^^").value() == Type::CARET);
BOOST_TEST(!details::parse_const_token("&+").has_value());
}
@@ -63,6 +64,7 @@ const std::vector<std::string_view> input{
"",
" + - ",
"1+2",
+ ".5^-1 ^ 4",
"1+2 * (3- 4e-2)",
" 2 * (1 + 3 * (1 - -3)) ",
};
@@ -93,6 +95,14 @@ const std::vector<Expected> expected{
Token{2},
}},
{{
+ Token{.5},
+ Token{Type::CARET},
+ Token{Type::MINUS},
+ Token{1},
+ Token{Type::CARET},
+ Token{4},
+ }},
+ {{
Token{1},
Token{Type::PLUS},
Token{2},
diff --git a/test/unit_tests/parser.cpp b/test/unit_tests/parser.cpp
index 562c6b7..37d9e0a 100644
--- a/test/unit_tests/parser.cpp
+++ b/test/unit_tests/parser.cpp
@@ -30,6 +30,10 @@ const std::vector<std::string_view> input{
" 2 * (1 + 3) ",
" 2 * (1 + 3 * (1 - -3)) ",
" -2 * ---- (3 + -100e-1) ", // Looks weird, but also works in e.g. Python
+ "2 ^ 3 ^ 3",
+ "(2 ^ 3) ^ 3", // Power operator is right-associative
+ "(.5 ^ -1) ^ 4",
+ ".5 ^ -1 ^ 4", // Power operator has higher precedence than the unary minus
};
const std::vector<double> expected{
@@ -39,6 +43,10 @@ const std::vector<double> expected{
8,
26,
14,
+ 134217728,
+ 512,
+ 16,
+ 2,
};
}