// 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);
  }
}

Began life as a copy of #1032659