binary_expressions.lua

-- binary expressions
-- operator precedence

do -- BitWise tutorial https://www.youtube.com/watch?v=L4P98pGhpnE
	local tokens, token, i

	local function next_token()
		i = i + 1
		token = tokens:sub(i, i)

		local num = tonumber(token)
		if num then token = num end

		if i > #tokens then
			token = nil
		end
	end

	local parse_expr

	local function parse_expr3()
		if type(token) == "number" then
			local val = token
			next_token()
			return val
		elseif token == "(" then
			next_token()
			local val = parse_expr()
			assert(token == ")")
			next_token()
			return val
		else
			error("expected number or ( got " .. tostring(token))
		end
	end

	local function parse_expr2()
		if token == "-" then
			next_token()
			local val = parse_expr2()
			return -val
		elseif token == "+" then
			next_token()
			return parse_expr2()
		end

		return parse_expr3()
	end

	local function parse_expr1()
		local val = parse_expr2()

		while token == "*" or token == "/" do
			local op = token
			next_token()
			local rval = parse_expr2()
			if op == "*" then
				val = val * rval
			else
				assert(op == "/")
				val = val / rval
			end
		end
		return val
	end

	local function parse_expr0()
		local val = parse_expr1()
		while token == "+" or token == "-" do
			local op = token
			next_token()
			local rval = parse_expr1()
			if op == "+" then
				val = val + rval
			else
				assert(op == "-")
				val = val - rval
			end
		end
		return val
	end

	parse_expr = function(str)
		return parse_expr0()
	end

	local function test(str)
		i = 0
		tokens = str
		next_token()

		assert(loadstring([[
			local val = (...)(']] .. str .. [[')
			local expected = ]] .. str .. [[
			if val == expected then
				print('\t]] .. str .. [[: ' .. val)
			else
				print('\t]] .. str .. [[: expected ' .. expected .. ' != ' .. val)
			end
		]]))(parse_expr)
	end
	
	print("BitWise:")
	
	test("1")
	test("(1)")
	test("-1")
	test("1-2-3")
	test("2*3+4*5")
	test("2*(3+4)*5")
	test("2+-1")
end

do -- improved code with a way to define operators in tables and return binary expression tree
	local operators = {
		["^"] = {10, 9},
		["%"] = {7, 7},
		["/"] = {7, 7},
		["*"] = {7, 7},
		["+"] = {6, 6},
		["-"] = {6, 6},
		["<"] = {3, 3},
		[">"] = {3, 3},
	}

	local unary_operators = {
		["-"] = true,
		["#"] = true,
	}

	local tokens, token, i

	local function next_token()
		i = i + 1
		token = tokens:sub(i, i)

		local num = tonumber(token)
		if num then token = num end

		if i > #tokens then
			token = nil
		end
	end

	local function parse_expression(priority)
		local val

		if unary_operators[token] then
			local op = token
			next_token()
			val = {unary = true, op = op, value = parse_expression(0)}
		elseif type(token) == "number" then
			val = token
			next_token()
		elseif token == "(" then
			next_token()
			val = parse_expression(0)
			assert(token == ")")
			next_token()
		else
			error("expected number or ( got " .. tostring(token))
		end

		while operators[token] and operators[token][1] > priority do
			local op = token
			next_token()
			val = {op = op, left = val, right = parse_expression(operators[op][2])}
		end

		return val
	end

	local function test(str)
		i = 0
		tokens = str
		next_token()

		local tbl = parse_expression(0)
	
		local function dump(v)
			if type(v) == "number" then
				io.write(v)
			else
				if v.left then
					io.write("(")
					dump(v.left)
				end

				io.write(v.op)
				if v.unary then io.write(v.value) end

				if v.right then
					dump(v.right)
					io.write(")")
				end
			end
		end
		io.write("\t")
		dump(tbl)
		io.write("\n")
	end
	
	print("binary expression tree:")

	test("1")
	test("(1)")
	test("-1")
	test("1-2-3")
	test("2*3+4*5")
	test("2*(3+4)*5")
	test("2+-1")
end