mathtool2/lib/expr_parse.dart

/// 把 Symja 语法的表达式文本解析成节点树。
///
/// 用途是**粘贴**：计算器的输入是结构化的，从剪贴板进来的却是一串文本，
/// 得先转成树才能继续用按钮编辑。
///
/// 设计原则：**只解析一个明确的子集，遇到不认识的东西就明确报错，绝不猜。**
/// 猜错了用户看到的是算错的答案，比直接报错糟糕得多。
///
/// 支持的语法：
///   数字（含小数与 `1e-3` 科学计数法）
///   `+ - * / ^`、一元负号、并置乘法（`2x`、`2(x+1)`）
///   `Name[...]`、`( … )`、`{ … }`
///   `-> == :=`（当普通运算符节点）
///   标识符可以带 `_` 和 `$`（`x_`、`$ans`）
///
/// 不支持（会报错）：`@ /;; & 过长的上下文反引号` 等等。
library;

import 'expr_node.dart';

/// 解析失败。带上出错位置，方便定位。
class ExprParseException implements Exception {
  final String message;
  final int position;
  const ExprParseException(this.message, this.position);

  @override
  String toString() => position >= 0 ? '第 ${position + 1} 个字符：$message' : message;
}

/// 解析成功返回根槽；失败抛 [ExprParseException]。
SeqNode parseSymjaExpr(String source) => _Parser(source).parse();

class _Parser {
  final String src;
  int i = 0;

  _Parser(this.src);

  bool get _eof => i >= src.length;
  String get _cur => src[i];

  void _ws() {
    while (!_eof && const {' ', '\t', '\n', '\r'}.contains(_cur)) {
      i++;
    }
  }

  void _expect(String ch) {
    _ws();
    if (_eof) throw ExprParseException('表达式不完整，缺少「$ch」', i);
    if (_cur != ch) throw ExprParseException('期望「$ch」，实际是「$_cur」', i);
    i++;
  }

  SeqNode parse() {
    final seq = SeqNode(_expr());
    _ws();
    if (!_eof) {
      throw ExprParseException('多余的内容「${src.substring(i)}」', i);
    }
    return seq;
  }

  // ---------------------------------------------------------------- 加减层
  //
  // 树里没有"加法节点"——加减乘都是序列里的字面量运算符，优先级交给 Symja
  // 求值时处理。只有 / 和 ^ 做成结构（分式、幂），因为它们要竖排/上标显示。

  List<ExprNode> _expr() {
    final out = <ExprNode>[..._term()];
    while (true) {
      _ws();
      if (_eof) break;

      // 多字符运算符要先判，否则 `x->0` 会被当成 `x` 减 `>0`
      if (src.startsWith('->', i)) {
        i += 2;
        out.add(LitNode('->'));
        out.addAll(_term());
      } else if (src.startsWith('==', i)) {
        i += 2;
        out.add(LitNode('=='));
        out.addAll(_term());
      } else if (src.startsWith(':=', i)) {
        i += 2;
        out.add(LitNode(':='));
        out.addAll(_term());
      } else if (_cur == '+' || _cur == '-') {
        out.add(LitNode(_cur));
        i++;
        out.addAll(_term());
      } else {
        break;
      }
    }
    return out;
  }

  // ---------------------------------------------------------------- 乘除层

  List<ExprNode> _term() {
    var out = <ExprNode>[..._unary()];
    while (true) {
      _ws();
      if (_eof) break;

      if (_cur == '*') {
        i++;
        out = [...out, LitNode('*'), ..._unary()];
      } else if (_cur == '/') {
        i++;
        out = [
          FracNode(num: SeqNode(out), den: SeqNode(_unary())),
        ];
      } else if (_startsValue(_cur)) {
        // 并置即乘法：2x、2(x+1)。不插 `*` 节点 —— 序列化出来还是 `2x`，
        // Symja 认这个写法，而且用户看到的和打进去的一样。
        out = [...out, ..._unary()];
      } else {
        break;
      }
    }
    return out;
  }

  bool _startsValue(String c) =>
      _isDigit(c) || c == '.' || _isIdentStart(c) || c == '(' || c == '{';

  // ---------------------------------------------------------------- 一元 / 幂

  List<ExprNode> _unary() {
    _ws();
    if (_eof) throw ExprParseException('表达式不完整', i);
    if (_cur == '-') {
      i++;
      return [LitNode('-'), ..._unary()];
    }
    if (_cur == '+') {
      i++;
      return _unary();
    }
    return _power();
  }

  List<ExprNode> _power() {
    final base = _primary();
    _ws();
    if (!_eof && _cur == '^') {
      i++;
      final exp = _unary(); // 右结合
      return [PowNode(base: SeqNode(base), exp: SeqNode(exp))];
    }
    return base;
  }

  // ---------------------------------------------------------------- 原子

