String Parsing and Brackets

[balabaster]

I'm looking for some ideas regarding string parsing and brackets.

Say I have the following string:

56*(73+23/(28+(7/14)-(3/2))

What would be the best way to parse the string for each opening bracket's closing bracket? Is there a standard way of doing this out there somewhere that I've failed to find?

As you can see by parsing the string visually, we're missing a closing bracket, and a simple count of opening braces and closing braces to check for a match will tell us one is missing

However, I'd like to highlight each set of braces when the cursor is inside a pair of brackets, or if I type a bracket, it automatically bolds it's corresponding pair. For instance, if I type a closing bracket, it's corresponding opening bracket is bolded, or if I change the position of the cursor, any brackets bounding the current cursor position is bolded.

Is this something that can easily be done using some application of regular expressions for instance that I have missed?

If anyone has a simple method of doing this, I would appreciate some insight into the method they used.

[cloud255]

Well counting braces i guess is the way to go, i would look for the last "(" brace first with the LastIndexOf() method and match that with the first ")" brace.
Then make a substring which excludes everything between that pair of braces. and repeat the process. Look into recursion for this.

This actaully looks like a really good exercise. if you get stuck/find a solution would you mind posting the code, i would love to have a look at it.

[balabaster]

Well counting braces i guess is the way to go, i would look for the last "(" brace first with the LastIndexOf() method and match that with the first ")" brace.
Then make a substring which excludes everything between that pair of braces. and repeat the process. Look into recursion for this.

This actaully looks like a really good exercise. if you get stuck/find a solution would you mind posting the code, i would love to have a look at it.

If I'm going to be parsing the string, then for sure recursion looks like the ideal solution. The LastIndexOf() method won't work as the last bracket doesn't always pair with the first...

Consider the following example:

(2+3)*(3+(27/(3*26)))

The final bracket actually matches with the second opening bracket in this case. I think the trick is to recurse until there are no more brackets inside any given pair and then work your way outwards, much like recursion through the file system using a tree or parsing XML or the DOM.

I'm still doing some research, but I will post information as I find that it is useful for this exercise.

[cloud255]

If I'm going to be parsing the string, then for sure recursion looks like the ideal solution. The LastIndexOf() method won't work as the last bracket doesn't always pair with the first...

Consider the following example:

(2+3)*(3+(27/(3*26)))

I see what you mean, a slight modification, still using the lastIndexOf() and then going the first ")" after that index would give you everything between those two brackets and then highlighting that would make any mistakes clearly visible and also conform to the mathematical order of operations (i think)...

But i am pretty confident that a better solution is possible, i'll do some thinking about analyzing the string as a char array and looking at individual elements between 'brace indicies'.

[Plater]

You might be able to look up like "mathmatical regex" and find something that would chunk your string into sections?


(2+3)*(3+(27/(3*26)))

a=3*6
b=27/a
c=3+b
d=2+3
final=d*c

[balabaster]

You might be able to look up like "mathmatical regex" and find something that would chunk your string into sections?


(2+3)*(3+(27/(3*26)))

a=3*6
b=27/a
c=3+b
d=2+3
final=d*c

I'm just investigating that route as we speak... however, the mathematical example was merely an example to demonstrate the need... it's final application won't be strictly mathematical, but will also hold some logical functions, for instance: Min, Max, Avg, Median, In, And, Or, Not

The syntax is not dissimilar to Excel's spreadsheet functions to provide an expression builder for a piece of software I'm writing for a client... This will allow them to code business rules right into their system without having to call me every 10 minutes to ask me to develop a rule and plug it in or change an existing rule. I'm basically trying to build a means of idiot proofing a concept that I haven't finished formulating yet.

A basic example of the expression that could be parsed:
Max(10, 0.1 * (@Value - (@Weight * 2.75)))

Where @Value and @Weight are variables that the user will be prompted for information.

The result of the final calculation would be the highest of $10 or 10% of any value exceeding $2.75 per lb. Essentially providing a standard formula for calculating a value above a minimum charge...

Or another example:

IF(@Value < 5, 0.25, 0)

This could calculate a surcharge of 25c if the amount entered by the user is less than $5.

Or yet another example:

IF(@Value IN (10, 4, 2, 27, 3), 4.5, 2.75)

If the value entered falls within items in the in list, then add a charge of $4.50, otherwise add a charge of $2.75. The IN operator checks a list that may also contain expressions, so expressions could get quite complex.

All that is irrelevant for the moment at this stage though, I'm not yet looking to build the calculation or obtain the result, but to provide some cosmetic solution to make it easier to read when it's being input into the input box (richtext). The method used however, will probably be the same

[balabaster]

Okay, for the mathematical portion of the subject I developed a bunch of regular expressions which can be plugged into a recursive function:

Using the mathematical principles of BoDMAS (Brackets, Division, Multiplication, Addition, Subtraction):

Brackets - Condense brackets out of the equation:
"\([^\(\)]*?\)" = Grab each phrase that doesn't contain any brackets...these can be evaluated as calculations, replace these phrases in the original string with the resulting calculation. Do this recursively until no brackets remain in your original phrase.

Evaluate a simple expression:
Now our phrase has been condensed down to a simple string containing just operands and operators (numbers and +-*\)
"(\d+(\.\d+)?)\s*[\\/\*+\-]\s*(\d+(\.\d+)?)"
Group 1 will contain the first operand
Group 2 will contain the fractional part of the first operand
Group 3 will contain the operator that may be / or \
Group 4 will contain the second operand
Group 5 will contain the fractional part of the second operand
When evaluating this phrase, you can eval the exact (or close to) output if the operator is / or just return the integer part of the result if the operator is \

Hey presto, you've got essentially two fairly small functions that can evaluate the whole phrase. Remember to prevent a user from entering more closing brackets than opening brackets or it could all fall to pieces.

Mental note: Don't forget which order to evaluate division, multiplication, addition and subtraction...

Now, on to including logic into the puzzle... I'll keep you posted.

[balabaster]

Okay, for those that care, I got this down to a single recursive function... and one helper extension for String.Replace to avoid having to build a whole stack and manage all that...

The code's a bit preliminary just now... I'm sure it can be condensed into something a little more elegant - each of the code blocks outside the condensing out of the brackets is so similar that I daresay I can create a separate function for them which is what I will work on next...

    Private Function Evaluate(ByVal Expression As String) As Double
 
        Dim oMatch As Match = Nothing
 
        'If we have any bracketed expressions, then condense them out...
        Dim Pattern As String = "\(([^\(\)]*?\))"
        While Regex.Matches(Expression, Pattern).Count > 0
 
            Dim oRegex As New Regex("\(([^\(\)]*)?\)")
            oMatch = oRegex.Match(Expression)
            Expression = Expression.Replace(oMatch.Index, oMatch.Length, Evaluate(oMatch.Groups(1).Value))
 
        End While
 
        'There are no brackets left, we're onto orders... i.e. powers and roots
        Pattern = "(\d+(\.\d+)?)((\s*\^\s*)|(√\s*))(\d+(\.\d+)?)"
        While Regex.Matches(Expression, Pattern).Count > 0
 
            Dim oMatches = Regex.Matches(Expression, Pattern)
            For Each oMatch In oMatches
 
                Dim Operand1 = oMatch.Groups(0).Value
                Dim [Operator] = oMatch.Groups(2).Value
                Dim Operand2 = oMatch.Groups(5).Value
 
                Dim Result As Double = 0
                Select Case [Operator].ToLower
                    Case "^" : Result = Math.Exp(Math.Log(Operand1) * Operand2)
                    Case "√" : Result = Math.Exp(Math.Log(Operand2) - Math.Log(Operand1))
                End Select
                Expression = Expression.Replace(oMatch.Index, oMatch.Length, Result)
            Next
 
        End While
 
        'All the brackets and orders have been processed, do the division and multiplication first
        Pattern = "(\d+(\.\d+)?)\s*([\\/*×])\s*(\d+(\.\d+)?)" 'All expressions containing / \ or * or ×
        While Regex.Matches(Expression, Pattern).Count > 0
 
            Dim oMatches = Regex.Matches(Expression, Pattern)
            For Each oMatch In oMatches
 
                Dim Operand1 = oMatch.Groups(1).Value
                Dim [Operator] = oMatch.Groups(3).Value
                Dim Operand2 = oMatch.Groups(4).Value
 
                Dim Result As Double = 0
                If IsNumeric(Operand1) And IsNumeric(Operand2) Then
                    Select Case [Operator].ToLower
                        Case "/", "÷" : Result = CDbl(Operand1) / CDbl(Operand2)
                        Case "\" : Result = CDbl(Operand1) \ CDbl(Operand2)
                        Case "*", "×" : Result = CDbl(Operand1) * CDbl(Operand2)
                    End Select
                    Expression = Expression.Replace(oMatch.Index, oMatch.Length, Result)
                End If
 
            Next
 
        End While
 
        'Now we're working left to right because we should only have + and - left
        Pattern = "^(\d+(\.\d+)?)\s*([-+])\s*(\d+(\.\d+)?)" 'First expression in string...
        Dim Total As Double = 0
        While Regex.Matches(Expression, Pattern).Count > 0
 
            oMatch = Regex.Match(Expression, Pattern)
            Dim Operand1 = oMatch.Groups(1).Value
            Dim [Operator] = oMatch.Groups(3).Value
            Dim Operand2 = oMatch.Groups(4).Value
 
            Dim Result As Double = 0
            Select Case [Operator].ToLower
                Case "+" : Result = CDbl(Operand1) + CDbl(Operand2)
                Case "-" : Result = CDbl(Operand1) - CDbl(Operand2)
            End Select
 
            Expression = Expression.Replace(oMatch.Index, oMatch.Length, Result)
 
        End While
 
        'Theoretically we should be down to just a solitary number now
        If IsNumeric(Expression) Then
            Return CDbl(Expression)
        Else
            Throw New Exception("Invalid expression: " & Expression)
        End If
 
    End Function

[balabaster]

Okay, with a little bit of exception handling to make sure that the expression is of a valid form, the following code should reduce a calculation to it's result...

Private Function Evaluate(ByVal Expression As String) As Double
 
    Dim oMatch As Match = Nothing
    Dim Pattern As String = "\(([^\(\)]*?\))"
    While Regex.Matches(Expression, Pattern).Count > 0
        oMatch = Regex.Match(Expression, Pattern)
        Expression = Expression.Replace(oMatch.Index, _
                                        oMatch.Length, _
                                        Evaluate(oMatch.Groups(1).Value))
    End While
 
    Dim Exprs() As String = New String() { _
        "(\d+(\.\d+)?)\s*(\^)\s*(\d+(\.\d+)?)", _
        "(\d+(\.\d+)?)?(√)\s*(\d+(\.\d+)?)", _
        "(\d+(\.\d+)?)\s*([\\/*×])\s*(\d+(\.\d+)?)", _
        "(\d+(\.\d+)?)\s*([-+])\s*(\d+(\.\d+)?)" _
    }
 
    For Each Expr As String In Exprs
        While Regex.Matches(Expression, Expr).Count > 0
 
            oMatch = Regex.Match(Expression, Expr)
            Dim Operand1 = oMatch.Groups(1).Value
            Dim [Operator] = oMatch.Groups(3).Value
            Dim Operand2 = oMatch.Groups(4).Value
 
            Dim Result As Double = 0
            Select Case [Operator].ToLower
                Case "^" : Result = Math.Pow(Operand1, Operand2)
                Case "√"
                    If Operand1 = "" Then Operand1 = 2
                    Result = Math.Pow(Operand2, (1 / CDbl(Operand1)))
                Case "/", "÷" : Result = CDbl(Operand1) / CDbl(Operand2)
                Case "\" : Result = CDbl(Operand1) \ CDbl(Operand2)
                Case "*", "×" : Result = CDbl(Operand1) * CDbl(Operand2)
                Case "+" : Result = CDbl(Operand1) + CDbl(Operand2)
                Case "-" : Result = CDbl(Operand1) - CDbl(Operand2)
            End Select
 
            Expression = Expression.Replace(oMatch.Index, _
                                            oMatch.Length, _
                                            Result)
 
        End While
    Next
 
    If IsNumeric(Expression) Then
        Return CDbl(Expression)
    Else
        Throw New Exception("Invalid expression: " & Expression)
    End If
 
End Function

You'll also need this module to extend the string datatype to replace by index and length:

Imports System.Runtime.CompilerServices
 
Module HelperExtensions
 
    <Extension()> _
    Public Function Replace(ByVal SearchString As String, _
                            ByVal StartIndex As Integer, _
                            ByVal Length As Integer, _
                            ByVal ReplaceString As String) As String
 
        SearchString = SearchString.Remove(StartIndex, Length)
        SearchString = SearchString.Insert(StartIndex, ReplaceString)
        Return SearchString
 
    End Function
 
End Module

[balabaster]

The regular expression pattern strings need to be modified to account for negative values...

(-?\d+(\.\d+)?)\s*[\\/*]\s*(-?\d+(\.\d+)?)

etc...

This will now handle negative numbers (well, if you're on a division or multiplication check)... all of patterns need to be changed to account for negatives. Percentage could be handled too, but then it starts getting messy because you have to account for percentage of what?

i.e.
4 + 3 * 12%...

is this interpreted as 4 plus 36% of 4 or 12% of 4 + 3?

What about 4 + 3 + 12% is this (4 + 3) + ((4 + 3) x 0.12) i.e. (4 + 3) * 1.12 or is this 4 + 3 + 0.12. What if the equation is more complex - what does the % really apply to.

What if you do 12 % 4 - is this now a modulator - i.e. 12 Mod 4 = 0?

Hence, I'm not sure exactly how I want to handle percentage yet...