|
Warning: this is an htmlized version!
The original is here, and the conversion rules are here. |
-- This file:
-- http://angg.twu.net/LUA/Parenthesize1.lua.html
-- http://angg.twu.net/LUA/Parenthesize1.lua
-- (find-angg "LUA/Parenthesize1.lua")
-- Author: Eduardo Ochs <eduardoochs@gmail.com>
--
-- (defun e () (interactive) (find-angg "LUA/Parenthesize1.lua"))
-- (find-angggrep "grep --color=auto -nH --null -e Parenthesize LUA/*.lua")
-- (find-es "maxima" "operators")
-- (find-angg "LUA/Arith6.lua" "Parenthesize")
-- (find-angg "LUA/Arith6.lua" "defs_0")
-- (find-es "maxima" "operators")
-- «.Parenthesize» (to "Parenthesize")
-- «.Parenthesize-tests» (to "Parenthesize-tests")
-- «.tostrp» (to "tostrp")
-- «.tostrp-tests» (to "tostrp-tests")
-- «.Stack» (to "Stack")
-- «.Stack-half-close-tests» (to "Stack-half-close-tests")
-- «.Stack-reduce-tests» (to "Stack-reduce-tests")
require "Show1" -- (find-angg "LUA/Show1.lua" "string.show")
require "Tree1" -- (find-angg "LUA/Tree1.lua")
require "GetInfo2" -- (find-angg "LUA/GetInfo2.lua")
-- «Parenthesize» (to ".Parenthesize")
Parenthesize = Class {
type = "Parenthesize",
new = function () return Parenthesize {ops={}} end,
__tostring = function (pth) return mytostringv(pth.ops) end,
__index = {
addinfix = function (pth, lbp, rbp, names)
for _,name in ipairs(split(names)) do
pth.ops[name] = HTable {fixity="infix", name=name, lbp=lbp, rbp=rbp}
end
return pth
end,
addprefix = function (pth, bp, names)
for _,name in ipairs(split(names)) do
pth.ops[name] = HTable {fixity="prefix", name=name, bp=bp}
end
return pth
end,
addpostfix = function (pth, bp, names)
for _,name in ipairs(split(names)) do
pth.ops[name] = HTable {fixity="postfix", name=name, bp=bp}
end
return pth
end,
op = function (pth, o) return o[0] end,
opp = function (pth, o) return pth.ops[o[0]] end,
bp = function (pth, o) return pth:opp(o).bp end,
lbp = function (pth, o) return pth:opp(o).lbp end,
rbp = function (pth, o) return pth:opp(o).rbp end,
fixity = function (pth, o) return pth:atomp(o) or pth:opp(o).fixity end,
bps = function (pth, o) return pth:lbp(o)..":"..pth:rbp(o) end,
infix = function (pth, o) return pth:fixity(o) == "infix" end,
prefix = function (pth, o) return pth:fixity(o) == "prefix" end,
postfix = function (pth, o) return pth:fixity(o) == "postfix" end,
atomp = function (pth, o) return type(o) ~= "table" and "atom" end,
--
fixity0 = function (pth, op) return pth.ops[op] and pth.ops[op].fixity end,
infix0 = function (pth, op) return pth:fixity0(op) == "infix" end,
prefix0 = function (pth, op) return pth:fixity0(op) == "prefix" end,
postfix0 = function (pth, op) return pth:fixity0(op) == "postfix" end,
--
paren = function (pth, o, i)
local bp = function (o) return pth:bp(o) end
local lbp = function (o) return pth:lbp(o) end
local rbp = function (o) return pth:rbp(o) end
local bps = function (o) return pth:bps(o) end
local inf = function (o) return pth:infix(o) end
local pre = function (o) return pth:prefix(o) end
local post = function (o) return pth:postfix(o) end
-- trivial cases:
if inf(o) and i==1 and post(o[1]) then return false, "_!+_" end
if inf(o) and i==2 and pre(o[2]) then return false, "_*-_" end
if pre(o) and pre(o[1]) then return false, "--_" end
if post(o) and post(o[1]) then return false, "_!!" end
-- cases with parentheses:
if inf(o) and i==1 and pre(o[1]) and bp(o[1]) < lbp(o) then
return true, "(pre_)inf_"
end
if inf(o) and i==1 and inf(o[1]) and rbp(o[1]) < lbp(o) then
return true, "(_inf_)inf_"
end
if inf(o) and i==2 and post(o[2]) and rbp(o) > bp(o[2]) then
return true, "_inf(_post)"
end
if inf(o) and i==2 and inf(o[2]) and rbp(o) > lbp(o[2]) then
return true, "_inf(_inf_)"
end
if pre(o) and post(o[1]) and bp(o) > bp(o[1]) then
return true, "pre(_post)"
end
if pre(o) and inf(o[1]) and bp(o) > lbp(o[1]) then
return true, "pre(_inf_)"
end
if post(o) and pre(o[1]) and bp(o[1]) < bp(o) then
return true, "(pre_)post"
end
if post(o) and inf(o[1]) and rbp(o[1]) < bp(o) then
return true, "(_inf_)post"
end
-- cases without parentheses:
if inf(o) and i==1 and pre(o[1]) and bp(o[1]) >= lbp(o) then
return false, ".pre_.inf_"
end
if inf(o) and i==1 and inf(o[1]) and rbp(o[1]) >= lbp(o) then
return false, "._inf_.inf_"
end
if inf(o) and i==2 and post(o[2]) and rbp(o) <= bp(o[2]) then
return false, "_inf._post."
end
if inf(o) and i==2 and inf(o[2]) and rbp(o) <= lbp(o[2]) then
return false, "_inf._inf_."
end
if pre(o) and post(o[1]) and bp(o) <= bp(o[1]) then
return false, "pre._post."
end
if pre(o) and inf(o[1]) and bp(o) <= lbp(o[1]) then
return false, "pre._inf_."
end
if post(o) and pre(o[1]) and bp(o[1]) >= bp(o) then
return false, ".pre_.post"
end
if post(o) and inf(o[1]) and rbp(o[1]) >= bp(o) then
return false, "._inf_.post"
end
end,
},
}
pth = Parenthesize.new()
pth:addinfix(10, 11, "+ -")
pth:addinfix(30, 31, "* /")
pth:addinfix(41, 40, "^")
pth:addpostfix(50, "!")
pth:addprefix (20, "u-")
bin = function (a, op, b) return Tree {[0]=op, a, b} end
add = function (a, b) return bin(a, "+", b) end
minus = function (a, b) return bin(a, "-", b) end
mul = function (a, b) return bin(a, "*", b) end
div = function (a, b) return bin(a, "/", b) end
pow = function (a, b) return bin(a, "^", b) end
fact = function (a) return Tree {[0]="!", a} end
uminus = function (a) return Tree {[0]="u-", a} end
-- string.op = function (o) return pth.ops[o] end
-- «Parenthesize-tests» (to ".Parenthesize-tests")
--[==[
* (eepitch-lua51)
* (eepitch-kill)
* (eepitch-lua51)
dofile "Parenthesize1.lua"
test1 = function (er, o) print(trees(o, er, pth:paren(o, 1))) end
test2 = function (er, o) print(trees(o, er, pth:paren(o, 2))) end
test2(true, mul(1, add(2, 3)))
test2(false, add(1, mul(2, 3)))
test1(true, mul(add(1, 2), 3))
test1(false, add(mul(1, 2), 3))
test1(false, minus(minus(1, 2), minus(3, 4)))
test2(true, minus(minus(1, 2), minus(3, 4)))
test1(true, pow(pow(1, 2), pow(3, 4)))
test2(false, pow(pow(1, 2), pow(3, 4)))
test1(false, add(fact(1), fact(2)))
test1(false, add(fact(1), fact(2)))
test1(true, pow(uminus(1), uminus(2)))
test2(false, pow(uminus(1), uminus(2)))
--]==]
-- «tostrp» (to ".tostrp")
tostrp = function (o, addparens)
if addparens then return "("..tostrp0(o)..")" end
return tostrp0(o)
end
tostrp0 = function (o)
local tsp = function (i, j) return tostrp(o[i], pth:paren(o,j)) end
if pth:atomp(o) then return tostring(o) end
if pth:prefix(o) then return format( "%s %s", o[0], tsp(1) ) end
if pth:postfix(o) then return format("%s %s" , tsp(1), o[0] ) end
if pth:infix(o) then return format("%s %s %s", tsp(1,1), o[0], tsp(2,2)) end
error "Foo!"
end
-- «tostrp-tests» (to ".tostrp-tests")
--[==[
* (eepitch-lua51)
* (eepitch-kill)
* (eepitch-lua51)
dofile "Parenthesize1.lua"
foo = minus(minus(1, 2), minus(3, 4))
foo = pow(pow(1, 2), pow(3, 4))
foo = uminus(1)
= foo
= tostrp(foo)
--]==]
-- «Stack» (to ".Stack")
Stack = Class {
type = "Stack",
new = function () return Stack {} end,
--
__tostring = function (s) return mapconcat(tostring, s, " ") end,
__tostring = function (s) return tostring(trees(unpack(s))) end,
__index = {
push = function (s, o) table.insert(s, o); return s end,
pushs = function (s, ...) for _,o in ipairs({...}) do s:push(o) end; return s end,
--
check = function (s) assert(#s>0, s.msg or "Empty stack"); return s end,
drop = function (s) s:check(); s[#s]=nil; return s end,
dropn = function (s, n) for i=1,n do s:drop() end; return s end,
dropuntil = function (s, n) while #s>n do s:drop() end; return s end,
clear = function (s) return s:dropn(#s) end,
--
pop = function (s) return s[#s], s:dropn(1) end,
pop2 = function (s) return s[#s-1], s[#s], s:dropn(2) end,
pop3 = function (s) return s[#s-2], s[#s-1], s[#s], s:dropn(3) end,
pop4 = function (s) return s[#s-3], s[#s-2], s[#s-1], s[#s], s:dropn(4) end,
--
pick = function (s, offset) return s[#s-offset] end,
pock = function (s, offset, o) s[#s-offset] = o; return s end,
--
pf1 = function (s, fmt) return s:push(format(fmt, s:pop())) end,
pf2 = function (s, fmt) return s:push(format(fmt, s:pop2())) end,
pf3 = function (s, fmt) return s:push(format(fmt, s:pop3())) end,
--
-- 2022sep04
halfpre = function (s) local op = s:pop(); return s:push(pre(op,"?")) end,
closepre = function (s) local a,b = s:pop2(); return s:push(pre(a[0],b)) end,
halfbin = function (s) local a,op = s:pop2(); return s:push(bin(a,op,"?")) end,
closebin = function (s) local a,b = s:pop2(); return s:push(bin(a[1], a[0], b)) end,
closepost = function (s) local a,op = s:pop2(); return s:push(post(a,op)) end,
--
reduce = function (s)
if pth:prefix(s:pick(1)) then return s:closepre() end
if pth:infix(s:pick(1)) then return s:closebin() end
error("bad reduce")
end,
half = function (s)
if pth:infix0(s:pick(0)) then return s:halfbin() end
if pth:prefix0(s:pick(0)) then return s:halfpre() end
error("bad half")
end,
pushh = function (s, op) s:push(op); return s:half() end,
},
}
pre = function (op, a) return Tree {[0]=op, a} end
post = function (a, op) return Tree {[0]=op, a} end
bin = function (a, op, b) return Tree {[0]=op, a, b} end
-- «Stack-reduce-tests» (to ".Stack-reduce-tests")
--[==[
* (eepitch-lua51)
* (eepitch-kill)
* (eepitch-lua51)
dofile "Parenthesize1.lua"
-- Ok:
s = Stack.new()
= s:push (2)
= s:pushh("+")
= s:push (3)
= s:reduce(3)
-- Ok:
s = Stack.new()
= s:pushh("u-")
= s:push ("2")
= s:reduce()
= s:halfpre()
= s:push("2")
= s:reduce()
= s:pick(1)
= pth:prefix(s:pick(1))
= s:pick(1)
= s:reduce()
= s:closepre()
run_my_repl_now()
= s:reduce()
stop_my_repl_now()
* (eek "C-x r SPC a")
= dg
= dg[7]
= dg[7]:vars()
= dg[7]:names()
= dg[7]:is()
= dg[7].v
= dg[7]:v "s"
s = Stack.new()
= s:push("3")
= s:push("/")
= s:halfbin()
= s:push("4")
= s:closebin()
s = Stack.new()
= s:push("5")
= s:push("!")
= s:closepost()
= s:reduce()
= s:push("!")
= s:reduce()
= s:push("+")
= s:reduce()
= s:push("b")
= s:reduce()
= s:push("/")
= pth:infix(s:pick(0))
= s:reduce()
run_my_repl_now()
= s:reduce()
stop_my_repl_now()
* (eek "C-x r SPC a")
= dg
= dg[7]
= dg[7]:vars()
= dg[7]:vs()
= s:halfbin()
= s:push("b")
= s:closebin()
= s:push("+")
= s:halfbin("+")
= s:push("c")
= s:push("!")
= s:closepost()
= s:closebin()
= s:push("u-")
= s:push("d")
= s:closepre()
= s:pick(0)
= pth:prefix(s:pick(0))
a,op = s:pop2()
= s:push(bin(a,op,"?"))
= s:push("b")
a,b = s:pop2()
= s:push(bin(a[1], a[0], b))
r = math.random
rr = function ()
local a = r(0,3)
if a == 0 then return "o" end
if a == 1 then return ":"..r(0,9) end
if a == 2 then return r(0,9)..":" end
if a == 3 then return r(0,9)..":"..r(0,9) end
end
rrs = function (n)
local str = ""
for i=1,n do str = str.." "..rr() end
return str
end
rs = function (str)
str = str or "+ - * / ^ u- ! o o"
local spl = split(str)
return spl[r(1,#spl)]
end
rss = function (n)
local str = ""
for i=1,n do str = str.." "..rs() end
return str
end
s = Stack.new()
= s:push("a")
= s:push("/")
a,op = s:pop2()
= s:push(bin(a,op,"?"))
= s:push("b")
a,b = s:pop2()
= s:push(bin(a[1], a[0], b))
= s:push("/")
= rrs(20)
= rss(20)
o / o * o * o / o ! u- u- o / o / o ! o ^ -
s = Stack.new()
= s:push("o")
= s:push("3:7")
= s:pf2("(%s_%s")
= s:push("o")
= s:push("9:1")
= s:pf2("(%s_%s")
= s:push(":7")
= s:push(":5")
= s:push(":6")
= s:push(":5")
= s:push("o")
= s:push("9:6")
= s:pf2("(%s_%s")
= s:push("o")
= s:pf2("%s_%s)")
= s:pf2("(%s_%s)")
= s:pf2("(%s_%s)")
= s:pf2("(%s_%s)")
= s:pf2("(%s_%s)")
= s:push("2:")
= s:pf2("(%s_%s)")
= s:pf2("%s_%s)")
= s:push("0:")
= s:pf2("(%s_%s)")
= s:pf2("%s_%s)")
= s:pf2("%s_%s)")
= s:pf2("%s_%s)")
= s:push("1:")
= s:push("0:")
= s:push("o")
= s:pf2("(%s_%s)")
= s:pf2("(%s_%s)")
= s:pf2("(%s_%s)")
= s:pf2("(%s_%s)")
= s:pf2("(%s_%s")
= s
s:push(format("(%s %s", s:pop2()))
= s
o 3:7 o 9:1 :7 :5 :6 :5 o 9:6 o 2: 0: o 2:4 o 2:5 6:2 5: :9 :7 7:
s = Stack.new()
s:pushs("a", ">", "b", "<")
= s
= math.random(100)
r = function () return math.random(10) end
--]==]
-- «Stack-half-close-tests» (to ".Stack-half-close-tests")
--[==[
* (eepitch-lua51)
* (eepitch-kill)
* (eepitch-lua51)
dofile "Parenthesize1.lua"
s = Stack.new()
= s:push("u-")
= s:halfpre()
= s:push("2")
= s:closepre()
s = Stack.new()
= s:push("3")
= s:push("/")
= s:halfbin()
= s:push("4")
= s:closebin()
s = Stack.new()
= s:push("5")
= s:push("!")
= s:closepost()
--]==]
-- Local Variables:
-- coding: utf-8-unix
-- End: