Оценка выражений и обход дерева с использованием полиморфизма? (аля Стив Егге)

String Tokenizer + LL (1) Parser предоставит вам дерево выражений ... способ полиморфизма может включать абстрактный арифметический класс с функцией «оценивать (a, b)», которая переопределяется для каждого из задействованных операторов (Добавление, Вычитание и т. д.), Чтобы вернуть соответствующее значение, а дерево содержит целые числа и арифметические операторы, которые могут быть оценены путем обхода дерева в почтовом (?) Порядке.

следует использовать функциональный язык imo. Деревья сложнее представлять и манипулировать ими на объектно-ориентированных языках.

Or maybe this is the real question: how can you represent (2) as a BST? That is the part that is tripping me up.

Рекурсия.

The problem, I think, is that we need to parse perentheses, and yet they are not a binary operator? Should we take (2) as a single token, that evaluates to 2?

Скобки не должны отображаться в дереве выражения, но они влияют на его форму. Например, дерево для (1 + 2) +3 отличается от 1+ (2 + 3):

    +
   / \
  +   3
 / \
1   2

против

    +
   / \
  1   +
     / \
    2   3

Скобки - это «подсказка» для синтаксического анализатора (например, per superjoe30, «рекурсивно спускаться»).

Re: Джастин

Думаю, дерево будет выглядеть примерно так:

  +
 / \
2  ( )
    |
    2

По сути, у вас будет узел "eval", который просто оценивает дерево под ним. Затем это будет оптимизировано до простого:

  +
 / \
2   2

В этом случае скобки не требуются и ничего не добавляют. Они ничего не добавляют логически, поэтому просто уйдут.

Это касается теории синтаксического анализа / компилятора, которая является своего рода кроличьей норой ... Книга Дракона - это стандартный текст для построения компилятора, который доводит его до крайностей. В этом конкретном случае вы хотите построить контекстно-свободная грамматика для базовой арифметики, а затем использовать эту грамматику для анализа абстрактное синтаксическое дерево. Затем вы можете перебирать дерево, уменьшая его снизу вверх (на этом этапе вы должны применить оператор полиморфизма / указателей на функции / переключателя, чтобы уменьшить дерево).

Я обнаружил, что эти заметки невероятно полезен в теории компилятора и синтаксического анализа.

Прогулка по полиморфному дереву, версия Python

#!/usr/bin/python

class Node:
    """base class, you should not process one of these"""
    def process(self):
        raise('you should not be processing a node')

class BinaryNode(Node):
    """base class for binary nodes"""
    def __init__(self, _left, _right):
        self.left = _left
        self.right = _right
    def process(self):
        raise('you should not be processing a binarynode')

class Plus(BinaryNode):
    def process(self):
        return self.left.process() + self.right.process()

class Minus(BinaryNode):
    def process(self):
        return self.left.process() - self.right.process()

class Mul(BinaryNode):
    def process(self):
        return self.left.process() * self.right.process()

class Div(BinaryNode):
    def process(self):
        return self.left.process() / self.right.process()

class Num(Node):
    def __init__(self, _value):
        self.value = _value
    def process(self):
        return self.value

def demo(n):
    print n.process()

demo(Num(2))                                       # 2
demo(Plus(Num(2),Num(5)))                          # 2 + 3
demo(Plus(Mul(Num(2),Num(3)),Div(Num(10),Num(5)))) # (2 * 3) + (10 / 2)

Тесты просто строят бинарные деревья с помощью конструкторов.

структура программы:

абстрактный базовый класс: Node

• все узлы наследуются от этого класса

абстрактный базовый класс: BinaryNode

• все бинарные операторы наследуются от этого класса
• Метод процесса выполняет работу по вычислению выражения и возврату результата

классы бинарных операторов: Plus, Minus, Mul, Div

• два дочерних узла, по одному для левых и правых подвыражений

числовой класс: Num

• содержит числовое значение конечного узла, например 17 или 42

@ Джастин:

Взгляните на мою заметку о представлении узлов. Если вы воспользуетесь этой схемой, то

2 + (2)

можно представить как

           .
          / \
         2  ( )
             |
             2

Представление узлов

Если мы хотим включить круглые скобки, нам нужно 5 видов узлов:

• бинарные узлы: добавьте Minus Mul Div
  , у них есть два дочерних узла, левый и правый

       +
      / \
  node   node
  

• узел для хранения значения: Val
  без дочерних узлов, только числовое значение

• узел для отслеживания паренсов: Paren
  - единственный дочерний узел для подвыражения.

      ( )
       |
      node
  

Для полиморфного решения нам нужны отношения классов:

• Узел
• BinaryNode: наследовать от узла
• Плюс: наследование от двоичного узла
• Минус: унаследовать от Binary Node
• Mul: наследовать от двоичного узла
• Div: наследовать от двоичного узла
• Значение: наследовать от узла
• Парен: наследовать от узла

Для всех узлов существует виртуальная функция eval (). Если вы вызовете эту функцию, она вернет значение этого подвыражения.

I won't give away the answer, but a Standard Bad Solution involves the use of a switch or case statment (or just good old-fashioned cascaded-ifs). A Slightly Better Solution involves using a table of function pointers, and the Probably Best Solution involves using polymorphism.

Последние двадцать лет эволюции интерпретаторов можно рассматривать как противоположный путь - полиморфизм (например, наивные метациркулярные интерпретаторы Smalltalk) для указателей функций (наивные реализации Lisp, многопоточный код, C++) для переключения (наивные интерпретаторы байтового кода), а затем и далее в JIT и т. д. - которые либо требуют очень больших классов, либо (в однополиморфных языках) двойной диспетчеризации, которая сокращает полиморфизм до типового случая, и вы снова на первом этапе. Какое определение «лучший» здесь используется?

Для простых вещей подойдет полиморфное решение - вот тот, который я сделал ранее, но либо стек и байт-код / ​​переключатель, либо использование компилятора среды выполнения обычно лучше, если вы, скажем, строите функцию с несколькими тысячами точек данных.

Думаю, вопрос в том, как написать парсер, а не оценщик. Вернее, как создать дерево выражения из строки.

Операторы case, возвращающие базовый класс, точно не учитываются.

Базовая структура «полиморфного» решения (это еще один способ сказать, мне все равно, с чем вы это строите, я просто хочу расширить ее, переписав минимально возможное количество кода) десериализация иерархии объектов из поток с (динамическим) набором известных типов.

Суть реализации полиморфного решения состоит в том, чтобы иметь способ создать объект выражения из сопоставителя шаблонов, вероятно, рекурсивного. То есть сопоставьте BNF или аналогичный синтаксис с фабрикой объектов.

Как уже упоминалось ранее, при использовании деревьев выражений скобки не нужны. Когда вы смотрите на дерево выражений, порядок операций становится тривиальным и очевидным. Парсеры являются подсказками для парсера.

В то время как принятый ответ - это решение одной половины проблемы, другая половина - фактический анализ выражения - все еще не решена. Как правило, такого рода проблемы можно решить с помощью парсер рекурсивного спуска. Написание такого парсера часто бывает забавным упражнением, но большинство современные инструменты для синтаксического анализа языка отвлечет вас от этого.

Синтаксический анализатор также будет сложнее существенно, если вы разрешите числа с плавающей запятой в своей строке. Мне пришлось создать DFA для приема чисел с плавающей запятой на C - это была очень кропотливая и детальная задача. Помните, что допустимые числа с плавающей запятой включают: 10, 10., 10.123, 9.876e-5, 1.0f, .025 и т. д. Я предполагаю, что в интервью было сделано некоторое отступление от этого (в пользу простоты и краткости).

Хм ... Я не думаю, что для этого можно написать нисходящий синтаксический анализатор без возврата, так что это должен быть своего рода синтаксический анализатор сдвига-уменьшения. LR (1) или даже LALR, конечно же, будут отлично работать со следующим (ad-hoc) определением языка:

Пуск -> E1
E1 -> E1 + E1 | E1-E1
E1 -> E2 * E2 | E2 / E2 | E2
E2 -> номер | (E1)

Разделение на E1 и E2 необходимо для сохранения приоритета * и / над + и -.

Но вот как я бы это сделал, если бы пришлось писать парсер вручную:

• Два стека, один хранит узлы дерева как операнды, а другой хранит операторы.
• Прочтите ввод слева направо, сделайте из чисел листовые узлы и вставьте их в стек операндов.
• Если у вас> = 2 операндов в стеке, вытяните 2, объедините их с самым верхним оператором в стеке операторов и верните эту структуру обратно в дерево операндов, пока не
• Следующий оператор имеет более высокий приоритет, чем тот, который в данный момент находится на вершине стека.

Это оставляет нам проблему работы со скобками. Одно изящное (как мне казалось) решение - сохранить приоритет каждого оператора в виде числа в переменной. Итак, изначально

• int плюс, минус = 1;
• int mul, div = 2;

Теперь каждый раз, когда вы видите левую скобку, увеличивайте все эти переменные на 2, и каждый раз, когда вы видите правую скобку, уменьшайте все переменные на 2.

