现代 C++ 数学表达式解释器实现

形式语言与自动机定义

• 文法 (Grammar) - G = (V, T, P, S)

  • V: 变量的非空有限集。∀A∈V，A 是语法变量（简称变量），也称为非终结符。V 定义了一个语法类别。
  • T: 终结符的非空有限集。∀a∈T，a 称为终结符，是语言句子中的实际符号。注意 V 描述的是语法类别，所以 V ∩ T = ∅。
  • P: 产生式的非空有限集。P = {α → β | ∃αᵢ ∈ V, α = α₁α₂...αₙ, α ∈ (V ∪ T)⁺, β ∈ (V ∪ T)*}。产生式 α → β 读作'α 定义为 β'，也称为定义或语法规则。
  • S: S ∈ V，是文法 G 的开始符号。

  注：α → β₁,...,α → βₙ 可简化为 α → β₁|...|βₙ，β₁,...,βₙ 称为候选项。

• 推导 (Derivation) 若 α → β ∈ P, γ, δ ∈ (V ∪ T)*，则 γαδ ⇒G γβδ

实现

#include <cmath>
#include <format>
#include <iostream>
#include <memory>
#include <numbers>
#include <regex>
#include <string>
#include <unordered_map>
#include <variant>
#include <vector>

struct Token {
    enum Type {
        PLUS = 1,
        MINUS = 1 << 1,
        NUMBER = 1 << 2,
        VAR = 1 << 3,
        MUL = 1 << 4,
        DIV = 1 << 5,
        POW = 1 << 6,
        LPR = 1 << 7,
        RPR = 1 << 8,
        PI = 1 << 9,
        EXP = 1 << 10,
        Func = 1 << 11,
        ANY = PLUS | MINUS | NUMBER | VAR | MUL | DIV | POW | LPR | RPR | PI | EXP | Func
    };
    Type type;
    std::string text;

    explicit Token(Type type, std::string const& text) : type{type}, text{text} {}
    explicit Token(Type type, std::string_view const& text) : type{type}, text{text} {}
    explicit Token(Type type, const char* text) : type{type}, text{text} {}

    friend std::ostream& operator<<(std::ostream& os, Token const& tk) {
        os << "Token Type: " << (tk.type) << " " << tk.text << "\n";
        return os;
    }

    static std::vector<Token> lex(const std::string& input);
    static std::string from(int bitmask) {
        std::string result;
        if (bitmask & PLUS) result += "|PLUS";
        if (bitmask & MINUS) result += "|MINUS";
        if (bitmask & NUMBER) result += "|NUMBER";
        if (bitmask & VAR) result += "|VAR";
        if (bitmask & MUL) result += "|MUL";
        if (bitmask & DIV) result += "|DIV";
        if (bitmask & POW) result += "|POW";
        if (bitmask & LPR) result += "|LPR";
        if (bitmask & RPR) result += "|RPR";
        if (bitmask & PI) result += "|PI";
        if (bitmask & EXP) result += "|EXP";
        if (bitmask & Func) result += "|Func";
        if (!result.empty()) return result.substr(1);
        return result + "|";
    }

private:
    static std::optional<Token> parse_ch(char c) {
        switch (c) {
            case '+': return Token(Token::PLUS, "+");
            case '-': return Token(Token::MINUS, "-");
            case '*': return Token(Token::MUL, "*");
            case '/': return Token(Token::DIV, "/");
            case '^': return Token(Token::POW, "^");
            case '(': return Token(Token::LPR, "(");
            case ')': return Token(Token::RPR, ")");
            case 'e': return Token(Token::EXP, "e");
            case 'x': return Token(Token::VAR, "x");
            case 'y': return Token(Token::VAR, "y");
            case 'z': return Token(Token::VAR, "z");
            default: return std::nullopt;
        }
    }
};

