82 lines
3 KiB
Text
82 lines
3 KiB
Text
with javascript_semantics
|
|
bool show_workings = true
|
|
|
|
constant operators = {"^","*","/","+","-"},
|
|
precedence = { 4, 3, 3, 2, 2 }
|
|
|
|
procedure shunting_yard(string infix, rpn)
|
|
string res = "", sep = "", stack_top
|
|
sequence stack = {},
|
|
ops = split(substitute_all(infix,{"(",")"},{" ( "," ) "}),' ')
|
|
printf(1,"Infix input: %-32s%s", {infix,iff(show_workings?'\n':' ')})
|
|
for i=1 to length(ops) do
|
|
string op = ops[i]
|
|
if op="(" then
|
|
stack = append(stack,op)
|
|
elsif op=")" then
|
|
while 1 do
|
|
stack_top = stack[$]
|
|
stack = stack[1..$-1]
|
|
if stack_top="(" then exit end if
|
|
res &= sep&stack_top
|
|
sep = " "
|
|
end while
|
|
else
|
|
integer k = find(op,operators)
|
|
if k!=0 then
|
|
integer prec = precedence[k]
|
|
while length(stack) do
|
|
stack_top = stack[$]
|
|
k = find(stack_top,operators)
|
|
if k=0 or prec>precedence[k]
|
|
or (prec=precedence[k] and stack_top="^") then
|
|
exit
|
|
end if
|
|
stack = stack[1..$-1]
|
|
res &= sep&stack_top
|
|
sep = " "
|
|
end while
|
|
stack = append(stack,op)
|
|
else
|
|
res &= sep&op
|
|
sep = " "
|
|
end if
|
|
end if
|
|
if show_workings then
|
|
?{op,stack,res}
|
|
end if
|
|
end for
|
|
for i=length(stack) to 1 by -1 do
|
|
string op = stack[i]
|
|
res &= sep&op
|
|
sep = " "
|
|
end for
|
|
printf(1,"result: %-22s [%s]\n", {res,iff(res=rpn?"ok","**ERROR**")})
|
|
end procedure
|
|
|
|
shunting_yard("3 + 4 * 2 / (1 - 5) ^ 2 ^ 3","3 4 2 * 1 5 - 2 3 ^ ^ / +")
|
|
show_workings = false
|
|
shunting_yard("((1 + 2) ^ (3 + 4)) ^ (5 + 6)","1 2 + 3 4 + ^ 5 6 + ^")
|
|
shunting_yard("(1 + 2) ^ (3 + 4) ^ (5 + 6)","1 2 + 3 4 + 5 6 + ^ ^")
|
|
shunting_yard("((3 ^ 4) ^ 2 ^ 9) ^ 2 ^ 5","3 4 ^ 2 9 ^ ^ 2 5 ^ ^")
|
|
shunting_yard("(1 + 4) * (5 + 3) * 2 * 3","1 4 + 5 3 + * 2 * 3 *")
|
|
shunting_yard("1 * 2 * 3 * 4","1 2 * 3 * 4 *")
|
|
shunting_yard("1 + 2 + 3 + 4","1 2 + 3 + 4 +")
|
|
shunting_yard("(1 + 2) ^ (3 + 4)","1 2 + 3 4 + ^")
|
|
shunting_yard("(5 ^ 6) ^ 7","5 6 ^ 7 ^")
|
|
shunting_yard("5 ^ 4 ^ 3 ^ 2","5 4 3 2 ^ ^ ^")
|
|
shunting_yard("1 + 2 + 3","1 2 + 3 +")
|
|
shunting_yard("1 ^ 2 ^ 3","1 2 3 ^ ^")
|
|
shunting_yard("(1 ^ 2) ^ 3","1 2 ^ 3 ^")
|
|
shunting_yard("1 - 1 + 3","1 1 - 3 +")
|
|
shunting_yard("3 + 1 - 1","3 1 + 1 -")
|
|
shunting_yard("1 - (2 + 3)","1 2 3 + -")
|
|
shunting_yard("4 + 3 + 2","4 3 + 2 +")
|
|
shunting_yard("5 + 4 + 3 + 2","5 4 + 3 + 2 +")
|
|
shunting_yard("5 * 4 * 3 * 2","5 4 * 3 * 2 *")
|
|
shunting_yard("5 + 4 - (3 + 2)","5 4 + 3 2 + -")
|
|
shunting_yard("3 - 4 * 5","3 4 5 * -")
|
|
shunting_yard("3 * (4 - 5)","3 4 5 - *")
|
|
shunting_yard("(3 - 4) * 5","3 4 - 5 *")
|
|
shunting_yard("4 * 2 + 1 - 5","4 2 * 1 + 5 -")
|
|
shunting_yard("4 * 2 / (1 - 5) ^ 2","4 2 * 1 5 - 2 ^ /")
|