// Core of a precedence- and parens-aware parser
// -operators are just strings to make things simpler
// 
sclass ShuntingYardCore {
  // Result computation in Reverse Polish notation containing both
  // literals and operators
  new LS outputQueue;
  
  // used temporarily
  new LS operatorStack;
  
  // 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; }
  
  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));
        }
        
      operatorStack.add(o1);
    } else // it's a literal, add to outputqueue
      addToOutputQueue(t);
  }
}