expression_parser.hpp¶
解析并计算带括号和运算符优先级的表达式；适合题目要求实现算术语法或把字符串转为表达式树。
Complexity: Time: O(t log o) for t tokens and ordered operator tables. Space: O(t) parse stacks/output.
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @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 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 token {
enum class kind {
operand,
operation,
left_parenthesis,
right_parenthesis,
end
} tp = kind::end;
std::string s0;
std::size_t pos = 0;
};
std::vector<std::string> 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);
}
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);
}
std::sort(ops.begin(), ops.end(), [](const auto &a, const auto &b) {
if (a.size() != b.size()) {
return a.size() > b.size();
}
return a < b;
});
ops.erase(std::unique(ops.begin(), ops.end()), ops.end());
std::vector<token> ts;
for (std::size_t pos = 0; pos < s.size();) {
unsigned char ch = s[pos];
if (std::isspace(ch)) {
pos++;
continue;
}
if (ch == '(' || ch == ')') {
ts.push_back({ch == '(' ? token::kind::left_parenthesis
: token::kind::right_parenthesis,
std::string(1, char(ch)), pos});
pos++;
continue;
}
if (std::isalnum(ch) || ch == '_') {
std::size_t end = pos + 1;
while (end < s.size()) {
unsigned char nxt = s[end];
if (!std::isalnum(nxt) && nxt != '_') {
break;
}
end++;
}
ts.push_back(
{token::kind::operand, std::string(s.substr(pos, end - pos)), pos});
pos = end;
continue;
}
auto it0 =
std::find_if(ops.begin(), ops.end(), [&](const std::string &opr) {
return s.substr(pos, opr.size()) == opr;
});
if (it0 == ops.end()) {
return {{}, expression_parse_error{pos, "unknown token"}};
}
ts.push_back({token::kind::operation, *it0, pos});
pos += it0->size();
}
ts.push_back({token::kind::end, {}, s.size()});
expression_tree t;
std::size_t cur = 0;
std::optional<expression_parse_error> err;
auto bad = [&](std::string msg) {
if (!err) {
err = expression_parse_error{ts[cur].pos, std::move(msg)};
}
return -1;
};
auto bin = [&](const std::string &opr) -> const expression_binary_operator * {
auto it = std::find_if(bop.begin(), bop.end(),
[&](const auto &op) { return op.opr == opr; });
return it == bop.end() ? nullptr : &*it;
};
auto una = [&](const std::string &opr) -> const expression_unary_operator * {
auto it = std::find_if(uop.begin(), uop.end(),
[&](const auto &op) { return op.opr == opr; });
return it == uop.end() ? nullptr : &*it;
};
auto ins = [&](expression_node u) {
t.tr.push_back(std::move(u));
return int(t.tr.size()) - 1;
};
auto dfs = [&](auto &f, int lo) -> int {
int ls = -1;
if (ts[cur].tp == token::kind::operand) {
ls = ins({expression_node::kind::operand, ts[cur].s0, -1, -1});
cur++;
} else if (ts[cur].tp == token::kind::left_parenthesis) {
cur++;
ls = f(f, 0);
if (ls == -1) {
return -1;
}
if (ts[cur].tp != token::kind::right_parenthesis) {
return bad("missing closing parenthesis");
}
cur++;
} else if (ts[cur].tp == token::kind::operation) {
const auto *op = una(ts[cur].s0);
if (op == nullptr) {
return bad("expected operand or prefix unary operator");
}
std::string opr = ts[cur++].s0;
int ch0 = f(f, op->pri);
if (ch0 == -1) {
return -1;
}
ls = ins({expression_node::kind::unary, std::move(opr), ch0, -1});
} else {
return bad("expected operand");
}
while (ts[cur].tp == token::kind::operation) {
const auto *op = bin(ts[cur].s0);
if (op == nullptr || op->pri < lo) {
break;
}
std::string opr = ts[cur++].s0;
int np = op->pri + (op->ras ? 0 : 1);
int rs = f(f, np);
if (rs == -1) {
return -1;
}
ls = ins({expression_node::kind::binary, std::move(opr), ls, rs});
}
return ls;
};
t.rt = dfs(dfs, 0);
if (t.rt == -1) {
return {{}, err};
}
if (ts[cur].tp != token::kind::end) {
bad(ts[cur].tp == token::kind::right_parenthesis
? "unmatched closing parenthesis"
: "unexpected token after expression");
return {{}, err};
}
return {std::move(t), {}};
}
} // namespace noya
#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 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 token {
enum class kind {
operand,
operation,
left_parenthesis,
right_parenthesis,
end
} tp = kind::end;
std::string s0;
std::size_t pos = 0;
};
std::vector<std::string> 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);
}
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);
}
std::sort(ops.begin(), ops.end(), [](const auto &a, const auto &b) {
if (a.size() != b.size()) {
return a.size() > b.size();
}
return a < b;
});
ops.erase(std::unique(ops.begin(), ops.end()), ops.end());
std::vector<token> ts;
for (std::size_t pos = 0; pos < s.size();) {
unsigned char ch = s[pos];
if (std::isspace(ch)) {
pos++;
continue;
}
if (ch == '(' || ch == ')') {
ts.push_back({ch == '(' ? token::kind::left_parenthesis
: token::kind::right_parenthesis,
std::string(1, char(ch)), pos});
pos++;
continue;
}
if (std::isalnum(ch) || ch == '_') {
std::size_t end = pos + 1;
while (end < s.size()) {
unsigned char nxt = s[end];
if (!std::isalnum(nxt) && nxt != '_') {
break;
}
end++;
}
ts.push_back(
{token::kind::operand, std::string(s.substr(pos, end - pos)), pos});
pos = end;
continue;
}
auto it0 =
std::find_if(ops.begin(), ops.end(), [&](const std::string &opr) {
return s.substr(pos, opr.size()) == opr;
});
if (it0 == ops.end()) {
return {{}, expression_parse_error{pos, "unknown token"}};
}
ts.push_back({token::kind::operation, *it0, pos});
pos += it0->size();
}
ts.push_back({token::kind::end, {}, s.size()});
expression_tree t;
std::size_t cur = 0;
std::optional<expression_parse_error> err;
auto bad = [&](std::string msg) {
if (!err) {
err = expression_parse_error{ts[cur].pos, std::move(msg)};
}
return -1;
};
auto bin = [&](const std::string &opr) -> const expression_binary_operator * {
auto it = std::find_if(bop.begin(), bop.end(),
[&](const auto &op) { return op.opr == opr; });
return it == bop.end() ? nullptr : &*it;
};
auto una = [&](const std::string &opr) -> const expression_unary_operator * {
auto it = std::find_if(uop.begin(), uop.end(),
[&](const auto &op) { return op.opr == opr; });
return it == uop.end() ? nullptr : &*it;
};
auto ins = [&](expression_node u) {
t.tr.push_back(std::move(u));
return int(t.tr.size()) - 1;
};
auto dfs = [&](auto &f, int lo) -> int {
int ls = -1;
if (ts[cur].tp == token::kind::operand) {
ls = ins({expression_node::kind::operand, ts[cur].s0, -1, -1});
cur++;
} else if (ts[cur].tp == token::kind::left_parenthesis) {
cur++;
ls = f(f, 0);
if (ls == -1) {
return -1;
}
if (ts[cur].tp != token::kind::right_parenthesis) {
return bad("missing closing parenthesis");
}
cur++;
} else if (ts[cur].tp == token::kind::operation) {
const auto *op = una(ts[cur].s0);
if (op == nullptr) {
return bad("expected operand or prefix unary operator");
}
std::string opr = ts[cur++].s0;
int ch0 = f(f, op->pri);
if (ch0 == -1) {
return -1;
}
ls = ins({expression_node::kind::unary, std::move(opr), ch0, -1});
} else {
return bad("expected operand");
}
while (ts[cur].tp == token::kind::operation) {
const auto *op = bin(ts[cur].s0);
if (op == nullptr || op->pri < lo) {
break;
}
std::string opr = ts[cur++].s0;
int np = op->pri + (op->ras ? 0 : 1);
int rs = f(f, np);
if (rs == -1) {
return -1;
}
ls = ins({expression_node::kind::binary, std::move(opr), ls, rs});
}
return ls;
};
t.rt = dfs(dfs, 0);
if (t.rt == -1) {
return {{}, err};
}
if (ts[cur].tp != token::kind::end) {
bad(ts[cur].tp == token::kind::right_parenthesis
? "unmatched closing parenthesis"
: "unexpected token after expression");
return {{}, err};
}
return {std::move(t), {}};
}
} // 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 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 token {
enum class kind {
operand,
operation,
left_parenthesis,
right_parenthesis,
end
} tp = kind::end;
std::string s0;
std::size_t pos = 0;
};
std::vector<std::string> 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);
}
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);
}
std::sort(ops.begin(), ops.end(), [](const auto &a, const auto &b) {
if (a.size() != b.size()) {
return a.size() > b.size();
}
return a < b;
});
ops.erase(std::unique(ops.begin(), ops.end()), ops.end());
std::vector<token> ts;
for (std::size_t pos = 0; pos < s.size();) {
unsigned char ch = s[pos];
if (std::isspace(ch)) {
pos++;
continue;
}
if (ch == '(' || ch == ')') {
ts.push_back({ch == '(' ? token::kind::left_parenthesis
: token::kind::right_parenthesis,
std::string(1, char(ch)), pos});
pos++;
continue;
}
if (std::isalnum(ch) || ch == '_') {
std::size_t end = pos + 1;
while (end < s.size()) {
unsigned char nxt = s[end];
if (!std::isalnum(nxt) && nxt != '_') {
break;
}
end++;
}
ts.push_back(
{token::kind::operand, std::string(s.substr(pos, end - pos)), pos});
pos = end;
continue;
}
auto it0 =
std::find_if(ops.begin(), ops.end(), [&](const std::string &opr) {
return s.substr(pos, opr.size()) == opr;
});
if (it0 == ops.end()) {
return {{}, expression_parse_error{pos, "unknown token"}};
}
ts.push_back({token::kind::operation, *it0, pos});
pos += it0->size();
}
ts.push_back({token::kind::end, {}, s.size()});
expression_tree t;
std::size_t cur = 0;
std::optional<expression_parse_error> err;
auto bad = [&](std::string msg) {
if (!err) {
err = expression_parse_error{ts[cur].pos, std::move(msg)};
}
return -1;
};
auto bin = [&](const std::string &opr) -> const expression_binary_operator * {
auto it = std::find_if(bop.begin(), bop.end(),
[&](const auto &op) { return op.opr == opr; });
return it == bop.end() ? nullptr : &*it;
};
auto una = [&](const std::string &opr) -> const expression_unary_operator * {
auto it = std::find_if(uop.begin(), uop.end(),
[&](const auto &op) { return op.opr == opr; });
return it == uop.end() ? nullptr : &*it;
};
auto ins = [&](expression_node u) {
t.tr.push_back(std::move(u));
return int(t.tr.size()) - 1;
};
auto dfs = [&](auto &f, int lo) -> int {
int ls = -1;
if (ts[cur].tp == token::kind::operand) {
ls = ins({expression_node::kind::operand, ts[cur].s0, -1, -1});
cur++;
} else if (ts[cur].tp == token::kind::left_parenthesis) {
cur++;
ls = f(f, 0);
if (ls == -1) {
return -1;
}
if (ts[cur].tp != token::kind::right_parenthesis) {
return bad("missing closing parenthesis");
}
cur++;
} else if (ts[cur].tp == token::kind::operation) {
const auto *op = una(ts[cur].s0);
if (op == nullptr) {
return bad("expected operand or prefix unary operator");
}
std::string opr = ts[cur++].s0;
int ch0 = f(f, op->pri);
if (ch0 == -1) {
return -1;
}
ls = ins({expression_node::kind::unary, std::move(opr), ch0, -1});
} else {
return bad("expected operand");
}
while (ts[cur].tp == token::kind::operation) {
const auto *op = bin(ts[cur].s0);
if (op == nullptr || op->pri < lo) {
break;
}
std::string opr = ts[cur++].s0;
int np = op->pri + (op->ras ? 0 : 1);
int rs = f(f, np);
if (rs == -1) {
return -1;
}
ls = ins({expression_node::kind::binary, std::move(opr), ls, rs});
}
return ls;
};
t.rt = dfs(dfs, 0);
if (t.rt == -1) {
return {{}, err};
}
if (ts[cur].tp != token::kind::end) {
bad(ts[cur].tp == token::kind::right_parenthesis
? "unmatched closing parenthesis"
: "unexpected token after expression");
return {{}, err};
}
return {std::move(t), {}};
}
} // namespace noya