toRPN function

List<Token<TokenType>> toRPN(List<Token<TokenType>> tokens, { ComputeContext context = const DefaultComputeContext(), })

An implementation of the Shunting-yard algorithm to turn the expression into reverse polish notation.

Based off of https://en.wikipedia.org/wiki/Shunting_yard_algorithm#The_algorithm_in_detail

Implementation

List<Token> toRPN(List<Token> tokens,
    {ComputeContext context = const DefaultComputeContext()}) {
  List<Token> operatorStack = [];
  List<Token> outputQueue = [];

  _log.finest('Before adding implicit multiplication: $tokens');
  tokens = _explicitMultiplications(context, tokens);
  _log.finest('After adding implicit multiplication: $tokens');

  for (int i = 0; i < tokens.length; i++) {
    final token = tokens.elementAt(i);

    switch (token.type) {
      case NumberTokenType _:
        {
          outputQueue.add(token);
        }
      case ConstantTokenType _:
        {
          outputQueue.add(token);
        }
      case FunctionTokenType _:
        {
          operatorStack.add(token);
        }
      case ModifierTokenType _:
        {
          outputQueue.add(token);
        }
      case OperatorTokenType _:
        {
          final o1 = token as OperatorToken;
          Token? o2 = operatorStack.lastOrNull;
          while (o2 is OperatorToken &&
              (o2.operator.precedence.priority >
                      o1.operator.precedence.priority ||
                  (o1.operator.precedence.priority ==
                          o2.operator.precedence.priority &&
                      o1.operator.isLeftAssociative))) {
            outputQueue.add(operatorStack.removeLast());
            o2 = operatorStack.lastOrNull;
          }
          operatorStack.add(o1);
        }
      case Comma _:
        {
          while (operatorStack.last.type is! OpeningBracket) {
            outputQueue.add(operatorStack.removeLast());
          }
        }
      case OpeningBracket _:
        {
          operatorStack.add(token);
        }
      case ClosingBracket _:
        {
          if (operatorStack.isEmpty) {
            throw ComputationError(ComputationStep.parsing,
                message: "Tried to close a bracket that was not opened",
                globalPosition: token.globalOffset);
          }
          while (operatorStack.last.type is! OpeningBracket) {
            outputQueue.add(operatorStack.removeLast());
          }
          // Remove the opening bracket
          operatorStack.removeLast();
          if (operatorStack.lastOrNull?.type is FunctionTokenType) {
            outputQueue.add(operatorStack.removeLast());
          }
        }
    }

    _log.finest(
        "Token: ${token.rawValue} Output: ${outputQueue.map((e) => e.rawValue).join(' ')} Operator stack: ${operatorStack.map((e) => e.rawValue).join(' ')}");
  }

  while (operatorStack.isNotEmpty) {
    if (operatorStack.last.type is OpeningBracket) {
      throw ComputationError(ComputationStep.parsing,
          message: "Tried to close a bracket that was not opened",
          globalPosition: operatorStack.last.globalOffset);
    }
    outputQueue.add(operatorStack.removeLast());
  }

  _log.finest("Output: ${outputQueue.map((e) => e.rawValue).join(' ')}");

  return outputQueue;
}