// 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;
      ifdef ShuntingYardParser_debug
        printVars(+o1, +operatorStack);
      endifdef
      while (!eqOneOf(o2 = last(operatorStack), "(", null)
        && (precedence(o2) > precedence(o1)
        ||  precedence(o2) == precedence(o1) && isLeftAssociative(o1))) {
          ifdef ShuntingYardParser_debug
            print("popLast");
          endifdef
          outputQueue.add(popLast(operatorStack));
        }
        
      S prev = _get(tok, iTok-2);
      int prec = precedence(prev);
      bool unary = eqOneOf(prev, null, ")") || prec >= precedence(o1);
      operatorStack.add(unary ? "u" + o1 : o1);
    } else if (iLiteralStart == 0)
      iLiteralStart = iTok;
    
     iTok += 2;
   true;
  }
  
  // return 0 for non-operator
  int precedence(S op) {
    if (eqOneOf(op, "*", "/")) ret 2;
    if (eqOneOf(op, "+", "-")) ret 1;
    ret 0;
  }
  bool isLeftAssociative(S op) { true; }
  
  void finishLiteral {
    if (iLiteralStart == 0) ret;
    outputQueue.add(joinSubList(tok, iLiteralStart, iTok-1));
    iLiteralStart = 0;
  }
  
  // returns list that can be processed with CalcRPN
  LS get() {
    run();
    ret outputQueue;
  }
}