Это гарантирует, что + в 3 * (4 + 5) будет иметь более высокий приоритет, чем *, и 3 * 4 не будет помещен в стек. Вместо этого он будет ждать 5, нажимать 4 + 5, затем нажимать 3 * (4 + 5).

Я написал такой парсер с помощью некоторых основных приемов, таких как Инфикс -> РПН и Маневровая площадка и Обходы по дереву. Вот реализация, которую я придумал.
Он написан на C++ и компилируется как в Linux, так и в Windows. Любые предложения / вопросы приветствуются.

So, let's try to tackle the problem all three ways. How do you go from an arithmetic expression (e.g. in a string) such as "2 + (2)" to an expression tree using cascaded-if's, a table of function pointers, and/or polymorphism?

Это интересно, но я не думаю, что это относится к области объектно-ориентированного программирования ... Я думаю, что это больше связано с методы синтаксического анализа.

Я как бы собрал это консольное приложение на C# в качестве доказательства концепции. Есть ощущение, что это могло бы быть намного лучше (этот оператор switch в GetNode неуклюжий (это там, потому что я ударил пробел, пытаясь сопоставить имя класса с оператором)). Любые предложения о том, как это можно улучшить, приветствуются.

using System;

class Program
{
    static void Main(string[] args)
    {
        string expression = "(((3.5 * 4.5) / (1 + 2)) + 5)";
        Console.WriteLine(string.Format("{0} = {1}", expression, new Expression.ExpressionTree(expression).Value));
        Console.WriteLine("\nShow's over folks, press a key to exit");
        Console.ReadKey(false);
    }
}

namespace Expression
{
    // -------------------------------------------------------

    abstract class NodeBase
    {
        public abstract double Value { get; }
    }

    // -------------------------------------------------------

    class ValueNode : NodeBase
    {
        public ValueNode(double value)
        {
            _double = value;
        }

        private double _double;
        public override double Value
        {
            get
            {
                return _double;
            }
        }
    }

    // -------------------------------------------------------

    abstract class ExpressionNodeBase : NodeBase
    {
        protected NodeBase GetNode(string expression)
        {
            // Remove parenthesis
            expression = RemoveParenthesis(expression);

            // Is expression just a number?
            double value = 0;
            if (double.TryParse(expression, out value))
            {
                return new ValueNode(value);
            }
            else
            {
                int pos = ParseExpression(expression);
                if (pos > 0)
                {
                    string leftExpression = expression.Substring(0, pos - 1).Trim();
                    string rightExpression = expression.Substring(pos).Trim();

                    switch (expression.Substring(pos - 1, 1))
                    {
                        case "+":
                            return new Add(leftExpression, rightExpression);
                        case "-":
                            return new Subtract(leftExpression, rightExpression);
                        case "*":
                            return new Multiply(leftExpression, rightExpression);
                        case "/":
                            return new Divide(leftExpression, rightExpression);
                        default:
                            throw new Exception("Unknown operator");
                    }
                }
                else
                {
                    throw new Exception("Unable to parse expression");
                }
            }
        }

        private string RemoveParenthesis(string expression)
        {
            if (expression.Contains("("))
            {
                expression = expression.Trim();

                int level = 0;
                int pos = 0;

                foreach (char token in expression.ToCharArray())
                {
                    pos++;
                    switch (token)
                    {
                        case '(':
                            level++;
                            break;
                        case ')':
                            level--;
                            break;
                    }

                    if (level == 0)
                    {
                        break;
                    }
                }

                if (level == 0 && pos == expression.Length)
                {
                    expression = expression.Substring(1, expression.Length - 2);
                    expression = RemoveParenthesis(expression);
                }
            }
            return expression;
        }

        private int ParseExpression(string expression)
        {
            int winningLevel = 0;
            byte winningTokenWeight = 0;
            int winningPos = 0;

            int level = 0;
            int pos = 0;

            foreach (char token in expression.ToCharArray())
            {
                pos++;

                switch (token)
                {
                    case '(':
                        level++;
                        break;
                    case ')':
                        level--;
                        break;
                }

                if (level <= winningLevel)
                {
                    if (OperatorWeight(token) > winningTokenWeight)
                    {
                        winningLevel = level;
                        winningTokenWeight = OperatorWeight(token);
                        winningPos = pos;
                    }
                }
            }
            return winningPos;
        }

        private byte OperatorWeight(char value)
        {
            switch (value)
            {
                case '+':
                case '-':
                    return 3;
                case '*':
                    return 2;
                case '/':
                    return 1;
                default:
                    return 0;
            }
        }
    }

    // -------------------------------------------------------

    class ExpressionTree : ExpressionNodeBase
    {
        protected NodeBase _rootNode;

