expression_parser.hpp¶
Parse identifiers, integers, parentheses, configurable binary operators, and configurable prefix unary operators into an expression tree.
解析并计算带括号和运算符优先级的表达式；适合题目要求实现算术语法或把字符串转为表达式树。
Implementation¶
#ifndef NOYA_EXPRESSION_PARSER_HPP
#define NOYA_EXPRESSION_PARSER_HPP 1
/// @complexity Time: O(t log o) for t tokens and ordered operator tables.
/// Space: O(t) parse stacks/output.
#include <algorithm>
#include <cctype>
#include <cstddef>
#include <optional>
#include <string>
#include <string_view>
#include <utility>
#include <vector>
namespace noya {
struct expression_binary_operator {
std::string symbol;
int precedence = 0;
bool right_associative = false;
};
struct expression_unary_operator {
std::string symbol;
int precedence = 0;
};
struct expression_node {
enum class kind { operand, unary, binary } type = kind::operand;
std::string token;
int left = -1;
int right = -1;
};
struct expression_tree {
std::vector<expression_node> nodes;
int root = -1;
};
struct expression_parse_error {
std::size_t position = 0;
std::string message;
};
struct expression_parse_result {
std::optional<expression_tree> tree;
std::optional<expression_parse_error> error;
explicit operator bool() const { return tree.has_value(); }
};
/// @brief Parse identifiers, integers, parentheses, configurable binary
/// operators, and configurable prefix unary operators into an expression tree.
inline expression_parse_result parse_expression(
std::string_view expression,
const std::vector<expression_binary_operator> &binary_operators,
const std::vector<expression_unary_operator> &unary_operators = {}) {
struct token {
enum class kind { operand, operation, left_parenthesis, right_parenthesis,
end } type = kind::end;
std::string text;
std::size_t position = 0;
};
std::vector<std::string> symbols;
for (const auto &operation : binary_operators) {
if (operation.symbol.empty() || operation.precedence < 0) {
return {{}, expression_parse_error{0, "invalid binary operator table"}};
}
symbols.push_back(operation.symbol);
}
for (const auto &operation : unary_operators) {
if (operation.symbol.empty() || operation.precedence < 0) {
return {{}, expression_parse_error{0, "invalid unary operator table"}};
}
symbols.push_back(operation.symbol);
}
std::sort(symbols.begin(), symbols.end(), [](const auto &first,
const auto &second) {
if (first.size() != second.size()) {
return first.size() > second.size();
}
return first < second;
});
symbols.erase(std::unique(symbols.begin(), symbols.end()), symbols.end());
std::vector<token> tokens;
for (std::size_t position = 0; position < expression.size();) {
unsigned char character = expression[position];
if (std::isspace(character)) {
position++;
continue;
}
if (character == '(' || character == ')') {
tokens.push_back({character == '(' ? token::kind::left_parenthesis
: token::kind::right_parenthesis,
std::string(1, char(character)), position});
position++;
continue;
}
if (std::isalnum(character) || character == '_') {
std::size_t end = position + 1;
while (end < expression.size()) {
unsigned char next = expression[end];
if (!std::isalnum(next) && next != '_') {
break;
}
end++;
}
tokens.push_back({token::kind::operand,
std::string(expression.substr(position, end - position)),
position});
position = end;
continue;
}
auto match = std::find_if(symbols.begin(), symbols.end(),
[&](const std::string &symbol) {
return expression.substr(position, symbol.size()) == symbol;
});
if (match == symbols.end()) {
return {{}, expression_parse_error{position, "unknown token"}};
}
tokens.push_back({token::kind::operation, *match, position});
position += match->size();
}
tokens.push_back({token::kind::end, {}, expression.size()});
expression_tree tree;
std::size_t cursor = 0;
std::optional<expression_parse_error> error;
auto fail = [&](std::string message) {
if (!error) {
error = expression_parse_error{tokens[cursor].position,
std::move(message)};
}
return -1;
};
auto binary = [&](const std::string &symbol)
-> const expression_binary_operator * {
auto iterator = std::find_if(
binary_operators.begin(), binary_operators.end(),
[&](const auto &operation) { return operation.symbol == symbol; });
return iterator == binary_operators.end() ? nullptr : &*iterator;
};
auto unary = [&](const std::string &symbol)
-> const expression_unary_operator * {
auto iterator = std::find_if(
unary_operators.begin(), unary_operators.end(),
[&](const auto &operation) { return operation.symbol == symbol; });
return iterator == unary_operators.end() ? nullptr : &*iterator;
};
auto make_node = [&](expression_node node) {
tree.nodes.push_back(std::move(node));
return int(tree.nodes.size()) - 1;
};
auto parse = [&](auto &self, int minimum_precedence) -> int {
int left = -1;
if (tokens[cursor].type == token::kind::operand) {
left = make_node(
{expression_node::kind::operand, tokens[cursor].text, -1, -1});
cursor++;
} else if (tokens[cursor].type == token::kind::left_parenthesis) {
cursor++;
left = self(self, 0);
if (left == -1) {
return -1;
}
if (tokens[cursor].type != token::kind::right_parenthesis) {
return fail("missing closing parenthesis");
}
cursor++;
} else if (tokens[cursor].type == token::kind::operation) {
const auto *operation = unary(tokens[cursor].text);
if (operation == nullptr) {
return fail("expected operand or prefix unary operator");
}
std::string symbol = tokens[cursor++].text;
int child = self(self, operation->precedence);
if (child == -1) {
return -1;
}
left = make_node(
{expression_node::kind::unary, std::move(symbol), child, -1});
} else {
return fail("expected operand");
}
while (tokens[cursor].type == token::kind::operation) {
const auto *operation = binary(tokens[cursor].text);
if (operation == nullptr || operation->precedence < minimum_precedence) {
break;
}
std::string symbol = tokens[cursor++].text;
int next_precedence =
operation->precedence + (operation->right_associative ? 0 : 1);
int right = self(self, next_precedence);
if (right == -1) {
return -1;
}
left = make_node({expression_node::kind::binary, std::move(symbol), left,
right});
}
return left;
};
tree.root = parse(parse, 0);
if (tree.root == -1) {
return {{}, error};
}
if (tokens[cursor].type != token::kind::end) {
fail(tokens[cursor].type == token::kind::right_parenthesis
? "unmatched closing parenthesis"
: "unexpected token after expression");
return {{}, error};
}
return {std::move(tree), {}};
}
} // namespace noya
#endif // NOYA_EXPRESSION_PARSER_HPP
#include <algorithm>
#include <cctype>
#include <cstddef>
#include <optional>
#include <string>
#include <string_view>
#include <utility>
#include <vector>
/// @complexity Time: O(t log o) for t tokens and ordered operator tables.
/// Space: O(t) parse stacks/output.
namespace noya {
struct expression_binary_operator {
std::string symbol;
int precedence = 0;
bool right_associative = false;
};
struct expression_unary_operator {
std::string symbol;
int precedence = 0;
};
struct expression_node {
enum class kind { operand, unary, binary } type = kind::operand;
std::string token;
int left = -1;
int right = -1;
};
struct expression_tree {
std::vector<expression_node> nodes;
int root = -1;
};
struct expression_parse_error {
std::size_t position = 0;
std::string message;
};
struct expression_parse_result {
std::optional<expression_tree> tree;
std::optional<expression_parse_error> error;
explicit operator bool() const { return tree.has_value(); }
};
/// @brief Parse identifiers, integers, parentheses, configurable binary
/// operators, and configurable prefix unary operators into an expression tree.
inline expression_parse_result parse_expression(
std::string_view expression,
const std::vector<expression_binary_operator> &binary_operators,
const std::vector<expression_unary_operator> &unary_operators = {}) {
struct token {
enum class kind { operand, operation, left_parenthesis, right_parenthesis,
end } type = kind::end;
std::string text;
std::size_t position = 0;
};
std::vector<std::string> symbols;
for (const auto &operation : binary_operators) {
if (operation.symbol.empty() || operation.precedence < 0) {
return {{}, expression_parse_error{0, "invalid binary operator table"}};
}
symbols.push_back(operation.symbol);
}
for (const auto &operation : unary_operators) {
if (operation.symbol.empty() || operation.precedence < 0) {
return {{}, expression_parse_error{0, "invalid unary operator table"}};
}
symbols.push_back(operation.symbol);
}
std::sort(symbols.begin(), symbols.end(), [](const auto &first,
const auto &second) {
if (first.size() != second.size()) {
return first.size() > second.size();
}
return first < second;
});
symbols.erase(std::unique(symbols.begin(), symbols.end()), symbols.end());
std::vector<token> tokens;
for (std::size_t position = 0; position < expression.size();) {
unsigned char character = expression[position];
if (std::isspace(character)) {
position++;
continue;
}
if (character == '(' || character == ')') {
tokens.push_back({character == '(' ? token::kind::left_parenthesis
: token::kind::right_parenthesis,
std::string(1, char(character)), position});
position++;
continue;
}
if (std::isalnum(character) || character == '_') {
std::size_t end = position + 1;
while (end < expression.size()) {
unsigned char next = expression[end];
if (!std::isalnum(next) && next != '_') {
break;
}
end++;
}
tokens.push_back({token::kind::operand,
std::string(expression.substr(position, end - position)),
position});
position = end;
continue;
}
auto match = std::find_if(symbols.begin(), symbols.end(),
[&](const std::string &symbol) {
return expression.substr(position, symbol.size()) == symbol;
});
if (match == symbols.end()) {
return {{}, expression_parse_error{position, "unknown token"}};
}
tokens.push_back({token::kind::operation, *match, position});
position += match->size();
}
tokens.push_back({token::kind::end, {}, expression.size()});
expression_tree tree;
std::size_t cursor = 0;
std::optional<expression_parse_error> error;
auto fail = [&](std::string message) {
if (!error) {
error = expression_parse_error{tokens[cursor].position,
std::move(message)};
}
return -1;
};
auto binary = [&](const std::string &symbol)
-> const expression_binary_operator * {
auto iterator = std::find_if(
binary_operators.begin(), binary_operators.end(),
[&](const auto &operation) { return operation.symbol == symbol; });
return iterator == binary_operators.end() ? nullptr : &*iterator;
};
auto unary = [&](const std::string &symbol)
-> const expression_unary_operator * {
auto iterator = std::find_if(
unary_operators.begin(), unary_operators.end(),
[&](const auto &operation) { return operation.symbol == symbol; });
return iterator == unary_operators.end() ? nullptr : &*iterator;
};
auto make_node = [&](expression_node node) {
tree.nodes.push_back(std::move(node));
return int(tree.nodes.size()) - 1;
};
auto parse = [&](auto &self, int minimum_precedence) -> int {
int left = -1;
if (tokens[cursor].type == token::kind::operand) {
left = make_node(
{expression_node::kind::operand, tokens[cursor].text, -1, -1});
cursor++;
} else if (tokens[cursor].type == token::kind::left_parenthesis) {
cursor++;
left = self(self, 0);
if (left == -1) {
return -1;
}
if (tokens[cursor].type != token::kind::right_parenthesis) {
return fail("missing closing parenthesis");
}
cursor++;
} else if (tokens[cursor].type == token::kind::operation) {
const auto *operation = unary(tokens[cursor].text);
if (operation == nullptr) {
return fail("expected operand or prefix unary operator");
}
std::string symbol = tokens[cursor++].text;
int child = self(self, operation->precedence);
if (child == -1) {
return -1;
}
left = make_node(
{expression_node::kind::unary, std::move(symbol), child, -1});
} else {
return fail("expected operand");
}
while (tokens[cursor].type == token::kind::operation) {
const auto *operation = binary(tokens[cursor].text);
if (operation == nullptr || operation->precedence < minimum_precedence) {
break;
}
std::string symbol = tokens[cursor++].text;
int next_precedence =
operation->precedence + (operation->right_associative ? 0 : 1);
int right = self(self, next_precedence);
if (right == -1) {
return -1;
}
left = make_node({expression_node::kind::binary, std::move(symbol), left,
right});
}
return left;
};
tree.root = parse(parse, 0);
if (tree.root == -1) {
return {{}, error};
}
if (tokens[cursor].type != token::kind::end) {
fail(tokens[cursor].type == token::kind::right_parenthesis
? "unmatched closing parenthesis"
: "unexpected token after expression");
return {{}, error};
}
return {std::move(tree), {}};
}
} // namespace noya