Разбор матэматычных выразаў на C#. Такенізацыя

Навука пастаянна развіваецца, тэхналогіі імкліва ўрываюцца ў наша жыццё, з’яўляюцца новыя інструменты і магчымасці, нязменна толькі адно – пануры выраз твару твайго інтэрв’юера. І калі з чытаннем эмоцый інтэрв’юера мы разабраліся, то з чытаннем выразаў у нас усё яшчэ ёсць праблемы. Таму ў дадзеным пасце разбяром самую простую тэму ў кантэксце дадзенай задачы – разбіццё зыходнага радка на асобныя токены.

Як згадвалася ў папярэдніх пастах пра постфіксную натацыю і алгарытм сартавальнай станцыі, мы маем наступныя віды токенаў:

Знакі арыфметычных аперацый +, -, *, /;
Круглыя дужкі (, );
Рэчаісныя лікі. Для прастаты абмяжуемся толькі лікамі з дзесятковым раздзяляльнікамі і цэлымі лікамі;
У якасці раздзяляльнікаў токенаў можа выступаць толькі сімвал прабелу.

Створым цела асноўнага метаду на C#. Будзем чытаць выраз сімвал за сімвалам і адразу апрацоўваць. Для нашага выпадку гэтага дастаткова, у іншых выпадках лексічныя аналізатары могуць патрабаваць больш складаных падыходаў. Дадзеная тэма дастаткова добра разгледжана ў той самай кнізе.

public class Tokenizer
{
    public IEnumerable<IToken> Parse(string expression)
    {
        foreach (char next in expression)
        {
            FeedCharacter(next);
        }
        return GetResult();
    }
}

Спачатку рэалізуем самы просты варыянт: уваходны радок змяшчае толькі адзін лік, прабелы і аператары адсутнічаюць.

Пакуль ёсць сімвалы, дадаем сімвалы ў асобнае сховішча, на аснове якіх будзем фарміраваць выніковы лік;
Калі ў сховішчы ёсць сімвалы, то канвертуем сімвалы ў лік і дадаем у спіс выніковых токенаў.

public class Tokenizer
{
    public Tokenizer()
    {
        _valueTokenBuilder = new StringBuilder();
        _infixNotationTokens = new List<IToken>();
    }

    public IEnumerable<IToken> Parse(string expression)
    {
        foreach (char next in expression)
        {
            FeedCharacter(next);
        }
        return GetResult();
    }

    private void FeedCharacter(char next)
    {
        _valueTokenBuilder.Append(next);
    }

    private IToken CreateOperandToken(string raw)
    {
        if (double.TryParse(raw, out double result))
        {
            return new OperandToken(result);
        }

        throw new SyntaxException($"The operand {raw} has an invalid format.");
    }

    private IEnumerable<IToken> GetResult()
    {
        if (_valueTokenBuilder.Length > 0)
        {
            var token = CreateOperandToken(_valueTokenBuilder.ToString());
            _valueTokenBuilder.Clear();
            _infixNotationTokens.Add(token);
        }

        return _infixNotationTokens.ToList();
    }

    private readonly StringBuilder _valueTokenBuilder;
    private readonly List<IToken> _infixNotationTokens;
}

Ускладнім трохі задачу: дазволім выкарыстанне некалькіх лікаў, якія раздзяляюцца прабеламі. Тады разбіццё на токены можна прадставіць у наступным выглядзе:

Пакуль ёсць сімвалы, аналізуем чарговы сімвал:
- Калі сімвал з’яўляецца раздзяляльнікам (прабелам), то канвертуем захаваныя ў сховішчы сімвалы ў лік і дадаем у спіс выніковых токенаў;
- Інакш выкарыстоўваем сімвал для фарміравання ліку ў асобным сховішчы;
Калі ў сховішчы засталіся сімвалы, то канвертуем сімвалы ў лік і дадаем у спіс выніковых токенаў.

public class Tokenizer
{
    public Tokenizer()
    {
        _valueTokenBuilder = new StringBuilder();
        _infixNotationTokens = new List<IToken>();
    }

    public IEnumerable<IToken> Parse(string expression)
    {
        foreach (char next in expression)
        {
            FeedCharacter(next);
        }
        return GetResult();
    }

    private void FeedCharacter(char next)
    {
        if (IsSpacingCharacter(next))
        {
            if (_valueTokenBuilder.Length > 0)
            {
                var token = CreateOperandToken(_valueTokenBuilder.ToString());
                _valueTokenBuilder.Clear();
                _infixNotationTokens.Add(token);
            }
        }
        else
        {
            _valueTokenBuilder.Append(next);
        }
    }

    private bool IsSpacingCharacter(char c)
    {
        switch (c)
        {
            case ' ':
                return true;
            default:
                return false;
        }
    }

    private IToken CreateOperandToken(string raw)
    {
        if (double.TryParse(raw, out double result))
        {
            return new OperandToken(result);
        }

        throw new SyntaxException($"The operand {raw} has an invalid format.");
    }

