A couple years ago, I wrote an article showing how to empower game designers with the ability to write simple formulas like `PlayerLevel*100+100`. These are much more useful than just constants and don’t require any of the complexity of a real programming language. Today we’ll bring it into the Burst-compatible world and also improve its ability to handle more complex formulas.

###### Problems

We left off with a formula evaluator that had these features:

• Constants like `123.45`. Values are `double`: 64-bit float.
• Variables like `health`. Uppercase, lowercase, and underscores allowed.
• Arithmetic operators: `+ - * / %`
• ``` ```
``` That was back in the Unity 2017.1 days. From today's 2019.2 perspective, we now notice that we're lacking the ability to evaluate expressions within Burst-compiled jobs. That's because the code uses strings, exceptions, and classes like List<T> and HashMap<T>. More fundamentally, formulas were executed from left to right in a simplistic way without any operator precedence at all. This meant that we could write a formula like this: x*3+1 And it would be evaluated, as expected, like this: (x*3)+1 But we couldn't write a formula like this: x+1*3 The reason is that it would be evaluated like this: (x+1)*3 It also lacked support for parentheses, so we couldn't write formulas like this: (x+1)*(y-2) There's no way to even rearrange this formula so that it would work without parentheses. We also couldn't add any spaces to make the formula more clear, like this: x*x + y*y + z*z We'll fix all of these issues today. Burst Compatibility First, let's add Burst support. The key here is to recognize that there are two main operations: compiling and evaluating. Compiling requires the formula string and so it'll never be supported in Burst. Evaluating, however, doesn't need the formula string so it should be possible to execute in Burst. To get the strings out of the Formula struct, we need to look at its only field: private List<Node> nodes; Node looks like this: private struct Node { public NodeType Type; public string Name; public double Value; public bool HasValue; } So we need to get rid of the List<Node> and get rid of the string Name field of Node in order to store a Formula in a Burst-compiled job. Getting rid of List<T> is easy: just swap in NativeArray<T> and handle dynamically growing it manually like so: // Double the length to avoid growing for every single new element NativeArray<Node> newNodes = new NativeArray<Node>(nodes.Length * 2, allocator); for (int i = 0; i < nodes.Length; ++i) { newNodes[i] = nodes[i]; } nodes.Dispose(); nodes = newNodes; To get rid of the string, we can build an array of variable names during compilation and only store the index into that array. This means setting variable values changes a little: // Old formula.SetVariable("level", 10);   // New formula.SetVariable(Array.IndexOf(compileResult.Variables, "level"), 10); Next, we need to get rid of the exceptions. Instead, we'll return a struct to tell the caller about the result of the compilation: public struct CompileResult { public bool Success; public Formula Formula; public string[] Variables; } Precedence and Parentheses To support operator precedence and parentheses, we need to split compilation into two parts: Parse the source string into nodes Reorder the nodes into "postfix order" (a.k.a. Reverse Polish Notation) The reason for the second step is because we want to be able to write in so-called "infix order" as math generally appears: x + 1 Evaluating infix expressions is very difficult though, so we'll reorder them so they're into postfix order: x 1 + In this order, evaluation is simple! When we encounter a constant or variable, we push it onto a stack. When we encounter an operator, we pop two values off the stack, apply the operator to them, and push the result onto the stack. The output is whatever's left on the stack. So for the above example of x 1 + when x has the value 10: Node Action Stack x Evaluate x 10 Push 10 10 1 Push 1 10 1 + Pop 1 10 Pop 10 Add 1 and 10 Push 11 11 The result is the 11 left on the stack. To do the reordering, we employ the Shunting Yard Algorithm. It uses a queue and a stack which we can easily allocate with NativeArray<Node> using Allocator.Temp without fearing creating any garbage. This algorithm support parentheses, so we can add them to our parsing step. We'll also add support for spaces, which we simply skip. Usage Now that we've made these changes, let's try out the system starting with a Burst-compiled job that evaluates formulas: [BurstCompile] struct FormulaJob : IJob { public Formula Formula; public NativeArray<double> Result;   public void Execute() { Result = Formula.Evaluate(); } } In order to feed in a Formula, let's compile one outside of the Burst job: Formula.CompileResult result = Formula.Compile( "(NumTargetsHit*100) - (NumTargetsMissed*50)", Allocator.TempJob); if (!result.Success) { Debug.LogError("Compile error"); } Then we set the variables' values: Formula formula = result.Formula; string[] variables = result.Variables;   formula.SetVariable(Array.IndexOf(variables, "NumTargetsHit"), 5); formula.SetVariable(Array.IndexOf(variables, "NumTargetsMissed"), 1); Now we can run the job: var evalResults = new NativeArray<double>(1, Allocator.TempJob); new FormulaJob { Formula = formula, Result = evalResults }.Run(); double evalResult = evalResults; evalResults.Dispose(); We have the result back from the job, so let's print it: Debug.Log("Result: " + evalResult); We see the expected result: 450! Source Code Here's the full source code for the formula compiler and evaluator. It weighs at just 452 SLOC: using System; using Unity.Collections;   /// <summary> /// Compiler and evaluator of simple formulas. A single line string is compiled /// and evaluated to produce a number result. It may consist of constants, /// variables, arithmetic operators (+, -, *, /, %), and parentheses. /// For example: <code>100*level+50</code> /// </summary> /// /// <example> /// Formula.CompileResult compileResult = Formula.Compile("level*50+100"); /// if (!compileResult.Success) /// { /// Debug.LogError("Compile error"); /// } /// else /// { /// Formula formula = compileResult.Formula; /// formula.SetVariable(Array.IndexOf(compileResult.Variables, "level"), 5); /// Debug.LogFormat("Result: {0}", formula.Evaluate()); /// } /// </example> /// /// <author> /// Jackson Dunstan, https://JacksonDunstan.com/articles/5385 /// </author> /// /// <license> /// MIT /// </license> public struct Formula : IDisposable { /// <summary> /// The result of calling <see cref="Compile"/> /// </summary> public struct CompileResult { public bool Success; public Formula Formula; public string[] Variables; }   /// <summary> /// Compile a formula string /// </summary> /// /// <param name="source"> /// Source to compile /// </param> /// /// <param name="allocator"> /// Allocator to allocate the formula with /// </param> /// /// <returns> /// The result of compilation /// </returns> public static CompileResult Compile(string source, Allocator allocator) { CompileResult result = ParseInfixFormula(source, allocator); if (!result.Success) { return default; }   if (!ConvertInfixToPostfix(ref result.Formula)) { result.Formula.Dispose(); return default; }   result.Formula.AllocateStack(allocator);   return result; }   /// <summary> /// Set a variable's value /// </summary> /// /// <param name="index"> /// Index of the variable in <see cref="CompileResult.Variables"/> /// </param> /// /// <param name="value"> /// Value of the variable /// </param> public void SetVariable(int index, double value) { for (int i = 0, count = m_NumNodes; i < count; ++i) { Node node = m_Nodes[i]; if (node.Type == NodeType.Variable && (int)node.Value == index) { node.Value = value; m_Nodes[i] = node; } } }   /// <summary> /// Evaluate the formula /// </summary> /// /// <returns> /// The result of evaluating the formula /// </returns> public double Evaluate() { int top = 0; for (int i = 0; i < m_NumNodes; ++i) { Node curNode = m_Nodes[i]; switch (curNode.Type) { case NodeType.Constant: m_Stack[top] = curNode.Value; top++; break; case NodeType.Variable: m_Stack[top] = curNode.Value; top++; break; case NodeType.Add: m_Stack[top - 2] = m_Stack[top - 2] + m_Stack[top - 1]; top--; break; case NodeType.Subtract: m_Stack[top - 2] = m_Stack[top - 2] - m_Stack[top - 1]; top--; break; case NodeType.Multiply: m_Stack[top - 2] = m_Stack[top - 2] * m_Stack[top - 1]; top--; break; case NodeType.Divide: m_Stack[top - 2] = m_Stack[top - 2] / m_Stack[top - 1]; top--; break; case NodeType.Modulus: m_Stack[top - 2] = m_Stack[top - 2] % m_Stack[top - 1]; top--; break; } }   return m_Stack; }   /// <summary> /// Dispose of any memory the formula holds /// </summary> public void Dispose() { if (m_Nodes.IsCreated) { m_Nodes.Dispose(); } if (m_Stack.IsCreated) { m_Stack.Dispose(); } }   private enum NodeType { Constant, Variable, Add, Subtract, Multiply, Divide, Modulus, LeftParen, RightParen, }   private struct Node { public NodeType Type; public double Value; }   private NativeArray<Node> m_Nodes; private int m_NumNodes; private NativeArray<double> m_Stack;   private void AddNode(Allocator allocator, in Node node) { if (!m_Nodes.IsCreated) { m_Nodes = new NativeArray<Node>(8, allocator); } else if (m_NumNodes >= m_Nodes.Length) { NativeArray<Node> newNodes = new NativeArray<Node>( m_Nodes.Length * 2, allocator); for (int i = 0; i < m_Nodes.Length; ++i) { newNodes[i] = m_Nodes[i]; } m_Nodes.Dispose(); m_Nodes = newNodes; } m_Nodes[m_NumNodes] = node; m_NumNodes++; }   private void AllocateStack(Allocator allocator) { m_Stack = new NativeArray<double>(m_NumNodes, allocator); }   private static int GetPrecedence(NodeType type) { switch (type) { case NodeType.Add: return 2; case NodeType.Subtract: return 2; case NodeType.Multiply: return 3; case NodeType.Divide: return 3; case NodeType.Modulus: return 3; default: return -1; } }   private static bool AreSubstringsEqual( string str, (int startIndex, int length) subA, (int startIndex, int length) subB) { if (subA.length != subB.length) { return false; } for (int i = 0; i < subA.length; ++i) { if (str[subA.startIndex + i] != str[subB.startIndex + i]) { return false; } } return true; }   private static CompileResult ParseInfixFormula( string source, Allocator allocator) { // Parse the source into the formula // Keep track of the size of the stack when it's evaluated NativeArray<(int startIndex, int length)> variables = default; int numVariables = 0; Formula formula = new Formula(); int stackSize = 0; for (int i = 0; i < source.Length; ) { char curChar = source[i];   // Constant if ((curChar >= '0' && curChar <= '9') || curChar == '.') { // Find the end int startIndex = i; do { i++; if (i >= source.Length) { break; } curChar = source[i]; } while ((curChar >= '0' && curChar <= '9') || curChar == '.');   // Parse the value double value; if (!double.TryParse( source.Substring(startIndex, i - startIndex), out value)) { formula.Dispose(); return default; }   // Add the node stackSize++; formula.AddNode( allocator, new Node { Type = NodeType.Constant, Value = value }); } // Variable else if ( (curChar >= 'a' && curChar <= 'z') || (curChar >= 'A' && curChar <= 'Z') || curChar == '_') { stackSize++;   // Find the end int startIndex = i; do { i++; if (i >= source.Length) { break; } curChar = source[i]; } while ( (curChar >= 'a' && curChar <= 'z') || (curChar >= 'A' && curChar <= 'Z') || curChar == '_');   // Find existing variable (int, int) variable = (startIndex, i - startIndex); bool found = false; for (int j = 0; j < numVariables; ++j) { if (AreSubstringsEqual(source, variables[j], variable)) { formula.AddNode( allocator, new Node { Type = NodeType.Variable, Value = j }); found = true; break; } }   if (!found) { // Initial variables allocation if (!variables.IsCreated) { variables = new NativeArray<(int, int)>(8, Allocator.Temp); } // Grow variables to fit more else if (variables.Length == numVariables) { var newVariables = new NativeArray<(int, int)>( variables.Length * 2, Allocator.Temp); for (int j = 0; j < numVariables; ++j) { newVariables[j] = variables[j]; } variables.Dispose(); variables = newVariables; }   formula.AddNode( allocator, new Node { Type = NodeType.Variable, Value = numVariables });   variables[numVariables] = variable; numVariables++; } } // Add else if (curChar == '+') { stackSize--; i++; formula.AddNode( allocator, new Node { Type = NodeType.Add }); } // Subtract else if (curChar == '-') { stackSize--; i++; formula.AddNode( allocator, new Node { Type = NodeType.Subtract }); } // Multiply else if (curChar == '*') { stackSize--; i++; formula.AddNode( allocator, new Node { Type = NodeType.Multiply }); } // Divide else if (curChar == '/') { stackSize--; i++; formula.AddNode( allocator, new Node { Type = NodeType.Divide }); } // Modulus else if (curChar == '%') { stackSize--; i++; formula.AddNode( allocator, new Node { Type = NodeType.Modulus }); } // Left paren else if (curChar == '(') { i++; formula.AddNode( allocator, new Node { Type = NodeType.LeftParen }); } // Right paren else if (curChar == ')') { i++; formula.AddNode( allocator, new Node { Type = NodeType.RightParen }); } // Space else if (curChar == ' ') { i++; } // Illegal else { formula.Dispose(); return default; } }   // There must be one element left on the stack as a result of evaluating if (stackSize != 1) { formula.Dispose(); return default; }   // Create strings from variable indices string[] variableStrings = null; if (variables.IsCreated) { variableStrings = new string[numVariables]; for (int i = 0; i < numVariables; ++i) { (int startIndex, int length) variable = variables[i]; variableStrings[i] = source.Substring( variable.startIndex, variable.length); } variables.Dispose(); }   return new CompileResult { Success = true, Formula = formula, Variables = variableStrings }; }   private static bool ConvertInfixToPostfix(ref Formula formula) { // Convert using the Shunting Yard algorithm // This calls for an output queue and an operator stack // Use temporary allocation since we only need them for this function NativeArray<Node> outputQueue = new NativeArray<Node>( formula.m_Nodes.Length, Allocator.Temp); NativeArray<Node> opStack = new NativeArray<Node>( formula.m_Nodes.Length, Allocator.Temp); int outputQueueIndex = 0; int opStackIndex = 0;   for (int i = 0; i < formula.m_NumNodes; ++i) { Node curNode = formula.m_Nodes[i]; switch (curNode.Type) { case NodeType.Constant: case NodeType.Variable: outputQueue[outputQueueIndex] = curNode; outputQueueIndex++; break; case NodeType.Add: case NodeType.Subtract: case NodeType.Multiply: case NodeType.Divide: case NodeType.Modulus: int curPrecedence = GetPrecedence(curNode.Type); while (opStackIndex > 0) { Node opTop = opStack[opStackIndex - 1]; if (opTop.Type == NodeType.LeftParen || GetPrecedence(opTop.Type) < curPrecedence) { break; }   // Pop off operator stack. Push onto output queue. opStackIndex--; outputQueue[outputQueueIndex] = opTop; outputQueueIndex++; }   opStack[opStackIndex] = curNode; opStackIndex++; break; case NodeType.LeftParen: opStack[opStackIndex] = curNode; opStackIndex++; break; case NodeType.RightParen: while (true) { if (opStackIndex <= 0) { outputQueue.Dispose(); opStack.Dispose(); return false; }   Node opTop = opStack[opStackIndex - 1]; if (opTop.Type == NodeType.LeftParen) { break; }   // Pop off operator stack. Push onto output queue. opStackIndex--; outputQueue[outputQueueIndex] = opTop; outputQueueIndex++; }   // Pop any left paren off operator stack and discard if (opStackIndex > 0 && opStack[opStackIndex - 1].Type == NodeType.LeftParen) { opStackIndex--; } break; } }   // Copy output to formula then pop operator stack into formula int formulaIndex = 0; for (int i = 0; i < outputQueueIndex; ++i) { formula.m_Nodes[formulaIndex] = outputQueue[i]; formulaIndex++; } for (int i = opStackIndex - 1; i >= 0; --i) { Node topNode = opStack[i]; if (topNode.Type == NodeType.LeftParen) { outputQueue.Dispose(); opStack.Dispose(); return false; } formula.m_Nodes[formulaIndex] = topNode; formulaIndex++; } formula.m_NumNodes = formulaIndex;   // Free temporaries outputQueue.Dispose(); opStack.Dispose();   return true; } } Here are some unit tests to go along with this: using System; using NUnit.Framework; using Unity.Collections;   public class FormulaTests { [TestCase("")] [TestCase("+")] [TestCase("+5")] [TestCase("5+")] [TestCase("(")] [TestCase(")")] [TestCase("()")] [TestCase("((5)")] [TestCase("(5))")] [TestCase("(5")] [TestCase("5)")] [TestCase("5++5")] [TestCase("5..5")] [TestCase("x.5")] [TestCase("x5")] [TestCase("5.x")] public void InvalidFormulaDoesNotCompile(string code) { Formula.CompileResult result = Formula.Compile(code, Allocator.Temp);   Assert.That(result.Success, Is.False); }   [TestCase("5", 5)] [TestCase(" 5", 5)] [TestCase("5 ", 5)] [TestCase(" 5 ", 5)] [TestCase("3.1415", 3.1415)] [TestCase("4+2", 6)] [TestCase("5-1", 4)] [TestCase("4*2", 8)] [TestCase("6/2", 3)] [TestCase("6%4", 2)] [TestCase("(4+2)", 6)] [TestCase("4+2*3", 10)] [TestCase("(4+2)*3", 18)] [TestCase("(4+((4+2)*3))*3", 66)] [TestCase("4*2+3", 11)] [TestCase("ten+2*3", 16)] [TestCase("ten+twenty*3", 70)] [TestCase("ten+twenty*thirty", 610)] [TestCase("ten+ten", 20)] public void FormulaEvaluatesToCorrectResult(string code, double expected) { Formula.CompileResult result = Formula.Compile(code, Allocator.Temp);   Assert.That(result.Success, Is.True);   Formula formula = result.Formula; if (result.Variables != null) { formula.SetVariable(Array.IndexOf(result.Variables, "ten"), 10); formula.SetVariable(Array.IndexOf(result.Variables, "twenty"), 20); formula.SetVariable(Array.IndexOf(result.Variables, "thirty"), 30); }   double actual = formula.Evaluate();   Assert.That(actual, Is.EqualTo(expected)); } } Conclusion Today we've seen how easy it is to port pre-Burst code so that Burst can compile it, even when that code was using strings, exceptions, and collections. We've also seen how to compile and evaluate more complex infix expressions with operator precedence and parentheses. The resulting system is a useful tool to give to game designers without the fear of them writing arbitrarily complex and slow code. Now they can express things like damage calculations in a formula that they can iterate on without the need for a programmer to modify C# code. It's much more powerful than giving them simple constants, yet it's still very approachable. Share on FacebookShare on TwitterShare on LinkedinShare on Reddit ```