// https://en.wikipedia.org/wiki/Shunting-yard_algorithm

sclass ShuntingYardParser is Steppable {
  LS tok;
  int iTok = 1;
  
  int iLiteralStart;
  new LS operatorStack;
  new LS outputQueue;
  
  *() {}
  *(S s) { this(javaTok(s)); }
  *(LS *tok) {}
  
  run { stepAll(this); }
  
  public bool step() {
    if (iTok >= l(tok)) {
      finishLiteral();
      while (nempty(operatorStack)) {
        var o = popLast(operatorStack);
        assertNequals(o, "(");
        outputQueue.add(o);
      }
      false;
    }
    
    S t = tok.get(iTok);

    if (eq(t, "(")) {
      finishLiteral();
      operatorStack.add(t);
    } else if (eq(t, ")")) {
      finishLiteral();
      while (!eq(last(operatorStack), "(")) {
        assertNempty(operatorStack);
        outputQueue.add(popLast(operatorStack));
      }
      popLast(operatorStack);
    } else if (!startsWithLetterOrDigit(t) && !eq(t, ".")) {
      // assume it's an operator
      finishLiteral();
      S o1 = t, o2;
      while (!eqOneOf(o2 = last(operatorStack), "(", null)
        && (precedence(o2) > precedence(o1)
        ||  precedence(o2) == precedence(o1) && isLeftAssociative(o1)))
          outputQueue.add(popLast(operatorStack));

      operatorStack.add(o1);
    } else if (iLiteralStart == 0)
      iLiteralStart = iTok;
    
     iTok += 2;
   true;
  }
  
  int precedence(S op) { ret 0; }
  bool isLeftAssociative(S op) { true; }
  
  void finishLiteral {
    if (iLiteralStart == 0) ret;
    outputQueue.add(joinSubList(tok, iLiteralStart, iTok-1));
    iLiteralStart = 0;
  }
}