9
\$\begingroup\$

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);
    }
    
\$\endgroup\$
  • 1
    \$\begingroup\$ TKNLGHT? I keep interpreting it as Token Light rather than what you probably intended as Token Length, which in that case would be TKNLGTH... which is irrelevant because it should be TokenLength, or if you insist on all caps, TOKEN_LENGTH. \$\endgroup\$ – helrich Dec 11 '14 at 15:07
  • \$\begingroup\$ What you may and may not do after receiving answers \$\endgroup\$ – Mathieu Guindon Dec 15 '14 at 1:47
11
\$\begingroup\$

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.

Tenary 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.

\$\endgroup\$
  • \$\begingroup\$ Isn't your implementation of IsOperator significantly slower? Also, could you give me your opinion about the general class structure (E.g. using bufferPointer as whole-class variable, ...)? And lastly, shouldn't PascalCase be used only for public function (and Camel for private)? \$\endgroup\$ – Petrroll Dec 11 '14 at 9:01
  • \$\begingroup\$ significantly slower is true, but what the ... using a String containing 100.000 chars will be done in 10 ms. It is for sure easier to read. \$\endgroup\$ – Heslacher Dec 11 '14 at 9:18
  • \$\begingroup\$ @Petrroll Methods always have PascalCasing. Only private members (not methods) or parameters use camelCase. \$\endgroup\$ – Abbas Dec 11 '14 at 9:44
  • \$\begingroup\$ Good points, the question is how to implement 'names and nums' (longer elements) parsing when parseNextToken takes only char as an input. Could you explain that a bit further? \$\endgroup\$ – Petrroll Dec 11 '14 at 10:22
  • \$\begingroup\$ Ok, that is kind of awesome. Truly nicely readable code. The only 'issue' I see with it is that you have to test for numbers and names when appending whitespace (and for numbers when names)... On the other hand, the performance loss is probably insignificant in comparison to the readability gain. \$\endgroup\$ – Petrroll Dec 11 '14 at 13:20
1
\$\begingroup\$

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)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.