Libraryless. Click here for Pure Java version (9315L/51K).
1 | // https://en.wikipedia.org/wiki/Shunting-yard_algorithm |
2 | |
3 | sclass ShuntingYardParser is Steppable {
|
4 | // input |
5 | LS tok; |
6 | int iTok = 1; |
7 | |
8 | // output |
9 | new LS outputQueue; |
10 | |
11 | // transitional |
12 | int iLiteralStart; |
13 | new LS operatorStack; |
14 | S lastNonSpacer; |
15 | |
16 | *() {}
|
17 | *(S s) { this(noTok(s)); }
|
18 | *(LS *tok) {}
|
19 | |
20 | run { stepAll(this); }
|
21 | |
22 | public bool step() {
|
23 | if (iTok >= l(tok)) {
|
24 | finishLiteral(); |
25 | while (nempty(operatorStack)) {
|
26 | var o = popLast(operatorStack); |
27 | assertNequals(o, "(");
|
28 | outputQueue.add(o); |
29 | } |
30 | false; |
31 | } |
32 | |
33 | S t = tok.get(iTok); |
34 | bool op = isOperator(t), space = isSpacer(t); |
35 | if (op && space) warn("Operators should not be spacers");
|
36 | |
37 | if (eq(t, "(")) {
|
38 | finishLiteral(); |
39 | operatorStack.add(t); |
40 | } else if (eq(t, ")")) {
|
41 | finishLiteral(); |
42 | while (!eq(last(operatorStack), "(")) {
|
43 | assertNempty(operatorStack); |
44 | outputQueue.add(popLast(operatorStack)); |
45 | } |
46 | popLast(operatorStack); |
47 | } else if (op) {
|
48 | finishLiteral(); |
49 | S o1 = t, o2; |
50 | ifdef ShuntingYardParser_debug |
51 | printVars(+o1, +operatorStack); |
52 | endifdef |
53 | while (!eqOneOf(o2 = last(operatorStack), "(", null)
|
54 | && (precedence(o2) > precedence(o1) |
55 | || precedence(o2) == precedence(o1) && isLeftAssociative(o1))) {
|
56 | ifdef ShuntingYardParser_debug |
57 | print("popLast");
|
58 | endifdef |
59 | outputQueue.add(popLast(operatorStack)); |
60 | } |
61 | |
62 | S lastTokenProcessed = lastNonSpacer; |
63 | bool unary; |
64 | if (lastTokenProcessed == null) |
65 | unary = true; // operator is first token in stream - unary |
66 | else if (eq(lastTokenProcessed, "("))
|
67 | unary = true; // directly after opening bracket - unary |
68 | else if (eq(lastTokenProcessed, ")")) |
69 | unary = false; // directly after closing bracket - binary |
70 | else if (!isOperator(lastTokenProcessed)) |
71 | unary = false; // directly after literal - binary |
72 | else |
73 | unary = true; // directly after another operator - unary |
74 | |
75 | operatorStack.add(unary ? "u" + o1 : o1); |
76 | } else if (iLiteralStart == 0) |
77 | iLiteralStart = iTok; |
78 | |
79 | iTok += 2; |
80 | |
81 | if (!space) lastNonSpacer = t; |
82 | |
83 | true; |
84 | } |
85 | |
86 | // return 0 for non-operator |
87 | int precedence(S op) {
|
88 | if (eqOneOf(op, "*", "/")) ret 2; |
89 | if (eqOneOf(op, "+", "-")) ret 1; |
90 | ret 0; |
91 | } |
92 | bool isLeftAssociative(S op) { true; }
|
93 | |
94 | bool isSpacer(S t) {
|
95 | ret emptyAfterTrim(t); |
96 | } |
97 | |
98 | bool isOperator(S t) {
|
99 | ret !isSpacer(t) |
100 | && !startsWithLetterOrDigit(t) && !eq(t, "."); |
101 | } |
102 | |
103 | void finishLiteral {
|
104 | if (iLiteralStart == 0) ret; |
105 | S s = joinSubList(tok, iLiteralStart, iTok-1); |
106 | if (!isSpacer(s)) |
107 | outputQueue.add(s); |
108 | iLiteralStart = 0; |
109 | } |
110 | |
111 | // returns list that can be processed with CalcRPN |
112 | LS get() {
|
113 | run(); |
114 | ret outputQueue; |
115 | } |
116 | } |
download show line numbers debug dex old transpilations
Travelled to 3 computer(s): bhatertpkbcr, mowyntqkapby, mqqgnosmbjvj
No comments. add comment
| Snippet ID: | #1032659 |
| Snippet name: | ShuntingYardParser [parses things like "1+2*(3-4)"] - simple parser with priorities |
| Eternal ID of this version: | #1032659/27 |
| Text MD5: | 4b3e4c4d7297f457ef437ceed16b70df |
| Transpilation MD5: | 124601defb683163c84c37fe87651bdd |
| 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:36:06 |
| Source code size: | 3038 bytes / 116 lines |
| Pitched / IR pitched: | No / No |
| Views / Downloads: | 138 / 324 |
| Version history: | 26 change(s) |
| Referenced in: | [show references] |