        public ExpressionTree(string expression)
        {
            _rootNode = GetNode(expression);
        }

        public override double Value
        {
            get
            {
                return _rootNode.Value;
            }
        }
    }

    // -------------------------------------------------------

    abstract class OperatorNodeBase : ExpressionNodeBase
    {
        protected NodeBase _leftNode;
        protected NodeBase _rightNode;

        public OperatorNodeBase(string leftExpression, string rightExpression)
        {
            _leftNode = GetNode(leftExpression);
            _rightNode = GetNode(rightExpression);

        }
    }

    // -------------------------------------------------------

    class Add : OperatorNodeBase
    {
        public Add(string leftExpression, string rightExpression)
            : base(leftExpression, rightExpression)
        {
        }

        public override double Value
        {
            get
            {
                return _leftNode.Value + _rightNode.Value;
            }
        }
    }

    // -------------------------------------------------------

    class Subtract : OperatorNodeBase
    {
        public Subtract(string leftExpression, string rightExpression)
            : base(leftExpression, rightExpression)
        {
        }

        public override double Value
        {
            get
            {
                return _leftNode.Value - _rightNode.Value;
            }
        }
    }

    // -------------------------------------------------------

    class Divide : OperatorNodeBase
    {
        public Divide(string leftExpression, string rightExpression)
            : base(leftExpression, rightExpression)
        {
        }

        public override double Value
        {
            get
            {
                return _leftNode.Value / _rightNode.Value;
            }
        }
    }

    // -------------------------------------------------------

    class Multiply : OperatorNodeBase
    {
        public Multiply(string leftExpression, string rightExpression)
            : base(leftExpression, rightExpression)
        {
        }

        public override double Value
        {
            get
            {
                return _leftNode.Value * _rightNode.Value;
            }
        }
    }
}

Хорошо, вот моя наивная реализация. Извините, я не подумал использовать для этого объекты, но их легко преобразовать. Я чувствую себя немного злым Вилли (из рассказа Стива).

#!/usr/bin/env python

#tree structure [left argument, operator, right argument, priority level]
tree_root = [None, None, None, None]
#count of parethesis nesting
parenthesis_level = 0
#current node with empty right argument
current_node = tree_root

#indices in tree_root nodes Left, Operator, Right, PRiority
L, O, R, PR = 0, 1, 2, 3

#functions that realise operators
def sum(a, b):
    return a + b

def diff(a, b):
    return a - b

def mul(a, b):
    return a * b

def div(a, b):
    return a / b

#tree evaluator
def process_node(n):
    try:
        len(n)
    except TypeError:
        return n
    left = process_node(n[L])
    right = process_node(n[R])
    return n[O](left, right)

#mapping operators to relevant functions
o2f = {'+': sum, '-': diff, '*': mul, '/': div, '(': None, ')': None}

#converts token to a node in tree
def convert_token(t):
    global current_node, tree_root, parenthesis_level
    if t == '(':
        parenthesis_level += 2
        return
    if t == ')':
        parenthesis_level -= 2
        return
    try: #assumption that we have just an integer
        l = int(t)
    except (ValueError, TypeError):
        pass #if not, no problem
    else:
        if tree_root[L] is None: #if it is first number, put it on the left of root node
            tree_root[L] = l
        else: #put on the right of current_node
            current_node[R] = l
        return

    priority = (1 if t in '+-' else 2) + parenthesis_level

    #if tree_root does not have operator put it there
    if tree_root[O] is None and t in o2f:
            tree_root[O] = o2f[t]
            tree_root[PR] = priority
            return

    #if new node has less or equals priority, put it on the top of tree
    if tree_root[PR] >= priority:
        temp = [tree_root, o2f[t], None, priority]
        tree_root = current_node = temp
        return

    #starting from root search for a place with higher priority in hierarchy
    current_node = tree_root
    while type(current_node[R]) != type(1) and priority > current_node[R][PR]:
        current_node = current_node[R]
    #insert new node
    temp = [current_node[R], o2f[t], None, priority]
    current_node[R] = temp
    current_node = temp



def parse(e):
    token = ''
    for c in e:
        if c <= '9' and c >='0':
            token += c
            continue
        if c == ' ':
            if token != '':
                convert_token(token)
                token = ''
            continue
        if c in o2f:
            if token != '':
                convert_token(token)
            convert_token(c)
            token = ''
            continue
        print "Unrecognized character:", c
    if token != '':
        convert_token(token)


def main():
    parse('(((3 * 4) / (1 + 2)) + 5)')
    print tree_root
    print process_node(tree_root)

if __name__ == '__main__':
    main()