Expression.cpp

#include "Expression.h"
#include "EvalState.h"

#include <limits>
#include <stdexcept>
#include <string>

// ========================
// Expression.cpp
// 表达式树各节点的实现，包括常量、变量、复合表达式的求值与树形打印。
// ========================

namespace {

// 快速幂算法：计算 base 的 exp 次幂，若溢出则抛出异常。
// @param base 底数
// @param exp 指数，必须非负
// @return 计算结果（int）
// @throws std::runtime_error 如果 exp < 0 或溢出
int powInt(int base, int exp) {
    if (exp < 0) {
        throw std::runtime_error("Exponent must be non-negative");
    }
    long long result = 1;
    long long b = base;
    int e = exp;
    while (e > 0) {
        if (e & 1) {
            result *= b;
        }
        // 检查中间结果是否溢出 int 范围
        if (result > std::numeric_limits<int>::max() || result < std::numeric_limits<int>::min()) {
            throw std::runtime_error("Exponentiation overflow");
        }
        b *= b;
        if (b > std::numeric_limits<int>::max() || b < std::numeric_limits<int>::min()) {
            throw std::runtime_error("Exponentiation overflow");
        }
        e >>= 1;
    }
    return static_cast<int>(result);
}

// BASIC 语义的取模：余数与除数同号，且绝对值小于除数绝对值。
// @param dividend 被除数
// @param divisor 除数，不能为0
// @return 余数
// @throws std::runtime_error 如果除数为0
int modWithSign(int dividend, int divisor) {
    if (divisor == 0) {
        throw std::runtime_error("Division by zero in MOD");
    }
    int remainder = dividend % divisor;
    // C++ 的 % 运算结果符号与被除数相同，BASIC 需与除数同号
    if (remainder != 0 && ((remainder > 0) != (divisor > 0))) {
        remainder += divisor;
    }
    return remainder;
}
} // namespace


// ========================
// ConstantExpression 常量节点
// ========================

// 构造函数，保存常量值
ConstantExpression::ConstantExpression(int value) : m_value(value) {}


// 求值：常量节点直接返回自身值
int ConstantExpression::eval(EvalState &state) const {
    // 这是一种常见的 C++ 写法，表示“我必须实现这个接口，但这个参数我用不到
    // 主要是因为继承了，必须得符合这个形式
    return m_value;
}

int ConstantExpression::getValue() const noexcept {
    return m_value;
}


// 生成语法树文本：缩进后输出常量值
std::string ConstantExpression::toTreeString(int indent) const {
    return std::string(indent, ' ') + std::to_string(m_value) + "\n";
}

void ConstantExpression::collectVarUses(std::map<std::string, int> &counter) const {
    (void)counter;
    // 用到了这个参数，但是什么也不做
    // = PASS
}


// ========================
// IdentifierExpression 变量节点
// ========================

// 构造函数，保存变量名
IdentifierExpression::IdentifierExpression(std::string name) : m_name(std::move(name)) {}

// 求值：查找变量表，未定义时报错
int IdentifierExpression::eval(EvalState &state) const {
    // std::map<std::string, int> variables = state.getState();
    const auto& variables = state.getState();
    auto it = variables.find(m_name);
    if (it == variables.end()) {
        throw std::runtime_error("Undefined variable: " + m_name);
    }
    return it->second;
}

const std::string& IdentifierExpression::getName() const noexcept {
    return m_name;
}


// 生成语法树文本：缩进后输出变量名
std::string IdentifierExpression::toTreeString(int indent) const {
    return std::string(indent, ' ') + m_name + "\n";
}

void IdentifierExpression::collectVarUses(std::map<std::string, int> &counter) const {
    ++counter[m_name];
}


// ========================
// CompoundExpression 复合表达式节点
// ========================

// 构造函数，保存操作符和左右子树
CompoundExpression::CompoundExpression(std::string op,
                                       std::unique_ptr<Expression> left,
                                       std::unique_ptr<Expression> right)
    : m_operator(std::move(op)), m_left(std::move(left)), m_right(std::move(right)) {}


// 求值：递归计算左右子树，根据操作符执行对应运算
// 支持 + - * / MOD **，遇到除零或未知操作符抛异常
int CompoundExpression::eval(EvalState &state) const {
    // std::map<std::string, int> variables = state.getState();
    int lhs = m_left->eval(state);
    int rhs = m_right->eval(state);
    if (m_operator == "+") return lhs + rhs;
    if (m_operator == "-") return lhs - rhs;
    if (m_operator == "*") return lhs * rhs;
    if (m_operator == "/") {
        if (rhs == 0) throw std::runtime_error("Division by zero");
        return lhs / rhs;
    }
    if (m_operator == "MOD") {
        return modWithSign(lhs, rhs);
    }
    if (m_operator == "**") {
        return powInt(lhs, rhs);
    }
    throw std::runtime_error("Unknown operator: " + m_operator);
}


// 生成语法树文本：本节点输出操作符，左右递归缩进
std::string CompoundExpression::toTreeString(int indent) const {
    // std::string res = std::string(indent, ' ') + "Exp " + m_operator + "\n";
    std::string res = std::string(indent, ' ') + m_operator + "\n";
    res += m_left->toTreeString(indent + 4);
    res += m_right->toTreeString(indent + 4);
    return res;
}

void CompoundExpression::collectVarUses(std::map<std::string, int> &counter) const {
    // 左右表达式递归计数
    if (m_left) {
        m_left->collectVarUses(counter);
    }
    if (m_right) {
        m_right->collectVarUses(counter);
    }
}

const std::string& CompoundExpression::getOp() const noexcept {
    return m_operator;
}

const Expression* CompoundExpression::getLeft() const noexcept {
    return m_left.get();
}

const Expression* CompoundExpression::getRight() const noexcept {
    return m_right.get();
}