Replace a^b by Pow(a,b)

Question

The application uses NCalc to execute diverse calculations.

The 'natural' way to write powers using a computer is using the ^ symbol. However, NCalc already uses it as bitwise or.

I use the following function to parse calculations and convert it to the Pow(a,b) format.

    Private Function _replacePower(Str As String) As String
        Const PowerString As String = "Pow({0},{1})"

        Dim i, j As Integer
        Dim c As String
        Dim before, after, all As String

        Dim other_p As Integer 'Keep track of other opening/closing parenthesis, to avoid breaking for a nested one.

        other_p = -1
        i = 1
        While i <= Len(Str)
            c = Mid(Str, i, 1)
            If c = "^" Then
                If Mid(Str, i - 1, 1) = ")" Then
                    j = i - 1
                    Do While Mid(Str, j, 1) <> "(" Or other_p > 0
                        If Mid(Str, j, 1) = ")" Then other_p = other_p + 1
                        If Mid(Str, j, 1) = "(" Then other_p = other_p - 1
                        j = j - 1
                    Loop
                    before = Mid(Str, j, i - j)
                Else
                    j = i - 1
                    'The expression to be raised is everything between the power and + - * / , ( <- Opening parenthesis is not ok if there is no closing one, and this case is handled above.
                    Do While (Mid(Str, j, 1) <> "+" And Mid(Str, j, 1) <> "-" And Mid(Str, j, 1) <> "*" And Mid(Str, j, 1) <> "/" And Mid(Str, j, 1) <> "," And Mid(Str, j, 1) <> "(")
                        j = j - 1
                        If j = 0 Then Exit Do
                    Loop
                    before = Mid(Str, j + 1, i - j - 1)
                End If

                other_p = -1

                If Mid(Str, i + 1, 1) = "(" Or other_p > 0 Then
                    j = i + 1
                    Do While Mid(Str, j, 1) <> ")"
                        If Mid(Str, j, 1) = ")" Then other_p = other_p - 1
                        If Mid(Str, j, 1) = "(" Then other_p = other_p + 1
                        j = j + 1
                    Loop
                    after = Mid(Str, i + 1, j - i)
                Else
                    j = i + 1
                    Do While (Mid(Str, j, 1) <> "+" And Mid(Str, j, 1) <> "-" And Mid(Str, j, 1) <> "*" And Mid(Str, j, 1) <> "/" And Mid(Str, j, 1) <> "," And Mid(Str, j, 1) <> ")")
                        j = j + 1
                        If j = Len(Str) + 1 Then Exit Do
                    Loop
                    after = Mid(Str, i + 1, j - i - 1)
                End If

                all = before & "^" & after
                Str = Replace(Str, all, String.Format(PowerString, before, after))
                i = 1
            End If
            i = i + 1
        End While
        Return Str
    End Function

My issues lies with performance, as it appears that this function is the bottleneck of the entire application. How could I improve?

Answer 1

One of your biggest performance issues is, using Mid to get one character from the string. This gets the character as a string which is inefficient. It would be better to get the character as a Char, by using the index operator of the String class(Str(j)). To compare with literal characters use the character indicator(c)at the end of the string quotes("+"c).

Whenever you have code duplication try to find a way to break that code out into a separate function. A case in point is when you are checking for operators in your string a simple function:

Private Function isOperator(chr As Char) As Boolean
    Return chr = "+"c OrElse chr = "-"c OrElse chr = "*"c OrElse chr = "/"c OrElse chr = ","c OrElse chr = ")"c
End Function

simplifies and unclutters your main code.

Whenever you have chained conditionals as above, use the shortcut boolean operators(OrElse and AndAlso). This way a false result will return right away instead of reading the rest.

Don't use Len() to get the length of the string. The String class has a length property that you can use and put into a variable.

Without any concrete examples of the complexity of the formulas that you're expecting, it's difficult to critique the efficiency of your approach. I'm thinking though, that as a general rule, anytime you are doing extensive string manipulations you should definitely look at using a StringBuilder.

Simplified with these recommendations your code would look something like this:

Private Function _replacePower(Str As String) As String
    Const PowerString As String = "Pow({0},{1})"

    Dim i, j As Integer
    Dim c As Char
    Dim before, after, all As String
    Dim length As Integer = Str.Length
    Dim other_p As Integer 'Keep track of other opening/closing parenthesis, to avoid breaking for a nested one.

    other_p = -1
    i = 1
    While i <= length
        c = Str(i)
        If c = "^"c Then
            If Str(i - 1) = ")"c Then
                j = i - 1
                Do While Str(j) <> "("c Or other_p > 0
                    If Str(j) = ")"c Then other_p = other_p + 1
                    If Str(j) = "("c Then other_p = other_p - 1
                    j = j - 1
                Loop
                before = Mid(Str, j, i - j)
            Else
                j = i - 1
                'The expression to be raised is everything between the power and + - * / , ( <- Opening parenthesis is not ok if there is no closing one, and this case is handled above.
                Do While (Not isOperator(Str(j)))
                    j = j - 1
                    If j = 0 Then Exit Do
                Loop
                before = Mid(Str, j + 1, i - j - 1)
            End If

            other_p = -1

            If Str(i + 1) = "("c Or other_p > 0 Then
                j = i + 1
                Do While Str(j) <> ")"c
                    If Str(j) = ")"c Then other_p = other_p - 1
                    If Str(j) = "("c Then other_p = other_p + 1
                    j = j + 1
                Loop
                after = Mid(Str, i + 1, j - i)
            Else
                j = i + 1
                Do While (Not isOperator(Str(j)))
                    j = j + 1
                    If j = length + 1 Then Exit Do
                Loop
                after = Mid(Str, i + 1, j - i - 1)
            End If

            all = before & "^" & after
            Str = Replace(Str, all, String.Format(PowerString, before, after))
            i = 1
        End If
        i = i + 1
    End While
    Return Str
End Function

Private Function isOperator(chr As Char) As Boolean
    Return chr = "+"c OrElse chr = "-"c OrElse chr = "*"c OrElse chr = "/"c OrElse chr = ","c OrElse chr = ")"c
End Function

I took a more in depth look at your code, and realized there were quite a few more improvements that could be made.

Don't be afraid to be verbose with your variable names. If you're worried about extra typing, Intellisense will bring up suggestions as you type, allowing you to just tab over the suggestion you want, instead of typing it all out.

You seem to do a lot of checking for different types of characters. Really all you need to check for is digits and brackets.

When checking for matching brackets, it is useful to have a `Dictionary(Of, Char, Integer)'. Opens are +1, closings are -1.

The Char class has an IsDigit function that simplifies checking for those.

There is another large code duplication when you check to the left and the right of the caret to get the appropriate strings.

You didn't mention whether there is a possibility of more than one caret symbol in a string. It seems logical that this could be a possibility. My though is make the function recursive to keep checking the returned string for caret's.

Putting this all together, you might come up with something like this:

Private Function FixString(value As String) As String
    Dim caretIndex = 0
    caretIndex = value.IndexOf("^"c)
    If caretIndex <> -1 Then
        Dim sb As New StringBuilder()
        Dim leftHand = ""
        Dim rightHand = ""
        Dim leftHandIndex = 0
        Dim rightHandIndex = 0
        leftHandIndex = caretIndex - 1
        rightHandIndex = caretIndex + 1
        leftHand = getString(value, caretIndex, leftHandIndex, -1)
        rightHand = getString(value, caretIndex, rightHandIndex, 1)
        sb.AppendFormat("{0}Pow({1},{2}){3}", value.Substring(0, leftHandIndex + 1), leftHand, rightHand, value.Substring(rightHandIndex))
        Return FixString(sb.ToString)
    Else
        Return value
    End If
End Function

Private Function getString(value As String, caretIndex As Integer, ByRef offset As Integer, increment As Integer) As String
    Dim bracketTotal = 0
    Dim index = offset
    If Char.IsDigit(value(index)) Then
        While index <> value.Length AndAlso Char.IsDigit(value(index))
            index += increment
        End While
    ElseIf brackets.ContainsKey(value(index)) Then
        bracketTotal += BRACKETS(value(index))
        index += increment
        While index <> value.Length AndAlso bracketTotal <> 0
            If BRACKETS.ContainsKey(value(index)) Then
                bracketTotal += BRACKETS(value(index))
            End If
            index += increment
        End While
    End If
    offset = index
    If increment = -1 Then
        Return value.Substring(index + 1, caretIndex - index - 1)
    End If
    Return value.Substring(caretIndex + 1, index - caretIndex - 1)
End Function


Private ReadOnly BRACKETS As Dictionary(Of Char, Integer) = New Dictionary(Of Char, Integer)() From
{
     {")"c, -1},
     {"("c, 1}
}

I didn't see anything in your code, that would suggest the possibility of badly formatted strings, so I assumed that validation was being handled elsewhere.