std::vector<Token> Token::lex(const std::string& input) {
    std::vector<Token> result;
    auto re = std::regex(R"(0*(\d+(\.\d+)?))");
    auto begin = input.begin();
    while (begin != input.end()) {
        auto t = parse_ch(*begin);
        if (t) {
            result.emplace_back(std::move(t.value()));
            begin++;
            continue;
        }
        auto PI = "PI";
        if (std::equal(PI, PI + 2, begin)) {
            result.emplace_back(Token::PI, PI);
            begin += 2;
            continue;
        }
        if (std::isdigit(*begin)) {
            std::smatch m;
            if (std::regex_search(begin, input.end(), m, re)) {
                auto number = m[1].str();
                result.emplace_back(Token::NUMBER, number);
                begin += number.size();
                continue;
            }
        } else if (std::isalpha(*begin)) {
            auto f = std::find_if(begin, input.end(), [](char c) { return !std::isalpha(c); });
            result.emplace_back(Token::Func, std::string(begin, f));
            begin = f;
            continue;
        }
        throw std::format_error("Invalid token while lexing.");
    }
    return result;
}

struct ast_element;
struct ast_visitor {
    std::vector<double> variable_feed;
    ast_visitor(std::vector<double> init_list) : variable_feed(std::move(init_list)) {}
    double operator()(ast_element& elem);
};

struct ast_element {
    using Node = std::unique_ptr<ast_element>;
    std::string text;
    Node l, r;
    double value;

    ast_element(std::string text, Node l, Node r) : text(std::move(text)), l(std::move(l)), r(std::move(r)) {}
    virtual double eval(const ast_visitor& visitor) = 0;
    virtual void accept(ast_visitor& visitor);
    virtual ~ast_element() = default;
};

struct Constant : ast_element {
    Constant(std::string text, double value) : ast_element(std::move(text), nullptr, nullptr) { this->value = value; }
    double eval(const ast_visitor&) { return this->value; }
};

struct Variable : ast_element {
    int feed = 0;
    Variable(std::string text, int feed = 0) : ast_element(std::move(text), nullptr, nullptr), feed{feed} {}
    double eval(const ast_visitor& visitor) { return this->value = visitor.variable_feed[feed]; }
};

struct BinaryOp : ast_element {
    using BOp = std::function<double(double, double)>;
    BOp f;
    BinaryOp(std::string text, Node l, Node r, BOp f) : ast_element(std::move(text), std::move(l), std::move(r)), f(std::move(f)) {}
    double eval(const ast_visitor&) { return this->value = f(l->value, r->value); }
};

struct UnaryOp : public ast_element {
    using UOp = std::function<double(double)>;
    UOp f;
    UnaryOp(std::string text, Node l, UOp f) : ast_element(std::move(text), std::move(l), nullptr), f(std::move(f)) {}
    double eval(const ast_visitor&) { return this->value = f(l->value); }
};

struct ast_factory {
    using Node = ast_element::Node;
    std::string text;
    ast_factory() {}
    ast_factory(std::string text) : text(std::move(text)) {}
    virtual ast_factory& with(std::string text) { this->text = std::move(text); return *this; }
    virtual Node create(Node l, Node r) { return nullptr; }
    virtual Node create(Node l) { return nullptr; }
    virtual Node create() { return nullptr; }
    virtual ~ast_factory() = default;
};

struct op_factory : ast_factory {
    using BOp = BinaryOp::BOp;
    using UOp = UnaryOp::UOp;
    using Op = std::variant<BOp, UOp>;
    Op f;
    op_factory(Op f) : ast_factory(), f(std::move(f)) {}
    op_factory(std::string text, Op f) : ast_factory(std::move(text)), f(std::move(f)) {}
    op_factory& with_Op(Op op) { this->f = std::move(op); return *this; }
    virtual Node create(Node l, Node r) { return std::make_unique<BinaryOp>(text, std::move(l), std::move(r), std::get<BOp>(f)); }
    virtual Node create(Node l) { return std::make_unique<UnaryOp>(text, std::move(l), std::get<UOp>(f)); }
};

struct const_factory : ast_factory {
    double value;
    const_factory() {}
    const_factory(std::string text, double value) : ast_factory(std::move(text)), value{value} {}
    const_factory& with_val(double val) { this->value = val; return *this; }
    virtual Node create() { return std::make_unique<Constant>(text, value); }
};

struct var_factory : ast_factory {
    var_factory() {}
    var_factory(std::string text) : ast_factory(std::move(text)) {}
    virtual Node create() { return std::make_unique<Variable>(text); }
};

