Math expression parser in C#

Question

EDIT: Added refactored version 2.0 to the end!

I have a parser that is supposed to take a string similar to a math expression and return a Tuple of:

• An array of strings where each string corresponds to one 'element' (number, operator, func name).
• An array of custom enum indicating whether corresponding string in array is Name, Number, etc.

I have honestly no idea how Buffer like readers are usually implemented so I'm open to suggestions on how to make my class a little less messy (I particularly don't like the fact I'm using bufferPointer in five different functions. The way I'm testing it I'm not out of my array in two places also doesn't seem to me as a good practice (though I couldn't find any good solution)).

using System;
using System.Collections.Generic;
using System.Text;

namespace MathExpressionSolver.Parser
{
    class ExpressionParser
    {
        const int TKNLGHT = 4;
        public bool SkipInvalidChars { get; set; } = true;

        private StringBuilder charBuffer;
        private int bufferPointer = 0;

        private List<string> listOfParsedExpressions;
        private List<ParsedSubstringType> listOfParsedTypes;
        private string stringExpression;

        public string StringExpression
        {
            set
            {
                listOfParsedExpressions.Clear();
                listOfParsedExpressions.Capacity = stringExpression.Length / TKNLGHT;

                listOfParsedTypes.Clear();
                listOfParsedTypes.Capacity = stringExpression.Length / TKNLGHT;

                stringExpression = value;
            }
        }

        public ExpressionParser() 
        {
            charBuffer = new StringBuilder(TKNLGHT);

            listOfParsedExpressions = new List<string>();
            listOfParsedTypes = new List<ParsedSubstringType>();

            stringExpression = string.Empty;
        }

        public ExpressionParser(string expression) : this()
        {
            StringExpression = expression;
        }

        public Tuple<string[], ParsedSubstringType[]> ParseExpression()
        {
            parseExpression();
            return new Tuple<string[], ParsedSubstringType[]>(listOfParsedExpressions.ToArray(), listOfParsedTypes.ToArray());
        }

        private void parseExpression()
        {
            listOfParsedExpressions.Clear();
            listOfParsedTypes.Clear();

            while (bufferPointer < stringExpression.Length)
            {
                parseNextToken();
            }
        }

        private void parseNextToken()
        {
            charBuffer.Clear();
            Func<char, bool> isTypeFunction = null;
            ParsedSubstringType currentType;

            bool isLong = false;
            bool trash = false;

            if (ParserHelper.IsNameChar(stringExpression[bufferPointer]))
            {
                addCurrCharToBuffer();
                isTypeFunction = ParserHelper.IsNameChar;
                currentType = ParsedSubstringType.Name;
                isLong = true;
            }
            else if (ParserHelper.IsNum(stringExpression[bufferPointer]))
            {
                addCurrCharToBuffer();
                isTypeFunction = ParserHelper.IsNum;
                currentType = ParsedSubstringType.Num;
                isLong = true;
            }
            else if (ParserHelper.IsWhiteSpace(stringExpression[bufferPointer]))
            {
                trashCurrChar();
                isTypeFunction = ParserHelper.IsWhiteSpace;
                currentType = ParsedSubstringType.WhiteSpace;
                isLong = true;
                trash = true;
            }
            else if (ParserHelper.IsLeftBracket(stringExpression[bufferPointer]))
            {
                addCurrCharToBuffer();
                currentType = ParsedSubstringType.Bracket;
            }
            else if (ParserHelper.IsRightBracket(stringExpression[bufferPointer]))
            {
                addCurrCharToBuffer();
                currentType = ParsedSubstringType.Bracket;
            }
            else if (ParserHelper.IsOperator(stringExpression[bufferPointer]))
            {
                addCurrCharToBuffer();
                currentType = ParsedSubstringType.Operator;
            }
            else if (ParserHelper.IsSeparator(stringExpression[bufferPointer]))
            {
                addCurrCharToBuffer();
                currentType = ParsedSubstringType.Separator;
            }
            else
            {
                trashCurrChar();
                if (SkipInvalidChars) return;
                else currentType = ParsedSubstringType.WhiteSpace;
            }

            if(isLong)
            {
                while(bufferPointer < stringExpression.Length && isTypeFunction(stringExpression[bufferPointer]))
                {
                    if (trash) trashCurrChar();
                    else addCurrCharToBuffer();
                }
            }

            listOfParsedExpressions.Add(charBuffer.ToString());
            listOfParsedTypes.Add(currentType);
        }

        private void addCurrCharToBuffer()
        {
            charBuffer.Append(stringExpression[bufferPointer]);
            bufferPointer++;
        }

        private void trashCurrChar()
        {
            bufferPointer++;
        }
    }

    public enum ParsedSubstringType { Name, Num, Bracket, Operator, Separator, WhiteSpace };

    public static class ParserHelper
    {
        public static bool IsNameChar(char a)
        {
            if(a == '_') return true;
            else return char.IsLetter(a);
        }

        public static bool IsNum(char a)
        {
            if (a == '.') return true;
            else return char.IsDigit(a);
        }

        public static bool IsLeftBracket(char a)
        {
            return (a == '(') ? true : false;
        }

        public static bool IsRightBracket(char a)
        {
            return (a == ')') ? true : false;
        }

        public static bool IsOperator (char a)
        {
            switch (a)
            {
                case '+':
                    return true;
                case '-':
                    return true;
                case '*':
                    return true;
                case '/':
                    return true;
                case '%':
                    return true;
                case '=':
                    return true;
                default:
                    return false;
            }
        }

        public static bool IsSeparator(char a)
        {
            return (a == ';') ? true : false; 
        }

        public static bool IsWhiteSpace(char a)
        {
            return (char.IsWhiteSpace(a)) ? true : false;
        }
    }
}

INPUT/OUTPUT testing:

INPUT: 2 & 3*(7- 3+2+-2 / 2(()*(2)
OUTPUT string[]: {2,,,3,*,(,7,-,,3,+,3,+,-,2,,/,,2,(,(,),*,(,2,)}
OUTPUT types[]: {Num, WhiteSpace, WhiteSpace, Num, Operator, Bracket, Num, Operator, ... }

Refactored version:

NOTES:

• I've kept camelCase naming for private methods names. The official naming convention talks only about public methods and camelCase really helps me with readability.
• I've separated parseNewExpression to it's own method as it seemed to me that there was too much code repetition.
• ParseExpression() is still without parameters because one should be able to Reparse previously added expression without the need to set it again (e.g. after SkipInvalidTokens settings change).

• Significantly reduced ParseExpression methods (there was quite a lot of overlapping cuntionality). Now it's slower but waaay nicer (and who cares about speed anyway...)

  public void ParseExpression()
  {
      ParsedSubstringType lastType = ParsedSubstringType.NotSet;
  
      parsedExpression.Clear();
      parsedTypes.Clear();
  
      StringBuilder charBuffer = new StringBuilder(avgTokenLength);
      foreach (char token in rawExpression)
      {
          ParsedSubstringType currentType = getTokenType(token);
          if(IsCoumpnoundable(lastType) && currentType != lastType)
          {
              parseNewExpression(charBuffer, lastType);
          }
  
          lastType = currentType;
          if (IsCoumpnoundable(currentType))
          {
              charBuffer.Append(token);
              continue;
          }
  
          if (currentType == ParsedSubstringType.Invalid && SkipInvalidChars) { continue; }
          charBuffer.Append(token);
  
          parseNewExpression(charBuffer, currentType);
      }
  
      if (charBuffer.Length > 0)
      {
          parseNewExpression(charBuffer, lastType);
      }
  }
  private void parseNewExpression(StringBuilder charBuffer, ParsedSubstringType currentType)
  {
      string expression = (isTrashable(currentType)) ? string.Empty : charBuffer.ToString();
  
      parsedTypes.Add(currentType);
      parsedExpression.Add(expression);
      charBuffer.Clear();
  }
  
  private bool IsCoumpnoundable(ParsedSubstringType type)
  {
      return (
              type == ParsedSubstringType.Num ||
              type == ParsedSubstringType.Name ||
              type == ParsedSubstringType.WhiteSpace
           );
  }
  
  private bool isTrashable(ParsedSubstringType type)
  {
      return (type == ParsedSubstringType.WhiteSpace);
  }
  

Answer 1

Naming and Style

• Based on the naming guidlines method names should be using PascalCase casing.
• you should not prefix the variablenames with the datatype -> listOfParsedExpressions
• variable names should be meaningful so you or Mr.Maintainer will understand them in 6 months also -> const int TKNLGHT = 4;
• you should use braces {} for single if statements also. This will make your code less errorprone.

Ternary expressions

You shouldn't use them like you do.

public static bool IsSeparator(char a)
{
    return (a == ';') ? true : false; 
}  

can be expressed as

public static bool IsSeparator(char a)
{
    if (a == ';') 
    { 
        return true;
    }
    else
    { 
        return false;
    }
}  

which in turn is just

public static bool IsSeparator(char a)
{
    return (a == ';');
} 

which is more readable.

Simplification

public static bool IsOperator (char a)
{
    switch (a)
    {
        case '+':
            return true;
        case '-':
            return true;
        case '*':
            return true;
        case '/':
            return true;
        case '%':
            return true;
        case '=':
            return true;
        default:
            return false;
    }
}  

can be reduced to

public static bool IsOperator(char a)
{
    return "+-*/=".Contains(a);
}

ExpressionParser

• Instead of incrementing the bufferPointer variable in multiple places, you should consider to either di it at one place (one method) only or change the parseNextToken() method to take a char as input parameter, where I prefer the later.

• Instead of returning a Tuple you should add 2 properties where the lists can be accessed.

• in the currents state there is no advantage of having a IsLeftBracket and a IsRightBracket check in the parseNextToken() method.

• you should add a ParsedSubstringType.InvalidToken for the result beeing more clear

Refactoring

I am not 100% happy with this, but it is a start

First we need a method to get the ParsedSubstringType of a given char

private ParsedSubstringType GetTokenType(char c)
{
    if (ParserHelper.IsNameChar(c))
    {
        return ParsedSubstringType.Name;
    }
    if (ParserHelper.IsNum(c))
    {
        return ParsedSubstringType.Num;
    }
    if (ParserHelper.IsWhiteSpace(c))
    {
        return ParsedSubstringType.WhiteSpace;
    }
    if (ParserHelper.IsLeftBracket(c) || ParserHelper.IsRightBracket(c))
    {
        return ParsedSubstringType.Bracket;
    }
    if (ParserHelper.IsOperator(c))
    {
        return ParsedSubstringType.Operator;
    }
    if (ParserHelper.IsSeparator(c))
    {
        return ParsedSubstringType.Separator;
    }
    return ParsedSubstringType.Invalid;
}

as you can see, I have already added Invalid to the enum.

Next we add a method to check if it is a possible compound expression (a name or num)

private bool IsPossibleCompoundExpression(ParsedSubstringType currentType)
{
    return (  
              currentType == ParsedSubstringType.Name ||  
              currentType == ParsedSubstringType.Num  
           );
}  

but, keeping in mind there could be the possibility (because the input is faulted), that a number would be followed by a name or opposite, we need to check if the lasttype is the same as the current.

I have added another value to the enum: NotSet indicating especial the same

The StringBuilder charBuffer is now local to the method.

and the former parseExpression() method where I added an input parameter

private void ParseExpression(String expression)
{
    StringBuilder charBuffer = new StringBuilder(expression.Length);

    listOfParsedExpressions.Clear();
    listOfParsedTypes.Clear();

    Boolean lastExpressionWasCompound = false;
    ParsedSubstringType lastType = ParsedSubstringType.Invalid;

    foreach (Char token in expression)
    {
        ParsedSubstringType currentType = GetTokenType(token);

        if (IsPossibleCompoundExpression(currentType, lastType))
        {
            if (lastType == ParsedSubstringType.NotSet || currentType != lastType)
            {
                listOfParsedExpressions.Add(charBuffer.ToString());
                listOfParsedTypes.Add(lastType);
                charBuffer.Clear();
            }

            charBuffer.Append(token);
            lastExpressionWasCompound = true;
            lastType = currentType;
            continue;
        }

        if (lastExpressionWasCompound)
        {
            listOfParsedExpressions.Add(charBuffer.ToString());
            listOfParsedTypes.Add(lastType);
            charBuffer.Clear();
            lastExpressionWasCompound = false;
        }

        if (currentType == ParsedSubstringType.Invalid && SkipInvalidChars)
        {
            continue;
        }

        listOfParsedTypes.Add(currentType);

        String parsedExpression = currentType == ParsedSubstringType.WhiteSpace ? String.Empty : token.ToString();

        listOfParsedExpressions.Add(parsedExpression);

    }

    if (charBuffer.Length > 0)
    {
        listOfParsedExpressions.Add(charBuffer.ToString());
        listOfParsedTypes.Add(lastType);
    }
}

ParserHelper

Setting aside what already been said about the tenary method.

• the decimal separator differs from country to country. Using of the CultureInfo is recommended.

• redunant else to be removed. If the condition is true, the else part is never reached and can therfor be removed.

  if(condition) return true;
  else return (true or false);
  

These and the above implemented the class looks like

public static class ParserHelper
{
    public static bool IsNameChar(char a)
    {
        return a == '_' || char.IsLetter(a);
    }
    private static char decimalSeparator = CultureInfo.CurrentCulture.NumberFormat.NumberDecimalSeparator[0];
    public static bool IsNum(char a)
    {
        return  (a == decimalSeparator) || char.IsDigit(a);
    }

    public static bool IsLeftBracket(char a)
    {
        return (a == '(');
    }

    public static bool IsRightBracket(char a)
    {
        return (a == ')');
    }

    public static bool IsOperator(char a)
    {
        return "+-*/%=".Contains(a);
    }

    public static bool IsSeparator(char a)
    {
        return (a == ';');
    }

    public static bool IsWhiteSpace(char a)
    {
        return char.IsWhiteSpace(a);
    }
}

You could also turn this into extension methods.

Answer 2

Lexicon

I'm a fan of using common terminology for best practices. You are creating a lexer rather than a parser.

• Parser: Within computational linguistics the term is used to refer to the formal analysis by a computer of a sentence or other string of words into its constituents, resulting in a parse tree showing their syntactic relation to each other, which may also contain semantic and other information.
• Lexer/Tokenizer: In computer science, lexical analysis, lexing or tokenization is the process of converting a sequence of characters (such as in a computer program or web page) into a sequence of tokens (strings with an assigned and thus identified meaning)