Parsing/Shunting-yard algorithm: Difference between revisions
Add Scala implementation
(Improved and adapted to Swift 5.7) |
(Add Scala implementation) |
||
| (5 intermediate revisions by 3 users not shown) | |||
Line 4,311:
input: ) (
RPN──► ─────── error in expression ───────
</pre>
=={{header|RPL}}==
≪ "§" + → expression
≪ { }
1 expression SIZE '''FOR''' j
DUP TYPE NOT <span style="color:grey">@ 1 if a number is in top-stack position</span>
expression j DUP SUB
'''IF''' "0123456789" OVER POS '''THEN'''
STR→
'''IF''' SWAP '''THEN''' SWAP 10 * + '''END'''
'''ELSE'''
'''IF''' SWAP '''THEN''' ROT ROT + SWAP '''END'''
'''IF''' "^*/+-()" OVER POS '''THEN''' + '''ELSE''' DROP '''END'''
'''END'''
'''NEXT'''
≫ ≫ ‘<span style="color:blue">LEXER</span>’ STO <span style="color:grey">@ ( "1+(2*3)" → { 1 "+" "(" 2 "*" 3 ")" } )</span>
≪ '''IF''' OVER '''THEN'''
"^*/+-" DUP 5 PICK POS SWAP ROT POS
{ 4 3 3 2 2 } { 1 0 0 0 0 }
→ o2 o1 prec rasso
≪ '''IF''' o2 '''THEN'''
prec o1 GET prec o2 GET
'''IF''' rasso o1 GET '''THEN''' < '''ELSE''' ≤ '''END'''
'''ELSE''' 0 '''END'''
≫
'''ELSE''' DROP 0 '''END'''
≫ ‘<span style="color:blue">POPOP?</span>’ STO <span style="color:grey">@ ( op → Boolean )</span>
≪ <span style="color:blue">LEXER</span> { } "" → infix postfix token
≪ 0
1 infix SIZE '''FOR''' j
infix j GET 'token' STO
1 SF
'''CASE'''
"^*/+-" token →STR POS '''THEN'''
1 CF
'''WHILE''' token <span style="color:blue">POPOP?</span> '''REPEAT'''
'postfix' ROT STO+ 1 - '''END'''
token SWAP 1 + '''END'''
"(" token == '''THEN'''
token SWAP 1 + '''END'''
")" token == '''THEN'''
'''WHILE''' DUP 1 FS? AND '''REPEAT'''
'''IF''' OVER "(" ≠ '''THEN'''
'postfix' ROT STO+
'''ELSE''' SWAP DROP 1 CF '''END'''
1 -
'''END'''
'''END'''
1 FS? '''THEN''' 'postfix' token STO+ '''END'''
'''END'''
'''NEXT'''
'''WHILE''' DUP '''REPEAT'''
'postfix' ROT STO+
1 - '''END'''
DROP ""
1 postfix SIZE '''FOR''' j
postfix j GET + " " + '''NEXT'''
≫ ≫ ‘<span style="color:blue">→RPN<span>’ STO
"3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3" <span style="color:blue">→RPN<span>
{{out}}
<pre>
1: "3 4 2 * 1 5 - 2 3 ^ ^ / + "
</pre>
Line 4,500 ⟶ 4,566:
calculate(postfix_tokens)
}</syntaxhighlight>
=={{header|Scala}}==
{{trans|Java}}
<syntaxhighlight lang="Scala">
import scala.util.control.Breaks._
object ShuntingYard {
def main(args: Array[String]): Unit = {
val infix = "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3"
println(s"infix: $infix")
println(s"postfix: ${infixToPostfix(infix)}")
}
def infixToPostfix(infix: String): String = {
val ops = "-+/*^"
val sb = new StringBuilder
val s = scala.collection.mutable.Stack[Int]()
infix.split("\\s").foreach { token =>
if (token.nonEmpty) {
val c = token.head
val idx = ops.indexOf(c)
if (idx != -1) {
if (s.isEmpty) s.push(idx)
else {
breakable({
while (s.nonEmpty) {
val prec2 = s.top / 2
val prec1 = idx / 2
if (prec2 > prec1 || (prec2 == prec1 && c != '^')) sb.append(ops(s.pop)).append(' ')
else break
}
});
s.push(idx)
}
} else if (c == '(') {
s.push(-2) // -2 stands for '('
} else if (c == ')') {
// until '(' on stack, pop operators.
while (s.top != -2) sb.append(ops(s.pop)).append(' ')
s.pop()
} else {
sb.append(token).append(' ')
}
}
}
while (s.nonEmpty) sb.append(ops(s.pop)).append(' ')
sb.toString
}
}
</syntaxhighlight>
{{out}}
<pre>
infix: 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
postfix: 3 4 2 * 1 5 - 2 3 ^ ^ / +
</pre>
=={{header|Sidef}}==
Line 5,419 ⟶ 5,545:
{{libheader|Wren-seq}}
{{libheader|Wren-pattern}}
<syntaxhighlight lang="
import "./pattern" for Pattern
/* To find out the precedence, we take the index of the
Line 5,681 ⟶ 5,807:
Output:
3 4 2 * 1 5 - 2 3 ^ ^ / +</pre>
=={{header|XPL0}}==
<syntaxhighlight lang "XPL0">int Stack(10);
int SP; \stack pointer
proc Push(N);
int N;
[Stack(SP):= N; SP:= SP+1];
func Pop;
[SP:= SP-1; return Stack(SP)];
func Precedence(Op);
int Op;
case Op of
^+, ^-: return 2;
^*, ^/: return 3;
^^: return 4
other [];
proc ShowStack;
int I;
[ChOut(0, 9\tab\);
for I:= 0 to SP-1 do
[ChOut(0, Stack(I)); ChOut(0, ^ )];
CrLf(0);
];
char Str;
int Token, Op1, Op2;
[Str:= "3 + 4 * 2 / ( 1 - 5 ) ^^ 2 ^^ 3 ";
SP:= 0;
Text(0, "Input Output Stack^m^j");
loop [repeat Token:= Str(0); Str:= Str+1;
until Token # ^ ; \skip space characters
if Token # $A0 \terminating space\ then
[ChOut(0, Token); ChOut(0, 9\tab\)];
case Token of
^+, ^-, ^*, ^/, ^^:
[Op1:= Token;
loop [if SP <= 0 then quit; \empty
Op2:= Stack(SP-1);
if Op2 = ^( then quit;
if Precedence(Op2) < Precedence(Op1) then quit;
if Precedence(Op2) = Precedence(Op1) then
if Op1 = ^^ then quit;
ChOut(0, Pop);
];
Push(Op1);
];
^(: Push(Token);
^): [while SP > 0 and Stack(SP-1) # ^( do
ChOut(0, Pop);
Pop; \discard left parenthesis
];
$A0: quit \terminating space with MSB set
other ChOut(0, Token); \print single digit number
ShowStack;
];
while SP > 0 do \print any remaining operators
[ChOut(0, 9\tab\);
ChOut(0, Pop);
ShowStack;
];
]</syntaxhighlight>
{{out}}
<pre>
Input Output Stack
3 3
+ +
4 4 +
* + *
2 2 + *
/ * + /
( + / (
1 1 + / (
- + / ( -
5 5 + / ( -
) - + /
^ + / ^
2 2 + / ^
^ + / ^ ^
3 3 + / ^ ^
^ + / ^
^ + /
/ +
+
</pre>
=={{header|zkl}}==
| |||