shuntingYard method

Implementation

List<Token> shuntingYard(List<Token> stream) {
  if (stream.isEmpty) {
    throw FormatException('The given tokenStream was empty.');
  }

  final List<Token> outputStream = <Token>[];
  final List<Token> operatorBuffer = <Token>[];

  Token? prevToken;

  for (Token curToken in stream) {
    // If the current Token is a value or a variable, put them into the output stream.
    if (curToken.type == TokenType.VAL || curToken.type == TokenType.VAR) {
      outputStream.add(curToken);
      prevToken = curToken;
      continue;
    }

    // If the current Token is a function, put it onto the operator stack.
    if (curToken.type.function) {
      curToken.argCount = 1;
      operatorBuffer.add(curToken);
      prevToken = curToken;
      continue;
    }

    /*
     *  If the current Token is a function argument separator, pop operators
     *  to output stream until a left brace is encountered.
     */
    if (curToken.type == TokenType.SEPAR) {
      while (operatorBuffer.isNotEmpty &&
          operatorBuffer.last.type != TokenType.LBRACE) {
        outputStream.add(operatorBuffer.removeLast());
      }

      if (operatorBuffer.length > 1) {
        var func = operatorBuffer[operatorBuffer.length - 2];
        if (func.type.function) {
          ++func.argCount;
        }
      }

      // If no left brace is encountered, separator was misplaced or parenthesis mismatch
      if (operatorBuffer.isNotEmpty &&
          operatorBuffer.last.type != TokenType.LBRACE) {
        //TODO never reached, check this.
        throw FormatException(
            'Misplaced separator or mismatched parenthesis.');
      }
      prevToken = curToken;
      continue;
    }

    /* if the current Tokens type is PLUS or MINUS and the previous Token is an operator or type LBRACE
     * or we're at the beginning of the expression (prevToken == null) the current Token is
     * an unary plur or minus, so the tokentype has to be changed.
     */
    if ((curToken.type == TokenType.MINUS ||
            curToken.type == TokenType.PLUS) &&
        (prevToken == null ||
            prevToken.type.operator ||
            prevToken.type == TokenType.SEPAR ||
            prevToken.type == TokenType.LBRACE)) {
      final Token newToken = Token(
          curToken.text,
          curToken.type == TokenType.MINUS
              ? TokenType.UNMINUS
              : TokenType.UNPLUS);
      operatorBuffer.add(newToken);
      prevToken = newToken;
      continue;
    }

    /*
     * If the current token is an operator and it's priority is lower than the priority of the last
     * operator in the operator buffer, than put the operators from the operator buffer into the output
     * stream until you find an operator with a priority lower or equal as the current tokens.
     * Then add the current Token to the operator buffer.
     */
    if (curToken.type.operator) {
      while (operatorBuffer.isNotEmpty &&
          ((curToken.type.leftAssociative &&
                  curToken.type.priority <=
                      operatorBuffer.last.type.priority) ||
              (!curToken.type.leftAssociative &&
                  curToken.type.priority <
                      operatorBuffer.last.type.priority))) {
        outputStream.add(operatorBuffer.removeLast());
      }
      operatorBuffer.add(curToken);
      prevToken = curToken;
      continue;
    }

    // If the current Token is a left brace, put it on the operator buffer.
    if (curToken.type == TokenType.LBRACE) {
      operatorBuffer.add(curToken);
      prevToken = curToken;
      continue;
    }

    // If the current Token is a right brace, empty the operator buffer until you find a left brace.
    if (curToken.type == TokenType.RBRACE) {
      while (operatorBuffer.isNotEmpty &&
          operatorBuffer.last.type != TokenType.LBRACE) {
        outputStream.add(operatorBuffer.removeLast());
      }

      // Expect next token on stack to be left parenthesis and pop it
      if (operatorBuffer.isEmpty ||
          operatorBuffer.removeLast().type != TokenType.LBRACE) {
        throw FormatException('Mismatched parenthesis.');
      }

      // If the token at the top of the stack is a function token, pop it onto the output queue.
      if (operatorBuffer.isNotEmpty && operatorBuffer.last.type.function) {
        outputStream.add(operatorBuffer.removeLast());
      }
    }
    prevToken = curToken;
  }

  /*
   * When the algorithm reaches the end of the input stream, we add the
   * tokens in the operatorBuffer to the outputStream. If the operator
   * on top of the stack is a parenthesis, there are mismatched parenthesis.
   */
  while (operatorBuffer.isNotEmpty) {
    if (operatorBuffer.last.type == TokenType.LBRACE ||
        operatorBuffer.last.type == TokenType.RBRACE) {
      throw FormatException('Mismatched parenthesis.');
    }
    outputStream.add(operatorBuffer.removeLast());
  }

  return outputStream;
}