// Core of a precedence- and parens-aware parser

// -operators are just strings to make things simpler

// -supports binary operators (left- or right-associative)

//  and unary (prefix) operators

// To use:

// -Override/swap the required methods to define operators etc

// -call handleToken on every token in the input

// -call handleEOT

// -use the outputQueue for computation

sclass ShuntingYardCore {

  // Result computation in Reverse Polish notation containing both

  // literals and operators

  settable new LS outputQueue;

  // used temporarily

  new LS operatorStack;

  S lastTokenProcessed;

  // Override this if you have your own output queue

  swappable void addToOutputQueue(S opOrLiteral) {

    outputQueue.add(opOrLiteral);

  }

  // Override this to define what an operator is

  swappable bool isOperator(S token) { false; }

  // Override this to define operator precedence. op is always an operator

  swappable int precedence(S op) { ret 1; }

  // Override this to make operators right-associative

  swappable bool isLeftAssociative(S op) { true; }

  // Add some kind of marker to operator to mark it as unary

  // (e.g. "-" => "u-")

  swappable S convertOperatorToUnary(S op) { ret "u" + op; }

  static final S OP_PAREN = "(";

  void handleEOT() {

    while (nempty(operatorStack)) {

      var o = popLast(operatorStack);

      assertNequals(o, OP_PAREN);

      addToOutputQueue(o);

    }

  }

  void handleToken(S t) {

    if (eq(t, "(")) {

      operatorStack.add(OP_PAREN);

    } else if (eq(t, ")")) {

      while (!eq(last(operatorStack), OP_PAREN)) {

        assertNempty(operatorStack);

        outputQueue.add(popLast(operatorStack));

      }

      popLast(operatorStack);

    } else if (isOperator(t)) {

      S o1 = t, o2;

      while (!eqOneOf(o2 = last(operatorStack), OP_PAREN, null)

        && (precedence(o2) > precedence(o1)

        ||  precedence(o2) == precedence(o1) && isLeftAssociative(o1))) {

          outputQueue.add(popLast(operatorStack));

        }

      // So we have parsed an operator - is it unary (prefix) or binary?

      bool unary;

      if (lastTokenProcessed == null)

        unary = true; // operator is first token in stream - unary

      else if (eq(lastTokenProcessed, "("))

        unary = true; // directly after opening bracket - unary

      else if (eq(lastTokenProcessed, ")"))

        unary = false; // directly after closing bracket - binary

      else if (!isOperator(lastTokenProcessed))

        unary = false; // directly after literal - binary

      else

        unary = true; // directly after another operator - unary

      operatorStack.add(unary ? convertOperatorToUnary(o1) : o1);

    } else // it's a literal, add to outputqueue

      addToOutputQueue(t);

    lastTokenProcessed = t;

  }

  bool isOperatorOrBracket(S t) {

    ret eqOneOf(t, "(", ")") || isOperator(t);

  }

}