Anonymous user
Parsing/Shunting-yard algorithm: Difference between revisions
Add language: UNIX Shell
mNo edit summary |
(Add language: UNIX Shell) |
||
Line 4,186:
</pre>
=={{header|Unix Shell}}==
<lang bash>#!/bin/sh
getopprec() {
case "$1" in
'+') echo 2;;
'-') echo 2;;
'*') echo 3;;
'/') echo 4;;
'%') echo 4;;
'^') echo 4;;
'(') echo 5;;
esac
}
getopassoc() {
case "$1" in
'^') echo r;;
*) echo l;;
esac
}
showstacks() {
[ -n "$1" ] && echo "Token: $1" || echo "End parsing"
echo -e "\tOutput: `tr $'\n' ' ' <<< "$out"`"
echo -e "\tOperators: `tr $'\n' ' ' <<< "$ops"`"
}
infix() {
local out="" ops=""
while [ "$#" -gt 0 ]; do
grep -qE '^[0-9]+$' <<< "$1"
if [ "$?" -eq 0 ]; then
out="`sed -e '$a'"$1" -e '/^$/d' <<< "$out"`"
showstacks "$1"
shift && continue
fi
grep -q '^[-+*/^%]$' <<< "$1"
if [ "$?" -eq 0 ]; then
topop="`sed -n '$p' <<< "$ops"`"
if [ -n "$topop" ] || [ \! "$topop" = '(' ]; then
thispred=`getopprec "$1"`
thisassoc=`getopassoc "$1"`
thatpred=`getopprec "$topop"`
thatassoc=`getopassoc "$topop"`
while [ $thatpred -gt $thispred ] 2> /dev/null || ( [ \
$thatpred -eq $thispred ] 2> /dev/null && [ $thisassoc = \
'l' ] 2> /dev/null ); do # To /dev/null 'cus u r fake news
[ "$topop" = '(' ] && break
op="`sed -n '$p' <<< "$ops"`"
out="`sed -e '$a'"$op" -e '/^$/d' <<< "$out"`"
ops="`sed '$d' <<< "$ops"`"
topop="`sed -n '$p' <<< "$ops"`"
thatpred=`getopprec "$topop"`
thatassoc=`getopassoc "$topop"`
done
fi
ops="`sed -e '$a'"$1" -e '/^$/d' <<< "$ops"`"
showstacks "$1"
shift && continue
fi
grep -q '^($' <<< "$1"
if [ "$?" -eq 0 ]; then
ops="`sed -e '$a'"$1" -e '/^$/d' <<< "$ops"`"
showstacks "$1"
shift && continue
fi
grep -q '^)$' <<< "$1"
if [ "$?" -eq 0 ]; then
grep -q '^($' <<< "`sed -n '$p' <<< "$ops"`"
while [ "$?" -ne 0 ]; do
op="`sed -n '$p' <<< "$ops"`"
out="`sed -e '$a'"$op" -e '/^$/d' <<< "$out"`"
ops="`sed '$d' <<< "$ops"`"
grep -q '^($' <<< "`sed '$p' <<< "$ops"`"
done
ops="`sed '$d' <<< "$ops"`"
showstacks "$1"
shift && continue
fi
shift
done
while [ -n "$ops" ]; do
op="`sed -n '$p' <<< "$ops"`"
out="`sed -e '$a'"$op" -e '/^$/d' <<< "$out"`"
ops="`sed '$d' <<< "$ops"`"
done
showstacks $1
}
infix 3 + 4 \* 2 / \( 1 - 5 \) ^ 2 ^ 3</lang>
===Output===
<lang>Token: 3
Output: 3
Operators:
Token: +
Output: 3
Operators: +
Token: 4
Output: 3 4
Operators: +
Token: *
Output: 3 4
Operators: + *
Token: 2
Output: 3 4 2
Operators: + *
Token: /
Output: 3 4 2
Operators: + * /
Token: (
Output: 3 4 2
Operators: + * / (
Token: 1
Output: 3 4 2 1
Operators: + * / (
Token: -
Output: 3 4 2 1
Operators: + * / ( -
Token: 5
Output: 3 4 2 1 5
Operators: + * / ( -
Token: )
Output: 3 4 2 1 5 -
Operators: + * /
Token: ^
Output: 3 4 2 1 5 -
Operators: + * / ^
Token: 2
Output: 3 4 2 1 5 - 2
Operators: + * / ^
Token: ^
Output: 3 4 2 1 5 - 2
Operators: + * / ^ ^
Token: 3
Output: 3 4 2 1 5 - 2 3
Operators: + * / ^ ^
End parsing
Output: 3 4 2 1 5 - 2 3 ^ ^ / * +
Operators:</lang>
=={{header|VBA}}==
|