expression_parser.hpp¶
按优先级和结合性递归解析表达式，支持括号与前缀一元运算符；返回拥有完整字符串的语法树或错误位置，不负责求值。
Complexity: Time: \(O(n + o \log o + t o)\) for bounded-length operators, where \(n\) is input length, \(o\) operator-table size and \(t\) token count. Space: \(O(n + o)\), including \(O(t)\) recursive parse depth.
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(n + o log o + t o) for bounded-length operators,
/// where n is input length, o operator-table size and t token count.
/// Space: O(n + o), including O(t) recursive parse depth.
#include <algorithm>
#include <cctype>
#include <cstddef>
#include <cstdint>
#include <optional>
#include <string>
#include <string_view>
#include <utility>
#include <vector>
namespace noya {
struct expression_binary_operator {
std::string opr;
int pri = 0;
bool ras = false;
};
struct expression_unary_operator {
std::string opr;
int pri = 0;
};
struct expression_node {
enum class kind { operand, unary, binary } tp = kind::operand;
std::string tok;
int ls = -1;
int rs = -1;
};
struct expression_tree {
std::vector<expression_node> tr;
int rt = -1;
};
struct expression_parse_error {
std::size_t ps = 0;
std::string msg;
};
struct expression_parse_result {
std::optional<expression_tree> t;
std::optional<expression_parse_error> err;
explicit operator bool() const { return t.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 s,
const std::vector<expression_binary_operator> &bop,
const std::vector<expression_unary_operator> &uop = {}) {
struct operation {
std::string_view spelling;
const expression_binary_operator *binary = nullptr;
const expression_unary_operator *unary = nullptr;
};
std::vector<operation> ops;
for (const auto &op : bop) {
if (op.opr.empty() || op.pri < 0)
return {{}, expression_parse_error{0, "invalid binary operator table"}};
ops.push_back({op.opr, &op, nullptr});
}
for (const auto &op : uop) {
if (op.opr.empty() || op.pri < 0)
return {{}, expression_parse_error{0, "invalid unary operator table"}};
ops.push_back({op.opr, nullptr, &op});
}
// Longest spelling wins; the first declaration of each kind still wins ties.
std::stable_sort(ops.begin(), ops.end(), [](const auto &a, const auto &b) {
if (a.spelling.size() != b.spelling.size())
return a.spelling.size() > b.spelling.size();
return a.spelling < b.spelling;
});
std::size_t used = 0;
for (auto op : ops) {
if (used && ops[used - 1].spelling == op.spelling) {
auto &prev = ops[used - 1];
if (!prev.binary)
prev.binary = op.binary;
if (!prev.unary)
prev.unary = op.unary;
} else {
ops[used++] = op;
}
}
ops.resize(used);
struct token {
enum class kind {
operand,
operation,
left_parenthesis,
right_parenthesis,
end
} tp;
std::string_view text;
std::size_t pos;
const operation *op = nullptr;
};
std::vector<token> tokens;
// Tokenize first so an unknown character keeps precedence over parse errors.
for (std::size_t pos = 0; pos < s.size();) {
unsigned char ch = s[pos];
if (std::isspace(ch)) {
++pos;
continue;
}
if (ch == '(' || ch == ')') {
tokens.push_back({ch == '(' ? token::kind::left_parenthesis
: token::kind::right_parenthesis,
s.substr(pos, 1), pos});
++pos;
continue;
}
if (std::isalnum(ch) || ch == '_') {
std::size_t end = pos + 1;
while (end < s.size()) {
unsigned char next = s[end];
if (!std::isalnum(next) && next != '_')
break;
++end;
}
tokens.push_back({token::kind::operand, s.substr(pos, end - pos), pos});
pos = end;
continue;
}
auto it = std::find_if(ops.begin(), ops.end(), [&](const auto &op) {
return s.substr(pos, op.spelling.size()) == op.spelling;
});
if (it == ops.end())
return {{}, expression_parse_error{pos, "unknown token"}};
tokens.push_back({token::kind::operation, it->spelling, pos, &*it});
pos += it->spelling.size();
}
tokens.push_back({token::kind::end, {}, s.size()});
expression_tree tree;
std::size_t cur = 0;
std::optional<expression_parse_error> error;
auto fail = [&](const char *message) {
error = expression_parse_error{tokens[cur].pos, message};
return -1;
};
auto insert = [&](expression_node node) {
tree.tr.push_back(std::move(node));
return int(tree.tr.size()) - 1;
};
// Parse a prefix/atom, then binary operators with sufficient binding power.
auto dfs = [&](auto &self, std::uint64_t lo) -> int {
const auto &tok = tokens[cur];
int left;
if (tok.tp == token::kind::operand) {
left = insert({expression_node::kind::operand, std::string(tok.text), -1, -1});
++cur;
} else if (tok.tp == token::kind::left_parenthesis) {
++cur;
left = self(self, 0);
if (left == -1) return -1;
if (tokens[cur].tp != token::kind::right_parenthesis)
return fail("missing closing parenthesis");
++cur;
} else if (tok.tp == token::kind::operation) {
if (!tok.op->unary) return fail("expected operand or prefix unary operator");
++cur;
int child = self(self, tok.op->unary->pri);
if (child == -1) return -1;
left = insert({expression_node::kind::unary, std::string(tok.text), child, -1});
} else return fail("expected operand");
while (tokens[cur].tp == token::kind::operation) {
const auto &next = tokens[cur];
const auto *op = next.op->binary;
if (!op || std::uint64_t(op->pri) < lo) break;
++cur;
// Widen before +1, including when the priority is INT_MAX.
int right = self(self, std::uint64_t(op->pri) + !op->ras);
if (right == -1) return -1;
left = insert({expression_node::kind::binary, std::string(next.text), left, right});
}
return left;
};
tree.rt = dfs(dfs, 0);
if (tree.rt == -1) return {{}, error};
if (tokens[cur].tp != token::kind::end) {
fail(tokens[cur].tp == token::kind::right_parenthesis
? "unmatched closing parenthesis" : "unexpected token after expression");
return {{}, error};
}
return {std::move(tree), {}};
}
} // namespace noya
// NOYA_EXPRESSION_PARSER_HPP
#ifndef NOYA_EXPRESSION_PARSER_HPP
#define NOYA_EXPRESSION_PARSER_HPP 1
/// @complexity Time: O(n + o log o + t o) for bounded-length operators,
/// where n is input length, o operator-table size and t token count.
/// Space: O(n + o), including O(t) recursive parse depth.
#include <algorithm>
#include <cctype>
#include <cstddef>
#include <cstdint>
#include <optional>
#include <string>
#include <string_view>
#include <utility>
#include <vector>
namespace noya {
struct expression_binary_operator {
std::string opr;
int pri = 0;
bool ras = false;
};
struct expression_unary_operator {
std::string opr;
int pri = 0;
};
struct expression_node {
enum class kind { operand, unary, binary } tp = kind::operand;
std::string tok;
int ls = -1;
int rs = -1;
};
struct expression_tree {
std::vector<expression_node> tr;
int rt = -1;
};
struct expression_parse_error {
std::size_t ps = 0;
std::string msg;
};
struct expression_parse_result {
std::optional<expression_tree> t;
std::optional<expression_parse_error> err;
explicit operator bool() const { return t.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 s,
const std::vector<expression_binary_operator> &bop,
const std::vector<expression_unary_operator> &uop = {}) {
struct operation {
std::string_view spelling;
const expression_binary_operator *binary = nullptr;
const expression_unary_operator *unary = nullptr;
};
std::vector<operation> ops;
for (const auto &op : bop) {
if (op.opr.empty() || op.pri < 0)
return {{}, expression_parse_error{0, "invalid binary operator table"}};
ops.push_back({op.opr, &op, nullptr});
}
for (const auto &op : uop) {
if (op.opr.empty() || op.pri < 0)
return {{}, expression_parse_error{0, "invalid unary operator table"}};
ops.push_back({op.opr, nullptr, &op});
}
// Longest spelling wins; the first declaration of each kind still wins ties.
std::stable_sort(ops.begin(), ops.end(), [](const auto &a, const auto &b) {
if (a.spelling.size() != b.spelling.size())
return a.spelling.size() > b.spelling.size();
return a.spelling < b.spelling;
});
std::size_t used = 0;
for (auto op : ops) {
if (used && ops[used - 1].spelling == op.spelling) {
auto &prev = ops[used - 1];
if (!prev.binary)
prev.binary = op.binary;
if (!prev.unary)
prev.unary = op.unary;
} else {
ops[used++] = op;
}
}
ops.resize(used);
struct token {
enum class kind {
operand,
operation,
left_parenthesis,
right_parenthesis,
end
} tp;
std::string_view text;
std::size_t pos;
const operation *op = nullptr;
};
std::vector<token> tokens;
// Tokenize first so an unknown character keeps precedence over parse errors.
for (std::size_t pos = 0; pos < s.size();) {
unsigned char ch = s[pos];
if (std::isspace(ch)) {
++pos;
continue;
}
if (ch == '(' || ch == ')') {
tokens.push_back({ch == '(' ? token::kind::left_parenthesis
: token::kind::right_parenthesis,
s.substr(pos, 1), pos});
++pos;
continue;
}
if (std::isalnum(ch) || ch == '_') {
std::size_t end = pos + 1;
while (end < s.size()) {
unsigned char next = s[end];
if (!std::isalnum(next) && next != '_')
break;
++end;
}
tokens.push_back({token::kind::operand, s.substr(pos, end - pos), pos});
pos = end;
continue;
}
auto it = std::find_if(ops.begin(), ops.end(), [&](const auto &op) {
return s.substr(pos, op.spelling.size()) == op.spelling;
});
if (it == ops.end())
return {{}, expression_parse_error{pos, "unknown token"}};
tokens.push_back({token::kind::operation, it->spelling, pos, &*it});
pos += it->spelling.size();
}
tokens.push_back({token::kind::end, {}, s.size()});
expression_tree tree;
std::size_t cur = 0;
std::optional<expression_parse_error> error;
auto fail = [&](const char *message) {
error = expression_parse_error{tokens[cur].pos, message};
return -1;
};
auto insert = [&](expression_node node) {
tree.tr.push_back(std::move(node));
return int(tree.tr.size()) - 1;
};
// Parse a prefix/atom, then binary operators with sufficient binding power.
auto dfs = [&](auto &self, std::uint64_t lo) -> int {
const auto &tok = tokens[cur];
int left;
if (tok.tp == token::kind::operand) {
left = insert({expression_node::kind::operand, std::string(tok.text), -1, -1});
++cur;
} else if (tok.tp == token::kind::left_parenthesis) {
++cur;
left = self(self, 0);
if (left == -1) return -1;
if (tokens[cur].tp != token::kind::right_parenthesis)
return fail("missing closing parenthesis");
++cur;
} else if (tok.tp == token::kind::operation) {
if (!tok.op->unary) return fail("expected operand or prefix unary operator");
++cur;
int child = self(self, tok.op->unary->pri);
if (child == -1) return -1;
left = insert({expression_node::kind::unary, std::string(tok.text), child, -1});
} else return fail("expected operand");
while (tokens[cur].tp == token::kind::operation) {
const auto &next = tokens[cur];
const auto *op = next.op->binary;
if (!op || std::uint64_t(op->pri) < lo) break;
++cur;
// Widen before +1, including when the priority is INT_MAX.
int right = self(self, std::uint64_t(op->pri) + !op->ras);
if (right == -1) return -1;
left = insert({expression_node::kind::binary, std::string(next.text), left, right});
}
return left;
};
tree.rt = dfs(dfs, 0);
if (tree.rt == -1) return {{}, error};
if (tokens[cur].tp != token::kind::end) {
fail(tokens[cur].tp == token::kind::right_parenthesis
? "unmatched closing parenthesis" : "unexpected token after expression");
return {{}, error};
}
return {std::move(tree), {}};
}
} // namespace noya
#endif // NOYA_EXPRESSION_PARSER_HPP
/// @complexity Time: O(n + o log o + t o) for bounded-length operators,
/// where n is input length, o operator-table size and t token count.
/// Space: O(n + o), including O(t) recursive parse depth.
#include <algorithm>
#include <cctype>
#include <cstddef>
#include <cstdint>
#include <optional>
#include <string>
#include <string_view>
#include <utility>
#include <vector>
namespace noya {
struct expression_binary_operator {
std::string opr;
int pri = 0;
bool ras = false;
};
struct expression_unary_operator {
std::string opr;
int pri = 0;
};
struct expression_node {
enum class kind { operand, unary, binary } tp = kind::operand;
std::string tok;
int ls = -1;
int rs = -1;
};
struct expression_tree {
std::vector<expression_node> tr;
int rt = -1;
};
struct expression_parse_error {
std::size_t ps = 0;
std::string msg;
};
struct expression_parse_result {
std::optional<expression_tree> t;
std::optional<expression_parse_error> err;
explicit operator bool() const { return t.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 s,
const std::vector<expression_binary_operator> &bop,
const std::vector<expression_unary_operator> &uop = {}) {
struct operation {
std::string_view spelling;
const expression_binary_operator *binary = nullptr;
const expression_unary_operator *unary = nullptr;
};
std::vector<operation> ops;
for (const auto &op : bop) {
if (op.opr.empty() || op.pri < 0)
return {{}, expression_parse_error{0, "invalid binary operator table"}};
ops.push_back({op.opr, &op, nullptr});
}
for (const auto &op : uop) {
if (op.opr.empty() || op.pri < 0)
return {{}, expression_parse_error{0, "invalid unary operator table"}};
ops.push_back({op.opr, nullptr, &op});
}
// Longest spelling wins; the first declaration of each kind still wins ties.
std::stable_sort(ops.begin(), ops.end(), [](const auto &a, const auto &b) {
if (a.spelling.size() != b.spelling.size())
return a.spelling.size() > b.spelling.size();
return a.spelling < b.spelling;
});
std::size_t used = 0;
for (auto op : ops) {
if (used && ops[used - 1].spelling == op.spelling) {
auto &prev = ops[used - 1];
if (!prev.binary)
prev.binary = op.binary;
if (!prev.unary)
prev.unary = op.unary;
} else {
ops[used++] = op;
}
}
ops.resize(used);
struct token {
enum class kind {
operand,
operation,
left_parenthesis,
right_parenthesis,
end
} tp;
std::string_view text;
std::size_t pos;
const operation *op = nullptr;
};
std::vector<token> tokens;
// Tokenize first so an unknown character keeps precedence over parse errors.
for (std::size_t pos = 0; pos < s.size();) {
unsigned char ch = s[pos];
if (std::isspace(ch)) {
++pos;
continue;
}
if (ch == '(' || ch == ')') {
tokens.push_back({ch == '(' ? token::kind::left_parenthesis
: token::kind::right_parenthesis,
s.substr(pos, 1), pos});
++pos;
continue;
}
if (std::isalnum(ch) || ch == '_') {
std::size_t end = pos + 1;
while (end < s.size()) {
unsigned char next = s[end];
if (!std::isalnum(next) && next != '_')
break;
++end;
}
tokens.push_back({token::kind::operand, s.substr(pos, end - pos), pos});
pos = end;
continue;
}
auto it = std::find_if(ops.begin(), ops.end(), [&](const auto &op) {
return s.substr(pos, op.spelling.size()) == op.spelling;
});
if (it == ops.end())
return {{}, expression_parse_error{pos, "unknown token"}};
tokens.push_back({token::kind::operation, it->spelling, pos, &*it});
pos += it->spelling.size();
}
tokens.push_back({token::kind::end, {}, s.size()});
expression_tree tree;
std::size_t cur = 0;
std::optional<expression_parse_error> error;
auto fail = [&](const char *message) {
error = expression_parse_error{tokens[cur].pos, message};
return -1;
};
auto insert = [&](expression_node node) {
tree.tr.push_back(std::move(node));
return int(tree.tr.size()) - 1;
};
// Parse a prefix/atom, then binary operators with sufficient binding power.
auto dfs = [&](auto &self, std::uint64_t lo) -> int {
const auto &tok = tokens[cur];
int left;
if (tok.tp == token::kind::operand) {
left = insert({expression_node::kind::operand, std::string(tok.text), -1, -1});
++cur;
} else if (tok.tp == token::kind::left_parenthesis) {
++cur;
left = self(self, 0);
if (left == -1) return -1;
if (tokens[cur].tp != token::kind::right_parenthesis)
return fail("missing closing parenthesis");
++cur;
} else if (tok.tp == token::kind::operation) {
if (!tok.op->unary) return fail("expected operand or prefix unary operator");
++cur;
int child = self(self, tok.op->unary->pri);
if (child == -1) return -1;
left = insert({expression_node::kind::unary, std::string(tok.text), child, -1});
} else return fail("expected operand");
while (tokens[cur].tp == token::kind::operation) {
const auto &next = tokens[cur];
const auto *op = next.op->binary;
if (!op || std::uint64_t(op->pri) < lo) break;
++cur;
// Widen before +1, including when the priority is INT_MAX.
int right = self(self, std::uint64_t(op->pri) + !op->ras);
if (right == -1) return -1;
left = insert({expression_node::kind::binary, std::string(next.text), left, right});
}
return left;
};
tree.rt = dfs(dfs, 0);
if (tree.rt == -1) return {{}, error};
if (tokens[cur].tp != token::kind::end) {
fail(tokens[cur].tp == token::kind::right_parenthesis
? "unmatched closing parenthesis" : "unexpected token after expression");
return {{}, error};
}
return {std::move(tree), {}};
}
} // namespace noya
// NOYA_EXPRESSION_PARSER_HPP