Parsing/Shunting-yard algorithm: Difference between revisions
Content added Content deleted
(Added Kotlin) |
mNo edit summary |
||
Line 2,453: | Line 2,453: | ||
<pre>infix: 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 |
<pre>infix: 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 |
||
postfix: 3 4 2 * 1 5 - 2 3 ^ ^ / + </pre> |
postfix: 3 4 2 * 1 5 - 2 3 ^ ^ / + </pre> |
||
=={{header|Julia}}== |
|||
Translation from the Wikipedia reference article's pseudocode. |
|||
<lang julia> |
|||
function parseinfix2rpn(s) |
|||
outputq = [] |
|||
opstack = [] |
|||
infix = split(s) |
|||
for tok in infix |
|||
if all(isnumber, tok) |
|||
push!(outputq, tok) |
|||
elseif tok == "(" |
|||
push!(opstack, tok) |
|||
elseif tok == ")" |
|||
while !isempty(opstack) && (op = pop!(opstack)) != "(" |
|||
push!(outputq, op) |
|||
end |
|||
else # operator |
|||
while !isempty(opstack) |
|||
op = pop!(opstack) |
|||
if Base.operator_precedence(Symbol(op)) > Base.operator_precedence(Symbol(tok)) || |
|||
(Base.operator_precedence(Symbol(op)) == |
|||
Base.operator_precedence(Symbol(tok)) && op != "^") |
|||
push!(outputq, op) |
|||
else |
|||
push!(opstack, op) # undo peek |
|||
break |
|||
end |
|||
end |
|||
push!(opstack, tok) |
|||
end |
|||
println("The working output stack is $outputq") |
|||
end |
|||
while !isempty(opstack) |
|||
if (op = pop!(opstack)) == "(" |
|||
throw("mismatched parentheses") |
|||
else |
|||
push!(outputq, op) |
|||
end |
|||
end |
|||
outputq |
|||
end |
|||
teststring = "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3" |
|||
println("\nResult: $teststring becomes $(join(parseinfix2rpn(teststring), ' '))") |
|||
</lang> |
|||
{{output}} |
|||
<pre> |
|||
The working output stack is Any["3"] |
|||
The working output stack is Any["3"] |
|||
The working output stack is Any["3", "4"] |
|||
The working output stack is Any["3", "4"] |
|||
The working output stack is Any["3", "4", "2"] |
|||
The working output stack is Any["3", "4", "2", "*"] |
|||
The working output stack is Any["3", "4", "2", "*"] |
|||
The working output stack is Any["3", "4", "2", "*", "1"] |
|||
The working output stack is Any["3", "4", "2", "*", "1"] |
|||
The working output stack is Any["3", "4", "2", "*", "1", "5"] |
|||
The working output stack is Any["3", "4", "2", "*", "1", "5", "-"] |
|||
The working output stack is Any["3", "4", "2", "*", "1", "5", "-"] |
|||
The working output stack is Any["3", "4", "2", "*", "1", "5", "-", "2"] |
|||
The working output stack is Any["3", "4", "2", "*", "1", "5", "-", "2"] |
|||
The working output stack is Any["3", "4", "2", "*", "1", "5", "-", "2", "3"] |
|||
Result: 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 becomes 3 4 2 * 1 5 - 2 3 ^ ^ / + |
|||
</pre> |
|||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |