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 | } |
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] |