Parsing/Shunting-yard algorithm: Difference between revisions
Content added Content deleted
(→{{header|OCaml}}: simplifiy implementation slightly by using list instead of queue, functions instead of hashtable) |
m (→{{header|Sidef}}: updated code) |
||
| Line 3,073: | Line 3,073: | ||
'-' => 2, |
'-' => 2, |
||
'(' => 1, |
'(' => 1, |
||
) |
) |
||
var assoc = Hash( |
var assoc = Hash( |
||
| Line 3,081: | Line 3,081: | ||
'+' => 'left', |
'+' => 'left', |
||
'-' => 'left', |
'-' => 'left', |
||
) |
) |
||
func shunting_yard(prog) { |
func shunting_yard(prog) { |
||
var inp = prog.words |
var inp = prog.words |
||
var ops = [] |
var ops = [] |
||
var res = [] |
var res = [] |
||
func report (op) { |
|||
printf("%25s %-7s %10s %s\n", |
|||
| ⚫ | |||
} |
|||
| ⚫ | |||
func shift (t) { report( "shift #{t}"); ops << t } |
func shift (t) { report( "shift #{t}"); ops << t } |
||
func reduce (t) { report("reduce #{t}"); res << t } |
func reduce (t) { report("reduce #{t}"); res << t } |
||
while (inp) { |
while (inp) { |
||
given(var t = inp.shift) { |
given(var t = inp.shift) { |
||
when (/\d/) { reduce(t) } |
when (/\d/) { reduce(t) } |
||
when ('(') { shift(t) } |
when ('(') { shift(t) } |
||
when (')') { |
when (')') { |
||
while (ops) { |
|||
(var x = ops.pop) == '(' ? break : reduce(x) |
|||
} |
|||
} |
|||
default { |
default { |
||
var newprec = prec{t} |
var newprec = prec{t} |
||
while (ops) { |
while (ops) { |
||
var oldprec = prec{ops[-1]} |
var oldprec = prec{ops[-1]} |
||
break if (newprec > oldprec) |
break if (newprec > oldprec) |
||
break if ((newprec == oldprec) && (assoc{t} == 'right')) |
break if ((newprec == oldprec) && (assoc{t} == 'right')) |
||
reduce(ops.pop) |
reduce(ops.pop) |
||
} |
} |
||
shift(t) |
shift(t) |
||
} |
} |
||
} |
} |
||
| Line 3,114: | Line 3,122: | ||
return res |
return res |
||
} |
} |
||
say shunting_yard('3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3').join(' ') |
say shunting_yard('3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3').join(' ')</lang> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||