-
Notifications
You must be signed in to change notification settings - Fork 1
/
MathParser_min.lua
1 lines (1 loc) · 21.9 KB
/
MathParser_min.lua
1
local Helpers_Helpers_module=(function(...)local char=string.char local match=string.match local gmatch=string.gmatch local insert=table.insert local Helpers={}function Helpers.stringToTable(string)local table={}for char in gmatch(string,".")do insert(table,char)end return table end function Helpers.createPatternLookupTable(pattern)local lookupTable={}for i=0,255 do local character=char(i)if match(character,pattern)then lookupTable[character]=true end end return lookupTable end function Helpers.makeTrie(table)local trieTable={}for _,op in ipairs(table)do local node=trieTable for character in op:gmatch(".")do node[character]=node[character]or{}node=node[character]end node.value=op end return trieTable end return Helpers end)("Helpers/Helpers")local Evaluator_Evaluator_module=(function(...)local Helpers=Helpers_Helpers_module local unpack=unpack or table.unpack local insert=table.insert local DEFAULT_OPERATOR_FUNCTIONS={Unary={["-"]=function(operand)return-operand end},Binary={["+"]=function(left,right)return left+right end,["-"]=function(left,right)return left-right end,["/"]=function(left,right)return left/right end,["*"]=function(left,right)return left*right end,["^"]=function(left,right)return left^right end,["%"]=function(left,right)return left%right end}}local DEFAULT_FUNCTIONS={sin=math.sin,cos=math.cos,tan=math.tan,asin=math.asin,acos=math.acos,atan=math.atan,floor=math.floor,ceil=math.ceil,abs=math.abs,sqrt=math.sqrt,log=math.log,log10=math.log10,exp=math.exp,rad=math.rad,deg=math.deg}local function Evaluator(expression,variables,operatorFunctions,functions)local expression=expression local variables=variables or{}local operatorFunctions=operatorFunctions or DEFAULT_OPERATOR_FUNCTIONS local functions=functions or{}local evaluateUnaryOperator,evaluateBinaryOperator,evaluateOperator,evaluateFunctionCall,evaluateNode function evaluateUnaryOperator(node)local nodeValue=node.Value local operatorFunction=operatorFunctions.Unary[nodeValue]assert(operatorFunction,"invalid operator: "..tostring(nodeValue))local operandValue=evaluateNode(node.Operand)return operatorFunction(operandValue,node)end function evaluateBinaryOperator(node)local nodeValue=node.Value local nodeLeft=node.Left local nodeRight=node.Right local operatorFunction=operatorFunctions.Binary[nodeValue]assert(operatorFunction,"invalid operator")local leftValue=evaluateNode(nodeLeft)local rightValue=evaluateNode(nodeRight)return operatorFunction(leftValue,rightValue,node)end function evaluateOperator(node)local isUnary=not(not node.Operand)if isUnary then return evaluateUnaryOperator(node)end return evaluateBinaryOperator(node)end function evaluateFunctionCall(node)local functionName=node.FunctionName local arguments=node.Arguments local functionCall=functions[functionName]or DEFAULT_FUNCTIONS[functionName]assert(functionCall,"invalid function call: "..tostring(functionName))local evaluatedArguments={}for _,argument in ipairs(arguments)do local evaluatedArgument=evaluateNode(argument)insert(evaluatedArguments,evaluatedArgument)end return functionCall(unpack(evaluatedArguments))end function evaluateNode(node)local nodeType=node.TYPE if nodeType=="Constant"then return tonumber(node.Value)elseif nodeType=="Variable"then local variableValue=variables[node.Value]if not variableValue then return error("Variable not found: "..tostring(node.Value))end return variableValue elseif nodeType=="Operator"or nodeType=="UnaryOperator"then return evaluateOperator(node)elseif nodeType=="FunctionCall"then return evaluateFunctionCall(node)end return error("Invalid node type: "..tostring(nodeType).." ( You're not supposed to see this error message. )")end local function resetToInitialState(givenExpression,givenVariables,givenOperatorFunctions,givenFunctions)expression=givenExpression variables=givenVariables or{}operatorFunctions=givenOperatorFunctions or DEFAULT_OPERATOR_FUNCTIONS functions=givenFunctions or DEFAULT_FUNCTIONS end local function evaluate()assert(expression,"No expression to evaluate")return evaluateNode(expression)end return{resetToInitialState=resetToInitialState,evaluate=evaluate}end return Evaluator end)("Evaluator/Evaluator")local Lexer_TokenFactory_module=(function(...)local TokenFactory={}function TokenFactory.createConstantToken(value,curCharPos)return{TYPE="Constant",Value=value,Position=curCharPos}end function TokenFactory.createVariableToken(value,curCharPos)return{TYPE="Variable",Value=value,Position=curCharPos}end function TokenFactory.createParenthesesToken(value,curCharPos)return{TYPE="Parentheses",Value=value,Position=curCharPos}end function TokenFactory.createOperatorToken(value,curCharPos)return{TYPE="Operator",Value=value,Position=curCharPos}end function TokenFactory.createCommaToken(curCharPos)return{TYPE="Comma",Value=",",Position=curCharPos}end return TokenFactory end)("Lexer/TokenFactory")local Lexer_Lexer_module=(function(...)local Helpers=Helpers_Helpers_module local TokenFactory=Lexer_TokenFactory_module local makeTrie=Helpers.makeTrie local stringToTable=Helpers.stringToTable local createPatternLookupTable=Helpers.createPatternLookupTable local concat=table.concat local insert=table.insert local rep=string.rep local createConstantToken=TokenFactory.createConstantToken local createVariableToken=TokenFactory.createVariableToken local createParenthesesToken=TokenFactory.createParenthesesToken local createOperatorToken=TokenFactory.createOperatorToken local createCommaToken=TokenFactory.createCommaToken local ERROR_SEPARATOR="+------------------------------+"local ERROR_NUMBER_AFTER_X="Expected a number after the 'x' or 'X'"local ERROR_NUMBER_AFTER_DECIMAL_POINT="Expected a number after the decimal point"local ERROR_NUMBER_AFTER_EXPONENT_SIGN="Expected a number after the exponent sign"local ERROR_INVALID_CHARACTER="Invalid character '%s'. Expected whitespace, parenthesis, comma, operator, or number."local ERROR_NO_CHAR_STREAM="No charStream given"local DEFAULT_OPERATORS={"+","-","*","/","^","%"}local DEFAULT_OPERATORS_TRIE=makeTrie(DEFAULT_OPERATORS)local WHITESPACE_LOOKUP=createPatternLookupTable("%s")local NUMBER_LOOKUP=createPatternLookupTable("%d")local IDENTIFIER_LOOKUP=createPatternLookupTable("[a-zA-Z_]")local HEXADECIMAL_NUMBER_LOOKUP=createPatternLookupTable("[%da-fA-F]")local PLUS_MINUS_LOOKUP=createPatternLookupTable("[+-]")local SCIENTIFIC_E_LOOKUP=createPatternLookupTable("[eE]")local HEXADECIMAL_X_LOOKUP=createPatternLookupTable("[xX]")local IDENTIFIER_CONTINUATION_LOOKUP=createPatternLookupTable("[a-zA-Z0-9_]")local PARENTHESIS_LOOKUP=createPatternLookupTable("[()]")local function Lexer(expression,operators,charPos)local stringToTableCache={}local errors={}local charStream,curChar,curCharPos if expression then expression=expression charStream=stringToTable(expression)curChar=charStream[charPos or 1]curCharPos=charPos or 1 stringToTableCache[expression]=charStream end local operatorTrie=(operators and makeTrie(operators))or DEFAULT_OPERATORS_TRIE local operators=operators or DEFAULT_OPERATORS local operatorsTrie=operatorTrie local function peek()return charStream[curCharPos+1]or"\0"end local function consume(n)local newCurCharPos=curCharPos+(n or 1)local newCurChar=charStream[newCurCharPos]or"\0"curCharPos=newCurCharPos curChar=newCurChar return newCurChar end local function generateErrorMessage(message,positionAdjustment)local position=curCharPos+(positionAdjustment or 0)local pointer=rep(" ",position-1).."^"local errorMessage="\n"..concat(charStream).."\n"..pointer.."\n"..message return errorMessage end local function displayErrors()local errors=errors if#errors>0 then local errorMessage=concat(errors,"\n"..ERROR_SEPARATOR)error("Lexer errors:".."\n"..ERROR_SEPARATOR..errorMessage.."\n"..ERROR_SEPARATOR)end end local function isNumber(char)local char=char or curChar return NUMBER_LOOKUP[char]or(char=="."and NUMBER_LOOKUP[peek()])end local function consumeHexNumber(number)insert(number,consume())local isHex=HEXADECIMAL_NUMBER_LOOKUP[peek()]if not isHex then local generatedErrorMessage=generateErrorMessage(ERROR_NUMBER_AFTER_X,1)insert(errors,generatedErrorMessage)end repeat insert(number,consume())isHex=HEXADECIMAL_NUMBER_LOOKUP[peek()]until not isHex return number end local function consumeFloatNumber(number)insert(number,consume())local isNumber=NUMBER_LOOKUP[peek()]if not isNumber then local generatedErrorMessage=generateErrorMessage(ERROR_NUMBER_AFTER_DECIMAL_POINT,1)insert(errors,generatedErrorMessage)end repeat insert(number,consume())isNumber=NUMBER_LOOKUP[peek()]until not isNumber return number end local function consumeScientificNumber(number)insert(number,consume())if PLUS_MINUS_LOOKUP[peek()]then insert(number,consume())end local isNumber=NUMBER_LOOKUP[peek()]if not isNumber then local generatedErrorMessage=generateErrorMessage(ERROR_NUMBER_AFTER_EXPONENT_SIGN,1)insert(errors,generatedErrorMessage)end repeat insert(number,consume())isNumber=NUMBER_LOOKUP[peek()]until not isNumber return number end local function consumeNumber()local number={curChar}local isFloat=false local isScientific=false local isHex=false if curChar=='0'and HEXADECIMAL_X_LOOKUP[peek()]then return concat(consumeHexNumber(number))end while NUMBER_LOOKUP[peek()]do insert(number,consume())end if peek()=="."then number=consumeFloatNumber(number)end local nextChar=peek()if SCIENTIFIC_E_LOOKUP[nextChar]then number=consumeScientificNumber(number)end return concat(number)end local function consumeIdentifier()local identifier,identifierLen={},0 local nextChar repeat identifierLen=identifierLen+1 identifier[identifierLen]=curChar local nextChar=peek()until not(IDENTIFIER_CONTINUATION_LOOKUP[nextChar]and consume())return concat(identifier)end local function consumeConstant()if isNumber(curChar)then local newToken=consumeNumber()return createConstantToken(newToken,curCharPos)end local errorMessage=generateErrorMessage(ERROR_INVALID_CHARACTER:format(curChar))insert(errors,errorMessage)return end local function consumeOperator()local node=operatorsTrie local charStream=charStream local curCharPos=curCharPos local operator local index=0 while true do local character=charStream[curCharPos+index]node=node[character]if not node then break end operator=node.value index=index+1 end if not operator then return end consume(#operator-1)return operator end local function consumeToken()local curChar=curChar if WHITESPACE_LOOKUP[curChar]then return elseif PARENTHESIS_LOOKUP[curChar]then return createParenthesesToken(curChar,curCharPos)elseif IDENTIFIER_LOOKUP[curChar]then return createVariableToken(consumeIdentifier(),curCharPos)elseif curChar==","then return createCommaToken(curCharPos)else local operator=consumeOperator()if operator then return createOperatorToken(operator,curCharPos)end return consumeConstant()end end local function consumeTokens()local tokens,tokensLen={},0 local curChar=curChar while curChar~="\0"do local newToken=consumeToken()if newToken then tokensLen=tokensLen+1 tokens[tokensLen]=newToken end curChar=consume()end return tokens end local function resetToInitialState(expression,givenOperators)if expression then expression=expression charStream=stringToTableCache[expression]or stringToTable(expression)curChar=charStream[1]curCharPos=1 stringToTableCache[expression]=charStream end operatorsTrie=(givenOperators and makeTrie(givenOperators))or DEFAULT_OPERATORS_TRIE operators=givenOperators or DEFAULT_OPERATORS end local function run()assert(charStream,ERROR_NO_CHAR_STREAM)errors={}local tokens=consumeTokens()displayErrors()return tokens end return{resetToInitialState=resetToInitialState,run=run}end return Lexer end)("Lexer/Lexer")local Parser_NodeFactory_module=(function(...)local NodeFactory={}function NodeFactory.createUnaryOperatorNode(operator,operand)return{TYPE="UnaryOperator",Value=operator,Operand=operand}end function NodeFactory.createOperatorNode(operator,left,right)return{TYPE="Operator",Value=operator,Left=left,Right=right}end function NodeFactory.createFunctionCallNode(functionName,arguments)return{TYPE="FunctionCall",FunctionName=functionName,Arguments=arguments}end return NodeFactory end)("Parser/NodeFactory")local Parser_Parser_module=(function(...)local Helpers=Helpers_Helpers_module local NodeFactory=Parser_NodeFactory_module local stringToTable=Helpers.stringToTable local insert=table.insert local concat=table.concat local max=math.max local min=math.min local rep=string.rep local createUnaryOperatorNode=NodeFactory.createUnaryOperatorNode local createOperatorNode=NodeFactory.createOperatorNode local createFunctionCallNode=NodeFactory.createFunctionCallNode local CONTEXT_CHAR_RANGE=20 local ERROR_NO_TOKENS="No tokens given"local ERROR_NO_TOKENS_TO_PARSE="No tokens to parse"local ERROR_EXPECTED_EOF="Expected EOF, got '%s'"local ERROR_UNEXPECTED_TOKEN="Unexpected token: '%s' in <primary>, expected constant, variable or function call"local ERROR_EXPECTED_EXPRESSION="Expected expression, got EOF"local ERROR_EXPECTED_CLOSING_PARENTHESIS="Expected ')', got EOF"local ERROR_EXPECTED_COMMA_OR_CLOSING_PARENTHESIS="Expected ',' or ')', got '%s'"local ERROR_NO_CHARSTREAM="<No charStream, error message: %s>"local DEFAULT_OPERATOR_PRECEDENCE_LEVELS={Unary={["-"]=4},Binary={["^"]=3,["*"]=2,["/"]=2,["%"]=2,["+"]=1,["-"]=1},RightAssociativeBinaryOperators={["^"]=true}}local ParserMethods={}local function Parser(tokens,operatorPrecedenceLevels,tokenIndex,expression)local currentTokenIndex,currentToken if tokens then currentTokenIndex=tokenIndex or 1 currentToken=tokens[currentTokenIndex]end local operatorPrecedenceLevels=operatorPrecedenceLevels or DEFAULT_OPERATOR_PRECEDENCE_LEVELS local expression=expression local function peek(n)return tokens[currentTokenIndex+(n or 1)]end local function consume(n)local newCurrentTokenIndex=currentTokenIndex+(n or 1)local newCurrentToken=tokens[newCurrentTokenIndex]currentTokenIndex=newCurrentTokenIndex currentToken=newCurrentToken return newCurrentToken end local function isBinaryOperator(token)local token=token or currentToken if not operatorPrecedenceLevels.Binary then return end return token and token.TYPE=="Operator"and operatorPrecedenceLevels.Binary[token.Value]end local function isUnaryOperator(token)local token=token or currentToken if not operatorPrecedenceLevels.Unary then return end return token and token.TYPE=="Operator"and operatorPrecedenceLevels.Unary[token.Value]end local function isRightAssociativeBinaryOperator(token)local token=token or currentToken if not operatorPrecedenceLevels.RightAssociativeBinaryOperators then return end return token and token.TYPE=="Operator"and operatorPrecedenceLevels.RightAssociativeBinaryOperators[token.Value]end local function isFunctionCall()local nextToken=peek()if not nextToken then return end return currentToken.TYPE=="Variable"and nextToken.TYPE=="Parentheses"and nextToken.Value=="("end local function getPrecedence(token)return token and operatorPrecedenceLevels.Binary[token.Value]end local function generateError(message,...)if not expression then return ERROR_NO_CHARSTREAM:format(message)end local charStream=stringToTable(expression)local message=message:format(...)local position=(not currentToken and#charStream+1)or currentToken.Position local strippedExpressionTable={}for index=max(1,position-CONTEXT_CHAR_RANGE),min(position+CONTEXT_CHAR_RANGE,#charStream)do insert(strippedExpressionTable,charStream[index])end local strippedExpression=table.concat(strippedExpressionTable)local pointer=rep(" ",position-1).."^"return"\n"..strippedExpression.."\n"..pointer.."\n"..message end local parseFunctionCall,parseBinaryOperator,parseUnaryOperator,parsePrimaryExpression,parseExpression function parseFunctionCall()local functionName=currentToken.Value consume(2)local arguments={}while true do local argument=parseExpression()insert(arguments,argument)if not currentToken then local lastToken=peek(-1)if lastToken.TYPE=="Comma"then error(generateError(ERROR_EXPECTED_EXPRESSION))end error(generateError(ERROR_EXPECTED_CLOSING_PARENTHESIS))elseif currentToken.Value==")"then break elseif currentToken.TYPE=="Comma"then consume()else error(generateError(ERROR_EXPECTED_COMMA_OR_CLOSING_PARENTHESIS,currentToken.Value))end end consume()return createFunctionCallNode(functionName,arguments)end function parseBinaryOperator(minPrecedence)local expression=parseUnaryOperator()while isBinaryOperator(currentToken)do local precedence=getPrecedence(currentToken)if precedence<=minPrecedence and not isRightAssociativeBinaryOperator(currentToken)then break end local operatorToken=currentToken if not consume()then error(generateError(ERROR_EXPECTED_EXPRESSION))end local right=parseBinaryOperator(precedence)expression=createOperatorNode(operatorToken.Value,expression,right)end return expression end function parseUnaryOperator()if not isUnaryOperator(currentToken)then return parsePrimaryExpression()end local operator=currentToken.Value if not consume()then error(generateError(ERROR_EXPECTED_EXPRESSION))end local expression=parseUnaryOperator()return createUnaryOperatorNode(operator,expression)end function parsePrimaryExpression()local token=currentToken if not token then return end local tokenValue=token.Value local tokenType=token.TYPE if tokenType=="Parentheses"and tokenValue=="("then consume()local expression=parseExpression()if not currentToken or currentToken.Value~=")"then error(generateError(ERROR_EXPECTED_CLOSING_PARENTHESIS))end consume()return expression elseif tokenType=="Variable"then if isFunctionCall()then return parseFunctionCall()end consume()return token elseif tokenType=="Constant"then consume()return token end error(generateError(ERROR_UNEXPECTED_TOKEN,tokenValue))end function parseExpression()local expression=parseBinaryOperator(0)return expression end local function resetToInitialState(givenTokens,givenOperatorPrecedenceLevels,givenTokenIndex,givenExpression)assert(givenTokens,ERROR_NO_TOKENS)tokens=givenTokens currentTokenIndex=givenTokenIndex or 1 currentToken=givenTokens[currentTokenIndex]operatorPrecedenceLevels=givenOperatorPrecedenceLevels or DEFAULT_OPERATOR_PRECEDENCE_LEVELS expression=givenExpression end local function parse(noErrors)assert(tokens,ERROR_NO_TOKENS_TO_PARSE)local expression=parseExpression()if currentToken and not noErrors then error(generateError(ERROR_EXPECTED_EOF,currentToken.Value))end return expression end return{resetToInitialState=resetToInitialState,parse=parse}end return Parser end)("Parser/Parser")local scriptPath,requirePath,localPath,oldPath if not LUAXEN_PACKER then scriptPath=debug.getinfo(1).source:match("@?(.*/)")or""requirePath=scriptPath.."./?.lua"localPath=scriptPath.."./"oldPath=package.path package.path=package.path..";"..requirePath end local Helpers=Helpers_Helpers_module local Evaluator=Evaluator_Evaluator_module local Lexer=Lexer_Lexer_module local Parser=Parser_Parser_module local MathParserMethods={}function MathParserMethods:tokenize(expression)if self.cachedTokens[expression]then return self.cachedTokens[expression]end self.Lexer.resetToInitialState(expression,self.operators)local tokens=self.Lexer.run()self.cachedTokens[expression]=tokens return tokens end function MathParserMethods:parse(tokens,expression)if self.cachedASTs[expression]then return self.cachedASTs[expression]end self.Parser.resetToInitialState(tokens,self.operatorPrecedenceLevels,nil,expression)local AST=self.Parser.parse()self.cachedASTs[expression]=AST return AST end function MathParserMethods:evaluate(AST)if self.cachedResults[AST]then return self.cachedResults[AST]end self.Evaluator.resetToInitialState(AST,self.variables,self.operatorFunctions,self.functions)local evaluatedValue=self.Evaluator:evaluate()self.cachedResults[AST]=evaluatedValue return evaluatedValue end function MathParserMethods:solve(expression)return self:evaluate(self:parse(self:tokenize(expression),expression))end function MathParserMethods:addVariable(variableName,variableValue)self.variables=self.variables or{}self.variables[variableName]=variableValue self.cachedResults={}end function MathParserMethods:addVariables(variables)for variableName,variableValue in pairs(variables)do self:addVariable(variableName,variableValue)end self.cachedResults={}end function MathParserMethods:addFunction(functionName,functionValue)self.functions=self.functions or{}self.functions[functionName]=functionValue self.cachedResults={}end function MathParserMethods:addFunctions(functions)for functionName,functionValue in pairs(functions)do self:addFunction(functionName,functionValue)end self.cachedResults={}end function MathParserMethods:setOperatorPrecedenceLevels(operatorPrecedenceLevels)self.operatorPrecedenceLevels=operatorPrecedenceLevels self.cachedASTs={}end function MathParserMethods:setVariables(variables)self.variables=variables self.cachedResults={}end function MathParserMethods:setOperatorFunctions(operatorFunctions)self.operatorFunctions=operatorFunctions self.cachedResults={}end function MathParserMethods:setOperators(operators)self.operators=operators self.cachedTokens={}end function MathParserMethods:setFunctions(functions)self.functions=functions self.cachedResults={}end function MathParserMethods:resetCaches()self.cachedTokens={}self.cachedASTs={}self.cachedResults={}end function MathParserMethods:resetToInitialState(operatorPrecedenceLevels,variables,operatorFunctions,operators,functions)self.operatorPrecedenceLevels=operatorPrecedenceLevels self.variables=variables self.operatorFunctions=operatorFunctions self.operators=operators self.functions=functions self.cachedTokens={}self.cachedASTs={}self.cachedResults={}end local MathParser={}function MathParser:new(operatorPrecedenceLevels,variables,operatorFunctions,operators,functions)local MathParserInstance={}for key,value in pairs(MathParserMethods)do MathParserInstance[key]=value end MathParserInstance.operatorPrecedenceLevels=operatorPrecedenceLevels MathParserInstance.variables=variables MathParserInstance.operatorFunctions=operatorFunctions MathParserInstance.operators=operators MathParserInstance.functions=functions MathParserInstance.cachedTokens={}MathParserInstance.cachedASTs={}MathParserInstance.cachedResults={}MathParserInstance.Lexer=Lexer(nil,operators)MathParserInstance.Parser=Parser(nil,operatorPrecedenceLevels)MathParserInstance.Evaluator=Evaluator(nil,variables,operatorFunctions,functions)return MathParserInstance end if not LUAXEN_PACKER then package.path=oldPath end return MathParser