逆波兰式算法 #Lua

rpn.lua

local function IsString(ch)
    return string.match(ch, "[^\t%s%d%+%-%*/%%%(%)]")
end

local function GetString(szExpression, nIndex)
    return string.find(szExpression, "^([^\t%s%d%+-%*/%%%(%)]+)", nIndex)
end

local function IsNumber(ch)
    return string.match(ch, "[%d%.]+")
end

local function GetNumber(szExpression, nIndex)
    return string.find(szExpression, "([%d%.]+)", nIndex)
end

local function GetVariable(szVar)
    local tVariable = _G
    for szIndex in string.gmatch(szVar, "[^%.]+") do
        if tVariable and type(tVariable) == "table" then
            tVariable = tVariable[szIndex]
        else
            tVariable = nil
            break
        end
    end
    return tVariable
end

--[[
--表达式中的值直接压入tTrans,tStack只保存符号
--如果运算符是"("，直接压入tTrans
--如果运算符是")"，把"("之间的操作符全部弹出，压入tTrans，然后抛弃"("
--如果运算符是"/","*","%"的时候，先弹出所有"/","*","%"，然后压入当前运算符
--如果运算符是"+","-"的时候，弹出所有到"("之间的运算符，然后压入当前运算符
--]]
function GetTrans(szExpression)
    local tTrans, tStack = { }, { }
    local nIndex = 1
    while nIndex <= #szExpression do
        local ch = string.sub(szExpression, nIndex, nIndex)
        if IsString(ch) then
            local _, nEnd, szVar = GetString(szExpression, nIndex)
            local var = GetVariable(szVar)
            if type(var) == "function" then
                table.insert(tStack, var)
                -- 函数直接压入运算符表
            elseif type(var) == "number" then
                table.insert(tStack, tonumber(var))
            else
                table.insert(tTrans, szVar)
                -- 变量直接压入表达式表
            end
            nIndex = nEnd + 1
        elseif ch == "(" then
            table.insert(tStack, ch)
            nIndex = nIndex + 1
        elseif ch == ")" then
            for i = #tStack, 1, -1 do
                if tStack[i] ~= "(" then
                    tTrans[#tTrans + 1] = table.remove(tStack, i)
                else
                    break
                end
            end
            nIndex = nIndex + 1
            table.remove(tStack)
        elseif ch == "+" or ch == "-" then
            for i = #tStack, 1, -1 do
                if tStack[i] ~= "(" then
                    tTrans[#tTrans + 1] = table.remove(tStack, i)
                else
                    break
                end
            end
            table.insert(tStack, ch)
            nIndex = nIndex + 1
        elseif ch == "*" or ch == "/" or ch == "%" then
            for i = #tStack, 1, -1 do
                if tStack[i] == "*" or tStack[i] == "/" or tStack[i] == "/" then
                    tTrans[#tTrans + 1] = table.remove(tStack, i)
                else
                    break
                end
            end
            table.insert(tStack, ch)
            nIndex = nIndex + 1
        elseif IsNumber(ch) then
            local _, nEnd, szNumber = GetNumber(szExpression, nIndex)
            table.insert(tTrans, tonumber(szNumber))
            nIndex = nEnd + 1
        else
            nIndex = nIndex + 1
        end
    end
    for i = #tStack, 1, -1 do
        table.insert(tTrans, tStack[i])
    end
    return tTrans
end

-- fnReader(k) 用来读取非数值变量
function eval(szExpression, fnReader)
    local tExpression = GetTrans(szExpression)
    local tStack = { }
    local nLeft, nRight
    for index, val in ipairs(tExpression) do
        if type(val) == "string" then
            if #val == 1 and val ~= "," then
                -- 运算符号
                nRight = table.remove(tStack)
                nLeft = table.remove(tStack)
                if type(nRight) == "string" then
                    nRight = fnReader(nRight)
                end
                if type(nLeft) == "string" then
                    nLeft = fnReader(nLeft)
                end
                local tCalc = {
                    ["+"] = nLeft + nRight,
                    ["-"] = nLeft - nRight,
                    ["*"] = nLeft * nRight,
                    ["/"] = nLeft / nRight,
                    ["%"] = nLeft % nRight
                }
                if tCalc[val] then
                    table.insert(tStack, tCalc[val])
                end
            else
                table.insert(tStack, val)
            end
        elseif type(val) == "function" then
            local tParam = { }
            if #tStack > 0 then
                table.insert(tParam, table.remove(tStack))
            end
            local nRemoveCount = 0
            for i = #tStack, 1, -2 do
                if tStack[i] == "," then
                    nRemoveCount = nRemoveCount + 2
                    table.insert(tParam, tStack[i - 1])
                end
            end
            for i = 1, nRemoveCount do
                table.remove(tStack)
            end
            table.insert(tStack, val(unpack(tParam)))
        elseif type(val) == "number" then
            table.insert(tStack, val)
        end
    end
    return tStack[1]
end

function test()
    return 1
end

print(eval("1+2+test(1,2,3)+3+4"))