Here’s an operator precedence parser that does work, although this is not a typical way to do it:
NOTE: Fixed associativity
--Is this token an operator?
function IsOperator(token)
return token:match("[%+%-/%*%(%)%^]")
end
--Return the next token and the remaining expression string
function Lex(exp_str)
local token = exp_str:match("^(%d*%.?%d+)") or IsOperator(exp_str)
return token, exp_str:sub(#token + 1)
end
--Check if the operator is left-right associative
function IsLeftRight(op)
return op ~= "^"
end
--Evaluate operator on operands
function Operator(b, op, a)
if op == "*" then
return a * b
elseif op == "/" then
return a / b
elseif op == "+" then
return a + b
elseif op == "-" then
return a - b
elseif op == "^" then
return a ^ b
end
end
--Return an operator's precedence
function Precedence(op)
--Subexpressions have precedence 3
if op == "^" then
return 2
elseif op == "*" or op == "/" then
return 1
elseif op == "+" or op == "-" then
return 0
end
end
--Parse and evaluate an expression
function ParseExpression(exp_str)
--Strip whitespace
--Note that adjacent numbers separated by a space will be combined,
--not multiplied
exp_str = exp_str:gsub("%s", "")
print("Expression:", exp_str)
local token --Current token
local stack = {} --Tokens tack
local last_prec --Last operator's precedence
local prec_stack = {} --Saved precedence stack
--Push token to stack
function Push(v)
stack[#stack + 1] = v
end
--Pop token from stack
function Pop()
local val = stack[#stack]
stack[#stack] = nil
return val
end
--Peek token at offset in token stack
function Peek(offset)
return stack[#stack + (offset or 0)]
end
--Push the current last_prec
function PushPrecedence()
prec_stack[#prec_stack + 1] = last_prec
end
--Pop the previous last_prec
function PopPrecedence()
local val = prec_stack[#prec_stack]
prec_stack[#prec_stack] = nil
return val
end
--Check if only one token remains
function Done()
return #stack == 1
end
--Evaluate (Literal, Operator, Literal) on the stack
function PopOperator()
-- Pop <- B
-- Pop <- Op
-- Pop <- A <- Result
Push(Operator(Pop(), Pop(), Pop()))
end
--Check if current subexpression contains only one value
function SubexpressionDone()
return Done() or Peek(-1) == "("
end
--Pop operators until expression fully evaluated
function PopSubexpression()
while not SubexpressionDone() do
PopOperator()
end
--Pop result and return
return Pop()
end
--Check the stack of operators of greater or equal precedence to 'prec'
--Apply those operators until none are left
function RollDownStack(prec)
if SubexpressionDone() then
return
end
local next_prec = Precedence(Peek(-1))
if next_prec <= prec then
PopOperator()
else
return
end
RollDownStack(prec)
end
--Handle a single token
function ConsumeToken(token)
--Push token
Push(token)
if token == "(" then
--Begin subexpression
--Implied multiply
if tonumber(Peek(-1)) then
local v = Pop()
ConsumeToken("*")
Push(v)
end
print("Open subexpression")
PushPrecedence(last_prec)
elseif token == ")" then
--Evaluate subexpression
Pop() --Pop )
--Replace ( on stack with subexpression result
local v = PopSubexpression()
Pop()
Push(v)
--Restore last precedence of previous context
last_prec = PopPrecedence()
print("Close subexpression:", Peek())
elseif IsOperator(token) then
--Operator
--Check precedence
local new_prec = Precedence(token)
local saved_op
--Any previous operator?
if last_prec then
if IsLeftRight(token) and new_prec <= last_prec then
--Lower precedence operator, must evaluate
--previous operators first
--Save current operator
saved_op = Pop()
--Evaluate previous operators
RollDownStack(last_prec)
--Replace saved operator
print("Triggered Rolldown:", Peek())
Push(saved_op)
end
end
--Remember operator's precedence
print("Operator", token)
last_prec = new_prec
elseif tonumber(token) then
--Literal
print("Literal ", tonumber(token))
--Implied multiply
if tonumber(Peek(-1)) then
local v = Pop()
ConsumeToken("*")
Push(v)
end
end
end
--Consume all tokens
while #exp_str ~= 0 do
token, exp_str = Lex(exp_str)
ConsumeToken(token)
end
--Evaluate top level expression
local result = PopSubexpression()
print("Result:", result)
return tonumber(result)
end
local tests = {
["10 * (3 + 2) * (4 + 3) * 9"] = 3150,
["10 * 3 + 2 * 4 + 3 * 9"] = 65,
["10 ^ 2 + 35"] = 135,
["(0.1 + 9.9) ^ 3"] = 1000,
["(((((1 + 1) 3) 4) 5) 6)"] = 720,
["(6 (5 (4 (3 (1 + 1)))))"] = 720,
["2^3 + 2^5 + 2^7"] = 168,
["2^(1^(2^3))"] = 2,
["2^1^2^3"] = 2,
["10^(2+1)5"] = 5000,
["1.35*10^4"] = 13500,
["2 * (4 ^ 3 + 1)"] = 130,
["42"] = 42,
["2 ^ 3 * 4 + 1"] = 33,
["2 ^ 2 ^ 4"] = 65536,
["1/2/2/2"] = 1/8,
["1-2-3-4"] = -8,
["2^2-2^3-3^2"] = -13,
}
local results = {}
for equ, answer in pairs(tests) do
local v = ParseExpression(equ)
print()
if answer == v then
table.insert(results, string.format("%30s == %8s", equ, v))
else
table.insert(results, string.format("%30s ~= %8s (%s)", equ, answer, v))
end
end
for i, result in ipairs(results) do
print(result)
end