  List<ExprNode> _primary() {
    _ws();
    if (_eof) throw ExprParseException('表达式不完整', i);
    final c = _cur;

    if (c == '(') {
      i++;
      final inner = _expr();
      _expect(')');
      return [GroupNode(SeqNode(inner))];
    }

    if (c == '{') {
      i++;
      // 花括号里是**逗号分隔的列表**（`{n, 1, Infinity}`），不是单个表达式。
      // 逗号当成字面量节点留着，序列化时拼回去。
      final inner = <ExprNode>[];
      _ws();
      if (!_eof && _cur != '}') {
        while (true) {
          if (inner.isNotEmpty) inner.add(LitNode(', '));
          inner.addAll(_expr());
          _ws();
          if (!_eof && _cur == ',') {
            i++;
            continue;
          }
          break;
        }
      }
      _expect('}');
      return [BraceNode(SeqNode(inner))];
    }

    if (_isDigit(c) || c == '.') return [LitNode(_number())];

    // `%` 是 Symja 的"上一次结果"，编辑框里统一显示成 ANS
    if (c == '%') {
      i++;
      return [const LitNode('%', display: 'ANS')];
    }

    if (_isIdentStart(c)) {
      final name = _ident();
      _ws();
      if (!_eof && _cur == '[') {
        i++;
        final args = _args();
        _expect(']');
        // ∫ / ∑ / ∏ / lim 的习惯写法认成大运算符，这样复制→粘贴能闭环
        final big = _tryBigOp(name, args);
        return [big ?? FuncNode(name, args)];
      }
      return [LitNode(name)];
    }

    throw ExprParseException('看不懂的字符「$c」', i);
  }

  /// 认得出来就返回大运算符节点，认不出返回 null（交给普通的 FuncNode）。
  static ExprNode? _tryBigOp(String name, List<SeqNode> args) {
    if (args.length != 2) return null;

    if (name == 'Limit') {
      // Limit[f, x -> v]
      final parts = _splitTopLevel(args[1], '->');
      if (parts == null) return null;
      return BigOpNode(
        kind: 'Limit',
        body: args[0],
        variable: parts[0],
        lower: parts[1],
        upper: SeqNode(),
      );
    }

    if (name != 'Integrate' && name != 'Sum' && name != 'Product') return null;

    // Integrate[f, x] —— 不定积分，没有上下限
    if (args[1].children.length != 1 || args[1].children.first is! BraceNode) {
      return BigOpNode(
        kind: name,
        body: args[0],
        variable: args[1],
        lower: SeqNode(),
        upper: SeqNode(),
      );
    }

    // Integrate[f, {x, a, b}]
    final inner = (args[1].children.first as BraceNode).inner;
    final parts = _splitTopLevel(inner, ',');
    if (parts == null || parts.length != 3) return null;
    return BigOpNode(
      kind: name,
      body: args[0],
      variable: parts[0],
      lower: parts[1],
      upper: parts[2],
    );
  }

  /// 按顶层出现的 [sep] 字面量把槽切开。没出现就返回 null。
  ///
  /// 逗号在嵌套结构里（比如 `{Sin[x, y], 1}` 的内层）不算 —— 这里的
  /// 子节点本来就是树，所以"顶层"天然成立。
  static List<SeqNode>? _splitTopLevel(SeqNode seq, String sep) {
    final hits = <int>[
      for (var k = 0; k < seq.children.length; k++)
        if (seq.children[k] is LitNode &&
            ((seq.children[k] as LitNode).text == sep ||
                (seq.children[k] as LitNode).text == '$sep '))
          k,
    ];
    if (hits.isEmpty) return null;
    if (hits.length == 1 && sep == '->') {
      final k = hits.first;
      return [
        SeqNode(seq.children.sublist(0, k)),
        SeqNode(seq.children.sublist(k + 1)),
      ];
    }
    if (sep != ',') return null;

    final out = <SeqNode>[];
    var start = 0;
    for (final k in hits) {
      out.add(SeqNode(seq.children.sublist(start, k)));
      start = k + 1;
    }
    out.add(SeqNode(seq.children.sublist(start)));
    return out;
  }

  List<SeqNode> _args() {
    final out = <SeqNode>[];
    _ws();
    if (!_eof && _cur == ']') return out; // Sin[] 这种空参数

    while (true) {
      final nodes = _expr();
      // 空槽序列化出来是 Null；解析时还原成空槽，这样"复制→粘贴"能闭环
      final isNull = nodes.length == 1 &&
          nodes.first is LitNode &&
          (nodes.first as LitNode).text == 'Null';
      out.add(isNull ? SeqNode() : SeqNode(nodes));

      _ws();
      if (!_eof && _cur == ',') {
        i++;
        continue;
      }
      break;
    }
    return out;
  }

  String _number() {
    final start = i;
    while (!_eof && (_isDigit(_cur) || _cur == '.')) {
      i++;
    }
    // 科学计数法
    if (!_eof && (_cur == 'e' || _cur == 'E')) {
      var k = i + 1;
      if (k < src.length && (src[k] == '+' || src[k] == '-')) k++;
      if (k < src.length && _isDigit(src[k])) {
        i = k;
        while (!_eof && _isDigit(_cur)) {
          i++;
        }
      }
    }
    return src.substring(start, i);
  }

  String _ident() {
    final start = i;
    while (!_eof && _isIdentPart(_cur)) {
      i++;
    }
    return src.substring(start, i);
  }
}

bool _isDigit(String c) {
  final u = c.codeUnitAt(0);
  return u >= 0x30 && u <= 0x39;
}

bool _isLetter(String c) {
  final u = c.codeUnitAt(0);
  return (u >= 0x41 && u <= 0x5A) || (u >= 0x61 && u <= 0x7A) || c == '√';
}

bool _isIdentStart(String c) => _isLetter(c) || c == '_' || c == r'$';

bool _isIdentPart(String c) => _isLetter(c) || _isDigit(c) || c == '_' || c == r'$';