Not logged in.  Login/Logout/Register | List snippets | | Create snippet | Upload image | Upload data

90
LINES

< > BotCompany Repo | #1034914 // ShuntingYardCore - handles operator precences while parsing [OK]

JavaX fragment (include) [tags: use-pretranspiled]

Libraryless. Click here for Pure Java version (7867L/44K).

1  
// Core of a precedence- and parens-aware parser
2  
// -operators are just strings to make things simpler
3  
// -supports binary operators (left- or right-associative)
4  
//  and unary (prefix) operators
5  
6  
// To use:
7  
8  
// -Override/swap the required methods to define operators etc
9  
// -call handleToken on every token in the input
10  
// -call handleEOT
11  
// -use the outputQueue for computation
12  
13  
sclass ShuntingYardCore {
14  
  // Result computation in Reverse Polish notation containing both
15  
  // literals and operators
16  
  settable new LS outputQueue;
17  
  
18  
  // used temporarily
19  
  new LS operatorStack;
20  
  S lastTokenProcessed;
21  
  
22  
  // Override this if you have your own output queue
23  
  swappable void addToOutputQueue(S opOrLiteral) {
24  
    outputQueue.add(opOrLiteral);
25  
  }
26  
  
27  
  // Override this to define what an operator is
28  
  swappable bool isOperator(S token) { false; }
29  
  
30  
  // Override this to define operator precedence. op is always an operator
31  
  swappable int precedence(S op) { ret 1; }
32  
  
33  
  // Override this to make operators right-associative
34  
  swappable bool isLeftAssociative(S op) { true; }
35  
  
36  
  // Add some kind of marker to operator to mark it as unary
37  
  // (e.g. "-" => "u-")
38  
  swappable S convertOperatorToUnary(S op) { ret "u" + op; }
39  
  
40  
  static final S OP_PAREN = "(";
41  
  
42  
  void handleEOT() {
43  
    while (nempty(operatorStack)) {
44  
      var o = popLast(operatorStack);
45  
      assertNequals(o, OP_PAREN);
46  
      addToOutputQueue(o);
47  
    }
48  
  }
49  
50  
  void handleToken(S t) {
51  
    if (eq(t, "(")) {
52  
      operatorStack.add(OP_PAREN);
53  
    } else if (eq(t, ")")) {
54  
      while (!eq(last(operatorStack), OP_PAREN)) {
55  
        assertNempty(operatorStack);
56  
        outputQueue.add(popLast(operatorStack));
57  
      }
58  
      popLast(operatorStack);
59  
    } else if (isOperator(t)) {
60  
      S o1 = t, o2;
61  
      while (!eqOneOf(o2 = last(operatorStack), OP_PAREN, null)
62  
        && (precedence(o2) > precedence(o1)
63  
        ||  precedence(o2) == precedence(o1) && isLeftAssociative(o1))) {
64  
          outputQueue.add(popLast(operatorStack));
65  
        }
66  
        
67  
      // So we have parsed an operator - is it unary (prefix) or binary?
68  
      bool unary;
69  
      if (lastTokenProcessed == null)
70  
        unary = true; // operator is first token in stream - unary
71  
      else if (eq(lastTokenProcessed, "("))
72  
        unary = true; // directly after opening bracket - unary
73  
      else if (eq(lastTokenProcessed, ")"))
74  
        unary = false; // directly after closing bracket - binary
75  
      else if (!isOperator(lastTokenProcessed))
76  
        unary = false; // directly after literal - binary
77  
      else
78  
        unary = true; // directly after another operator - unary
79  
80  
      operatorStack.add(unary ? convertOperatorToUnary(o1) : o1);
81  
    } else // it's a literal, add to outputqueue
82  
      addToOutputQueue(t);
83  
      
84  
    lastTokenProcessed = t;
85  
  }
86  
  
87  
  bool isOperatorOrBracket(S t) {
88  
    ret eqOneOf(t, "(", ")") || isOperator(t);
89  
  }
90  
}

Author comment

Began life as a copy of #1032659

download  show line numbers  debug dex  old transpilations   

Travelled to 4 computer(s): bhatertpkbcr, ekrmjmnbrukm, mowyntqkapby, mqqgnosmbjvj

No comments. add comment

Snippet ID: #1034914
Snippet name: ShuntingYardCore - handles operator precences while parsing [OK]
Eternal ID of this version: #1034914/14
Text MD5: 002f17ae240c5d9cbfee4f6fb6272a15
Transpilation MD5: b9183940b58fa1e0302c208593664338
Author: stefan
Category: javax
Type: JavaX fragment (include)
Public (visible to everyone): Yes
Archived (hidden from active list): No
Created/modified: 2022-04-08 18:40:08
Source code size: 2983 bytes / 90 lines
Pitched / IR pitched: No / No
Views / Downloads: 142 / 261
Version history: 13 change(s)
Referenced in: [show references]