method shuntingYard

Source

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

  List<Token> outputStream = new List<Token>();
  List<Token> operatorBuffer = new List<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) {
      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.isEmpty && operatorBuffer.last.type != TokenType.LBRACE) {
        outputStream.add(operatorBuffer.removeLast());
      }
      // If no left brace is encountered, separator was misplaced or parenthesis mismatch
      if(!operatorBuffer.isEmpty && operatorBuffer.last.type != TokenType.LBRACE) {
        //TODO never reached, check this.
        throw new StateError('Misplaced separator or mismatched parenthesis.');
      }
      prevToken = curToken;
      continue;
    }

    /* if the current Tokens type is 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 minus, so the tokentype has to be changed.
     */
    if(curToken.type == TokenType.MINUS && (prevToken == null || prevToken.type.operator || prevToken.type == TokenType.LBRACE)) {
      Token newToken = new Token(curToken.text, TokenType.UNMINUS);
      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.isEmpty && ((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.isEmpty && 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 new StateError('Mismatched parenthesis.');
      }

      // If the token at the top of the stack is a function token, pop it onto the output queue.
      if (!operatorBuffer.isEmpty && 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.isEmpty) {
    if (operatorBuffer.last.type == TokenType.LBRACE ||
        operatorBuffer.last.type == TokenType.RBRACE) {
      throw new StateError('Mismatched parenthesis.');
    }
    outputStream.add(operatorBuffer.removeLast());
  }

  return outputStream;
}