You would search the tokenized expression for each operator in order, and choose them like that. If you find a parentheses, find its pair and send the contents back through the routine recursively.
Here is an example in C# (this is what tiDE uses) that is very similar to this routine, but it skips the tokenizing step.
Code: /// <summary>
/// Parses an expression, performing all required math, and
/// returns the binary equivalent with the specified number of bits.
/// This handles references and constants as well. Use this
/// method to parse code like this:
/// ld hl, PlotsScreen - (12 * 16h) + 2 + 'd'
/// This method adds an error and returns an empty value if neccissary
/// </summary>
private string ParseExpression(string Expression, int numBits,
bool offsetFromCurrent = false, int subtractFromValue = 0, bool negateValue = false, bool LittleEndian = true)
{
string value = "";
// How this is done:
// First, find all constants and replace them with their decimal equivalents
// Replace all hex/binary/characters with their decimal equivalents
// Create a stack of operations, push them to the stack according to order of operations
// Pop each item from the stack and execute it
// Check that the expression fits the number of available bits
// If it doesn't, add an error and return the default value
// Otherwise, return the result
// TODO: Handle non-literals
ushort parsedValue = 0;
if (UseOrderOfOperations)
{
parsedValue = ParseSubexpressionOOO(Expression, offsetFromCurrent);
}
else
{
}
if (offsetFromCurrent)
parsedValue = (ushort)(parsedValue - (ushort)OutputBytes.Count);
parsedValue -= (ushort)subtractFromValue;
if (negateValue)
parsedValue = (ushort)-parsedValue;
value = Convert.ToString(parsedValue, 2);
if (numBits != -1)
{
if (value.Length > numBits)
value = value.Substring(numBits);
while (value.Length < numBits)
value = "0" + value;
while (value.Length > numBits)
value = value.Remove(value.Length - 1);
if (numBits == 16 && LittleEndian)
value = value.Substring(8) + value.Remove(8); // Little endian
}
return value;
}
private int FindClosingParenthesis(string Value, int Opening)
{
int numParenthesis = 0, length = 0;
for (int i = Opening; i < Value.Length; i++)
{
if (Value[i] == '(')
numParenthesis++;
if (Value[i] == ')')
numParenthesis--;
if (numParenthesis == 0)
return length;
length++;
}
return -1;
}
/// <summary>
/// Parses a subexpression using order of operations
/// </summary>
/// <param name="Expression"></param>
/// <returns></returns>
private ushort ParseSubexpressionOOO(string Expression, bool offestFromCurrent = false)
{
// Recursively parse parenthesis first
if (Expression.Contains('('))
{
int opening = Expression.IndexOf("(");
ushort value = ParseSubexpressionOOO(Expression.Substring(opening + 1,
FindClosingParenthesis(Expression, opening) - 1));
Expression = Expression.Remove(opening,
FindClosingParenthesis(Expression, opening) + 1);
Expression = Expression.Insert(opening, value.ToString());
}
bool negative = false;
if (Expression.StartsWith("-"))
{
negative = true;
Expression = Expression.Substring(1);
}
while (HasMathSymbols(Expression))
{
if (Expression.Contains("*"))
{
string value1 = Expression.Substring(0, Expression.IndexOf("*"));
string value2 = Expression.Substring(Expression.IndexOf("*") + 1);
int startIndex = 0, length = 0;
for (int i = value1.Length - 1; i != -1; i--)
{
if ("*-+/|^&".Contains(value1[i]))
{
value1 = value1.Substring(i + 1);
startIndex = i + 1;
break;
}
}
for (int i = 0; i < value2.Length; i++)
{
if ("*-+/|^&".Contains(value2[i]))
{
value2 = value2.Remove(i);
length = value1.Length + i + 1;
break;
}
}
if (length == 0)
length = Expression.Length - startIndex;
ushort result = (ushort)(ParseValue(value1, offestFromCurrent) * ParseValue(value2, offestFromCurrent));
Expression = Expression.Remove(startIndex, length);
Expression = Expression.Insert(startIndex, result.ToString());
continue;
}
if (Expression.Contains("/"))
{
string value1 = Expression.Substring(0, Expression.IndexOf("/"));
string value2 = Expression.Substring(Expression.IndexOf("/") + 1);
int startIndex = 0, length = 0;
for (int i = value1.Length - 1; i != -1; i--)
{
if ("*-+/|^&".Contains(value1[i]))
{
value1 = value1.Substring(i + 1);
startIndex = i + 1;
break;
}
}
for (int i = 0; i < value2.Length; i++)
{
if ("*-+/|^&".Contains(value2[i]))
{
value2 = value2.Remove(i);
length = value1.Length + i + 1;
break;
}
}
if (length == 0)
length = Expression.Length;
ushort result = (ushort)(ParseValue(value1, offestFromCurrent) / ParseValue(value2, offestFromCurrent));
Expression = Expression.Remove(startIndex, length);
Expression = Expression.Insert(startIndex, result.ToString());
continue;
}
if (Expression.Contains("+"))
{
string value1 = Expression.Substring(0, Expression.IndexOf("+"));
string value2 = Expression.Substring(Expression.IndexOf("+") + 1);
int startIndex = 0, length = 0;
for (int i = value1.Length - 1; i != -1; i--)
{
if ("*-+/|^&".Contains(value1[i]))
{
value1 = value1.Substring(i + 1);
startIndex = i + 1;
break;
}
}
for (int i = 0; i < value2.Length; i++)
{
if ("*-+/|^&".Contains(value2[i]))
{
value2 = value2.Remove(i);
length = value1.Length + i + 1;
break;
}
}
if (length == 0)
length = Expression.Length;
ushort result = (ushort)(ParseValue(value1, offestFromCurrent) + ParseValue(value2, offestFromCurrent));
Expression = Expression.Remove(startIndex, length);
Expression = Expression.Insert(startIndex, result.ToString());
continue;
}
if (Expression.Contains("-"))
{
string value1 = Expression.Substring(0, Expression.IndexOf("-"));
string value2 = Expression.Substring(Expression.IndexOf("-") + 1);
int startIndex = 0, length = 0;
for (int i = value1.Length - 1; i != -1; i--)
{
if ("*-+/|^&".Contains(value1[i]))
{
value1 = value1.Substring(i + 1);
startIndex = i + 1;
break;
}
}
for (int i = 0; i < value2.Length; i++)
{
if ("*-+/|^&".Contains(value2[i]))
{
value2 = value2.Remove(i);
length = value1.Length + i + 1;
break;
}
}
if (length == 0)
length = Expression.Length;
ushort result = (ushort)(ParseValue(value1, offestFromCurrent) - ParseValue(value2, offestFromCurrent));
Expression = Expression.Remove(startIndex, length);
Expression = Expression.Insert(startIndex, result.ToString());
continue;
}
}
if (negative)
return (ushort)(-(int)ParseValue(Expression, offestFromCurrent));
return ParseValue(Expression, offestFromCurrent);
}
private bool HasMathSymbols(string Expression)
{
bool inString = false;
bool inChar = false;
foreach (char c in Expression)
{
if (c == '"' && !inString)
inChar = !inChar;
if (c == '\'' && !inChar)
inString = !inString;
if ("+-*/|&^".Contains(c) && !inString && !inChar)
return true;
}
return false;
}
private string GetWithinParenthesis(string Value)
{
int startIndex = -1, length = 0;
int numOpen = 0, i = 0;
foreach (char c in Value)
{
if (c == '(')
{
if (numOpen == 0)
startIndex = i;
numOpen++;
}
if (c == ')')
{
numOpen--;
if (numOpen == 0)
break;
}
if (numOpen != 0)
length++;
i++;
}
if (startIndex == -1)
return "";
return Value.Substring(startIndex, length);
}
I was always wondering this, but how does this method handle nested parentheses? (As-in put them in order-of-ops)