struct ParseException : public std::exception {
    using itr = std::vector<Token>::const_iterator;
    std::string err;
    ParseException(const std::string& expecting, const std::string& having) : err(std::format("Syntax error, expecting: {}, having: {}", expecting, having)) {}
    ParseException(const std::string& having) : err(std::format("Syntax error, having: {}", having)) {}
    const char* what() const noexcept { return err.c_str(); }
};

struct Parser {
    using Node = ast_element::Node;
    using itr = std::vector<Token>::const_iterator;
    std::unordered_map<std::string, op_factory::UOp> function_table;
    itr begin, end;

    Parser(itr begin, itr end) : begin{begin}, end{end} {}
    Parser& register_function(const std::string& text, std::function<double(double)> func) {
        function_table[text] = std::move(func);
        return *this;
    }
    Node parse() { return E(); }
    bool accepted() { return begin == end; }

private:
    void throwIfExhausted() {
        if (begin == end) throw ParseException("Input exhausted");
    }
    void consumeToken(Token::Type type) {
        throwIfExhausted();
        if (begin->type != type) throw ParseException(Token::from(type), begin->text);
        begin++;
    }

    // E -> C | C + D | C - D
    Node E() {
        auto c = C();
        if (begin == end || (begin->type != Token::PLUS && begin->type != Token::MINUS)) return c;
        auto factory = op_factory(begin->text, begin->type == Token::PLUS ? op_factory::BOp(std::plus<double>{}) : op_factory::BOp(std::minus<double>{}));
        begin++;
        auto d = D();
        return factory.create(std::move(c), std::move(d));
    }

    // Allow leading sign in E
    // C -> +T | -T | T
    Node C() {
        throwIfExhausted();
        if (begin->type == Token::PLUS || begin->type == Token::MINUS) {
            begin++;
            auto factory = op_factory(begin->text, begin->type == Token::PLUS ? op_factory::UOp([](double v) { return v; }) : op_factory::UOp([](double v) { return -v; }));
            auto t = T();
            return factory.create(std::move(t));
        }
        auto t = T();
        return t;
    }

    // D -> T | T + D | T - D
    Node D() {
        auto t = T();
        if (begin == end || (begin->type != Token::PLUS && begin->type != Token::MINUS)) return t;
        auto factory = op_factory(begin->text, begin->type == Token::PLUS ? op_factory::BOp(std::plus<double>{}) : op_factory::BOp(std::minus<double>{}));
        begin++;
        auto d = D();
        return factory.create(std::move(t), std::move(d));
    }

    // T -> F | F * T | F / T
    Node T() {
        auto f = F();
        if (begin == end || (begin->type != Token::MUL && begin->type != Token::DIV)) return f;
        auto fun = begin->type == Token::MUL ? op_factory::BOp([](double a, double b) { return a * b; }) : op_factory::BOp([](double a, double b) { return a / b; });
        auto factory = op_factory(begin->text, fun);
        begin++;
        auto t = T();
        return factory.create(std::move(f), std::move(t));
    }

    // F -> P | P ^ P
    Node F() {
        auto p = P();
        if (begin == end || begin->type != Token::POW) return p;
        auto factory = op_factory(begin->text, [](double a, double b) { return std::pow(a, b); });
        begin++;
        return factory.create(std::move(p), P());
    }

    // P -> [:digit:]+(.[:digit:]+)? | PI | e | (E) | B | X
    Node P() {
        throwIfExhausted();
        if (begin->type == Token::LPR) {
            consumeToken(Token::LPR);
            auto e = E();
            consumeToken(Token::RPR);
            return e;
        }
        if (begin->type == Token::Func) return B();
        if (begin->type == Token::VAR) return X();
        auto factory = const_factory();
        switch (begin->type) {
            case Token::NUMBER: factory.with_val(std::stod(begin->text)); break;
            case Token::PI: factory.with_val(std::numbers::pi); break;
            case Token::EXP: factory.with_val(std::numbers::e); break;
            default: throw ParseException("NUMBER|PI|e", begin->text);
        }
        factory.with(begin->text);
        begin++;
        return factory.create();
    }

