--[[
Precedence: (lower - higher)
- left 2
+ left 3
/ left 4
% left 5
* left 6
^ left 7
--]]
patterns = {"%d+","-","+","/","%%","*","%^","%(","%)"}
function lex(str)
for i,p in ipairs(patterns) do
local a,b = str:find(p)
if a == 1 then
local token = {i,str:sub(a,b)}
setmetatable(token, {__tostring = function(self) return string.format("%s",self[2]) end})
str = str:sub(b+1)
return token, str
end
end
print(string.format("Cannot tokenize the string '%s'",str))
return nil
end
function interp(str)
str = str:gsub("%s","")
local token = nil
local operators, operands = {}, {}
while #str > 0 do
token, str = lex(str)
if token[1] == 1 then
-- push number onto operands stack
table.insert(operands, tonumber(token[2]))
elseif token[1] == 8 then
-- push lparen onto operators stack
table.insert(operators, token)
elseif token[1] == 9 then
-- pop from operators until lparen
local tos = operators[#operators]
while tos[1] ~= 8 do
operators[#operators] = nil
operands = apply(operands, tos)
tos = operators[#operators]
end
operators[#operators] = nil
else
-- operators
-- while there are operators on the stack whose precedence is higher, pop those
while #operators > 0 do
local tos = operators[#operators]
if token[1] <= tos[1] and tos[1] ~= 8 then
operands = apply(operands, tos)
operators[#operators] = nil
else
break
end
end
table.insert(operators, token)
end
end
-- reduce everything else on the operator stack
while #operators > 0 do
local tos = operators[#operators]
if tos[1] ~= 8 then
operands = apply(operands, tos)
operators[#operators] = nil
else
return nil
end
end
return operands[#operands]
end
function apply(operands, token)
local b = operands[#operands]
operands[#operands] = nil
local a = operands[#operands]
operands[#operands] = loadstring(string.format("return (%s) %s (%s)",a,token[2],b))()
return operands
end
print(interp("(6*(4+3)^3-10)/2^10"))