    private IEnumerable<IToken> GetResult()
    {
        if (_valueTokenBuilder.Length > 0)
        {
            var token = CreateOperandToken(_valueTokenBuilder.ToString());
            _valueTokenBuilder.Clear();
            _infixNotationTokens.Add(token);
        }

        return _infixNotationTokens.ToList();
    }

    private readonly StringBuilder _valueTokenBuilder;
    private readonly List<IToken> _infixNotationTokens;
}

Дададзім цяпер падтрымку апрацоўкі аператараў. Бо ў нашай пастаноўцы задачы ўсе аператары выражаюцца роўна адным сімвалам, то пры сустрэчы сімвала аператара будзем адразу захоўваць аператар у выніковую паслядоўнасць. Пры гэтым калі ў сховішчы ўтрымліваюцца сімвалы для фарміравання ліку, то канвертуем іх у лік. Тады фінальны алгарытм будзе выглядаць наступным чынам:

Пакуль ёсць сімвалы, аналізуем чарговы сімвал:
- Калі сімвал з’яўляецца раздзяляльнікам (прабелам), то канвертуем захаваныя ў сховішчы сімвалы ў лік і дадаем у спіс выніковых токенаў;
- Калі сімвал з’яўляецца аператарам, то канвертуем захаваныя ў сховішчы сімвалы ў лік і дадаем у спіс выніковых токенаў, пасля чаго дадаем токен аператара ў выніковы спіс;
- Інакш захоўваем сімвал для фарміравання ліку ў асобным сховішчы;
Калі ў сховішчы засталіся сімвалы, то канвертуем сімвалы ў лік і дадаем у спіс выніковых токенаў.

public class Tokenizer
{
    public Tokenizer()
    {
        _valueTokenBuilder = new StringBuilder();
        _infixNotationTokens = new List<IToken>();
    }

    public IEnumerable<IToken> Parse(string expression)
    {
        foreach (char next in expression)
        {
            FeedCharacter(next);
        }
        return GetResult();
    }

    private void FeedCharacter(char next)
    {
        if (IsSpacingCharacter(next))
        {
            if (_valueTokenBuilder.Length > 0)
            {
                var token = CreateOperandToken(_valueTokenBuilder.ToString());
                _valueTokenBuilder.Clear();
                _infixNotationTokens.Add(token);
            }
        }
        else if (IsOperatorCharacter(next))
        {
            if (_valueTokenBuilder.Length > 0)
            {
                var token = CreateOperandToken(_valueTokenBuilder.ToString());
                _valueTokenBuilder.Clear();
                _infixNotationTokens.Add(token);
            }

            var operatorToken = CreateOperatorToken(next);
            _infixNotationTokens.Add(operatorToken);
        }
        else
        {
            _valueTokenBuilder.Append(next);
        }
    }

    private bool IsOperatorCharacter(char c)
    {
        switch (c)
        {
            case '(':
            case ')':
            case '+':
            case '-':
            case '*':
            case '/':
                return true;
            default:
                return false;
        }
    }

    private bool IsSpacingCharacter(char c)
    {
        switch (c)
        {
            case ' ':
                return true;
            default:
                return false;
        }
    }

    private IToken CreateOperandToken(string raw)
    {
        if (double.TryParse(raw, out double result))
        {
            return new OperandToken(result);
        }

        throw new SyntaxException($"The operand {raw} has an invalid format.");
    }

    private OperatorToken CreateOperatorToken(char c)
    {
        switch (c)
        {
            case '(': return new OperatorToken(OperatorType.OpeningBracket);
            case ')': return new OperatorToken(OperatorType.ClosingBracket);
            case '+': return new OperatorToken(OperatorType.Addition);
            case '-': return new OperatorToken(OperatorType.Subtraction);
            case '*': return new OperatorToken(OperatorType.Multiplication);
            case '/': return new OperatorToken(OperatorType.Division);
            default:
                throw new SyntaxException($"There's no a suitable operator for the char {c}");
        }
    }

    private IEnumerable<IToken> GetResult()
    {
        if (_valueTokenBuilder.Length > 0)
        {
            var token = CreateOperandToken(_valueTokenBuilder.ToString());
            _valueTokenBuilder.Clear();
            _infixNotationTokens.Add(token);
        }

        return _infixNotationTokens.ToList();
    }

    private readonly StringBuilder _valueTokenBuilder;
    private readonly List<IToken> _infixNotationTokens;
}

Як заўсёды поўную рэалізацыю можна паглядзець на GitHub праекта coding-interview, а гэтым пастом будзем завяршаць тэму разбору матэматычных выразаў. Спадзяюся, што ўсё было пазнавальна і цікава. Да сустрэчы!

Categories:Тэхнічнае сумоўе

Tags:C#Матэматычныя выразы Парсер

itdranik

IT Dranik

Разбор матэматычных выразаў на C#. Такенізацыя

Like this:

Leave a ReplyCancel reply

Share this:

Like this:

Leave a ReplyCancel reply