使用分流码算法的抽象语法树

Question

i有一个infix表达式，我已经将其化为象征性，并希望继续创建一个抽象的语法树。我了解在这些情况下使用的分流码算法。我只找到了将infix表达式转换为RPN格式而不是AST的方法。我可以先创建RPN版本，然后从中创建AST，但似乎不必要。

我选择的语言是JavaScript，尽管我只需要以任何语言和/或算法的描述看到一个示例。我已经浏览了《龙书》和《特伦斯·帕尔的书》，但都没有给我寻找答案。

Answer 1

请参阅用DART编写的简化版本，同时产生RPN和AST。来自Wikipedia的使用伪代码用于实施。

这是对算法的不错的视觉解释。

尝试一下

void main() {
  final ast = shunting('(2*3*x+5*y-3*z)/(1+3+2*2)'.split(''), 'xyz'.split(''));
  print(ast);
}
/// imm - immediate value
Ast shunting(
  List<String> body,
  List<String> arguments,
) {
  final tree = <Ast>[];
  final outputQueue = <String>[];
  final operatorStack = <String>[];
  for (final token in body) {
    if (int.tryParse(token) is int) {
      final operand = UnOp('imm', int.parse(token));
      outputQueue.add(token);
      tree.add(operand);
    } else if (arguments.contains(token)) {
      final operand = UnOp('arg', arguments.indexOf(token));
      outputQueue.add(token);
      tree.add(operand);
    } else if (token.isOperator) {
      while (operatorStack.isNotEmpty && (operatorStack.last > token || operatorStack.last.isSamePrecedence(token))) {
        final lastOp = operatorStack.removeLast();
        outputQueue.add(lastOp);
        final second = tree.removeLast();
        final first = tree.removeLast();
        tree.add(BinOp(lastOp, first, second));
      }
      operatorStack.add(token);
    } else if (token == '(') {
      operatorStack.add(token);
    } else if (token == ')') {
      assert(operatorStack.isNotEmpty, 'mismatched parenthesis');
      while (operatorStack.last != '(') {
        final lastOp = operatorStack.removeLast();
        outputQueue.add(lastOp);
        final second = tree.removeLast();
        final first = tree.removeLast();
        tree.add(BinOp(lastOp, first, second));
      }
      operatorStack.removeLast();
    }
  }
  while (operatorStack.isNotEmpty) {
    final lastOp = operatorStack.removeLast();
    outputQueue.add(lastOp);
    final second = tree.removeLast();
    final first = tree.removeLast();
    tree.add(BinOp(lastOp, first, second));
  }
  print('RPN: ${outputQueue.join()}');
  return tree.first;
}
abstract class Ast {
  abstract final String op;
}
class BinOp implements Ast {
  BinOp(
    this.op,
    this._a,
    this._b,
  );
  final Ast _a;
  final Ast _b;
  @override
  final String op;
  Ast a(Ast a) => _a;
  Ast b(Ast b) => _b;
  @override
  String toString() => '{op: $op, a: $_a, b: $_b}';
}
class UnOp implements Ast {
  UnOp(this.op, this.n);
  final int n;
  @override
  final String op;
  @override
  String toString() => '{op: $op, n: $n}';
}
extension Operators on String {
  bool operator >(Object other) {
    assert(other is String, 'Incompatible type comparison');
    return '*/'.split('').contains(this) && '+-'.split('').contains(other);
  }
  bool operator <(Object other) {
    assert(other is String, 'Incompatible type comparison');
    return '-+'.split('').contains(this) && '*/'.split('').contains(other);
  }
  bool get isOperator => '*/+-'.split('').contains(this);
  bool isSamePrecedence(Object other) {
    assert(other is String, 'Incompatible type comparison');
    if ('+-'.split('').contains(this) && '+-'.split('').contains(other)) return true;
    if ('/*'.split('').contains(this) && '/*'.split('').contains(other)) return true;
    return false;
  }
}