    // B -> sin(E) | cos(E) | tan(E) | arcsin(E) ....
    Node B() {
        auto factory = op_factory(begin->text, function_table.at(begin->text));
        begin++;
        consumeToken(Token::LPR);
        auto e = E();
        consumeToken(Token::RPR);
        return factory.create(std::move(e));
    }

    // X -> x, y, z
    Node X() {
        auto factory = var_factory(begin->text);
        begin++;
        return factory.create();
    }
};

double ast_visitor::operator()(ast_element& elem) {
    elem.accept(*this);
    return elem.eval(*this);
}

void ast_element::accept(ast_visitor& visitor) {
    if (l) l->accept(visitor);
    if (r) r->accept(visitor);
    this->eval(visitor);
    std::cout << "Visited: " << text << ",";
}

int main() {
    std::string input;
    std::cin >> input;
    auto lex = Token::lex(input);

    auto parser = Parser(lex.begin(), lex.end());
    parser.register_function("sin", [](double v) { return std::sin(v); })
           .register_function("cos", [](double v) { return std::cos(v); })
           .register_function("tan", [](double v) { return std::tan(v); })
           .register_function("abs", [](double v) { return std::abs(v); })
           .register_function("arcsin", [](double v) { return std::asin(v); })
           .register_function("arccos", [](double v) { return std::acos(v); })
           .register_function("arctan", [](double v) { return std::atan(v); });

    auto ast = parser.parse();
    std::cout << "Accept status: " << std::boolalpha << parser.accepted() << "\n";
    auto visitor = ast_visitor({1});
    auto result = visitor(*ast);
    std::cout << "Value: " << result;
}

概述

本程序实现了一个数学表达式解释器。它读取字符串表达式，将其转换为令牌（Tokens），解析为抽象语法树（AST），并使用访问者模式求值结果。

支持功能：

• 算术运算符：+ - * / ^
• 括号
• 常量：PI, e
• 变量：x, y, z
• 一元运算符
• 内置数学函数：sin, cos, tan, abs 等
• 可扩展函数注册

架构

输入字符串 → 词法分析器 (Lexer) → 语法分析器 (Parser) → 抽象语法树 (AST) → 访问者 (Visitor) → 计算结果

词法分析 (Tokenization)

令牌结构

每个令牌包含：

• type – 语义类别
• text – 原始源代码文本

令牌类型包括：

• 运算符 (+ - * / ^)
• 括号 (())
• 数字 (整数及浮点数)
• 常量 (PI, e)
• 变量 (x, y, z)
• 函数名 (sin, cos, …)

词法分析逻辑

• 单字符运算符直接匹配
• 数字使用正则表达式解析
• 字母序列视为函数名
• 非法字符触发异常

抽象语法树 (AST)

基类：ast_element

所有 AST 节点：

• 存储左右子节点指针
• 存储计算后的值
• 实现 eval()
• 支持访问者遍历

AST 节点类型

Constant

表示数字字面量和数学常数。

Variable

从访问者的变量馈送中检索其值。

BinaryOp

表示二元运算符的调用对象：

• 加法
• 减法
• 乘法
• 除法
• 幂运算

UnaryOp

表示一元运算符和数学函数。

工厂模式

AST 节点通过工厂创建：

工厂	职责
op_factory	一元及二元运算符
const_factory	数值常量
var_factory	变量

这保持了解析逻辑的清晰和可扩展性。

语法分析器 (递归下降)

文法

E → C | C + D | C - D
C → +T | -T | T
D → T | T + D | T - D
T → F | F * T | F / T
F → P | P ^ P
P → NUMBER | PI | e | (E) | B | X
B → func(E)
X → x | y | z

每个文法规则直接对应一个解析函数。运算符优先级由文法结构自然处理。

函数注册

数学函数动态注册：

parser.register_function("sin", [](double v){return std::sin(v);});

求值 (访问者模式)

访问者：

• 以后序遍历 AST
• 先评估子节点再评估父节点
• 返回最终数值结果

执行流程

1. 读取表达式字符串
2. 输入分词
3. 将令牌解析为 AST
4. 注册数学函数
5. 提供变量值
6. 评估 AST