exp_eval.lua

#!/usr/bin/lua

expr = io.read()

--tokenize

tokens = {}

local current_number = nil

local function push_digit(d)
    if not current_number then current_number = tonumber(d); return end
    current_number = (current_number * 10) + tonumber(d)
end

local function finish_token(token, kind)
    tokens[#tokens + 1] = {value = token, kind = kind}
end

function push_token(token, kind)
    if kind == "digit" then push_digit(token); return end
    
    if current_number then finish_token(current_number, "number"); current_number = nil end
    if kind == "space" then return end
    finish_token(token, kind)
end

for c in expr:gmatch(".") do
    local switch = {
        ['('] = "delimiter",
        [')'] = "delimiter",

        ['0'] = "digit",
        ['1'] = "digit",
        ['2'] = "digit",
        ['3'] = "digit",
        ['4'] = "digit",
        ['5'] = "digit",
        ['6'] = "digit",
        ['7'] = "digit",
        ['8'] = "digit",
        ['9'] = "digit",

        ['+'] = "operator",
        ['-'] = "operator",
        ['*'] = "operator",
        ['/'] = "operator",
        [' '] = "space"
    }

    local result = switch[c]
    if not result then
        print ("illegal character: " .. c)
        return
    else
        push_token(c, result)
    end
end
push_token(nil, "space") --since when you press enter no character is registered


local operations = {['+'] = "add", ['-'] = "sub", ['*'] = "mul", ['/'] = "div"} 
local delimiters = {['('] = "open", [')'] = "close"}

local function eval_expr(expr)
    if type(expr) == "number" then
        return "literal", expr
    end
    --don't re evaluate
    if expr.kind == "literal" then
        return "literal", expr.left
    end
    if #expr == 1 and expr[1].kind == "number" then
        return "literal", expr[1].value
    end
    local subexpr_open = false
    local left_leaf, right_leaf, operation = {}, {}, ""
    local current_leaf = left_leaf
    local nested_delims = 0
    for idx,val in ipairs(expr) do
        local ignore = false
        --if we've already changed leafs, just fill the right leaf
        if current_leaf ~= right_leaf then
            if delimiters[val.value] == "open" then
                if not subexpr_open then
                    subexpr_open = true
                    ignore = true
                else
                    nested_delims = nested_delims + 1
                end
            end
            if delimiters[val.value] == "close" then
                if not subexpr_open then 
                    print("unexpected closing delimiter")
                    error()
                elseif nested_delims == 0 then 
                    subexpr_open = false 
                    ignore = true
                else 
                    nested_delims = nested_delims - 1 
                end
            end

            if val.kind == "operator" and not subexpr_open then
                operation = operations[val.value]
                current_leaf = right_leaf
                ignore = true
            end
        end
        
        if not ignore then table.insert(current_leaf, val) end
    end
    if #right_leaf == 0 then
        --noop because we had a parenthesis
        return "add", left_leaf, {{value = 0, kind = "number"}}
    else
        return operation, left_leaf, right_leaf
    end
end


main_expr = tokens
local _,a, b = eval_expr(main_expr)
main_expr = {kind = _, left = a, right = b}

print(main_expr.kind, main_expr.left, main_expr.right)
local opr = {
    add = function(a, b) return a + b end,
    sub = function(a,b) return a - b end,
    mul = function(a,b) return a * b end,
    div = function(a,b) return a / b end
}
local current_node = main_expr
local leaf = ""
local level = 0
-- while main_expr.kind ~= "literal" do
while main_expr.kind ~= "literal" do

    local left, right = current_node.left, current_node.right
    if left.kind ~= "literal" then
        local _, la, lb = eval_expr(left)
        left = {parent = current_node, kind = _, left = la, right = lb}
        current_node.left = left
    end
    if right.kind ~= "literal" then
        local _, ra, rb = eval_expr(right)
        right = {parent = current_node, kind = _, left = ra, right = rb}
        current_node.right = right
    end
    if left.kind ~= "literal" then
        leaf = "left"    
        current_node = left
        level = level + 1
    elseif right.kind ~= "literal" then 
        leaf = "right"
        current_node = right
        level = level + 1
    end

    if left.kind == "literal" and right.kind == "literal" then

        local value = opr[current_node.kind](left.left, right.left)
        if current_node.parent then
            current_node.kind = "literal"
            current_node.left = value
            current_node = current_node.parent
            level = level - 1
            local left, right = current_node.left, current_node.right
        else 
            current_node.kind = "literal"
            current_node.left = value
        end
    end
end
print(main_expr.left)