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

sclass ShuntingYardParser is Steppable {
  // input
  LS tok;
  int iTok = 1;
  
  // output
  new LS outputQueue;
  
  // transitional
  int iLiteralStart;
  new LS operatorStack;
  S lastNonSpacer;
  
  *() {}
  *(S s) { this(noTok(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);
    bool op = isOperator(t), space = isSpacer(t);
    if (op && space) warn("Operators should not be spacers");
    
    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 (op) {
      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 lastTokenProcessed = lastNonSpacer;      
      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 ? "u" + o1 : o1);
    } else if (iLiteralStart == 0)
      iLiteralStart = iTok;
    
    iTok += 2;
     
    if (!space) lastNonSpacer = t;

    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; }
  
  bool isSpacer(S t) {
    ret emptyAfterTrim(t);
  }
  
  bool isOperator(S t) {
    ret !isSpacer(t)
      && !startsWithLetterOrDigit(t) && !eq(t, ".");
  }
  
  void finishLiteral {
    if (iLiteralStart == 0) ret;
    S s = joinSubList(tok, iLiteralStart, iTok-1);
    if (!isSpacer(s))
      outputQueue.add(s);
    iLiteralStart = 0;
  }
  
  // returns list that can be processed with CalcRPN
  LS get() {
    run();
    ret outputQueue;
  }
}