Как посчитать значения из AST-дерева?

Question

[Worgen]

Добрый день, необходимо сделать калькулятор который бы считал выражения следующих типов:
(2+5*(2+1))*2, 8*(2+1/(2+5)) и так далее.
Необходимо реализовать с помощью AST-дерево.
Я уже сделал парсер для этого, выводит он следующее:

Все это храниться у меня в списке в моем созданном классе:

class Node
    {
        public string type;
        public string value;

        public Node() { }
        public Node(string t, string v) { type = t; value = v; }
    }

//список который выводит после парсинга
List<Node> parse = new List<Node>();

Подскажите, пожалуйста, как мне щас посчитать все это? Не совсем понимаю как это реализовать.

Comments

[Lynn «Кофеман»]

Это у вас не AST, а пока только набор токенов.

Вообще примеров как разобрать арифметическое выражение в AST в сети куча на любом языке

Answer 1

[Денис Загаевский]

Как уже сказано, это не AST, а список токенов(надо сказать, неудобных токенов). Разобрать это в AST можно простейшим алгоритмом рекурсивного спуска, например. Затем вычислить.

Answer 2

[Руслан .]

Посмотрите вот эту статью:
https://habr.com/ru/post/281495/

Там в комментариях много интересных ссылок, например эта:
journal.stuffwithstuff.com/2011/03/19/pratt-parser...