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

Обход полиморфного дерева, версия 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)

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

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

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

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

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

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

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

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

класс чисел: Num

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

Проблема, я думаю, в том, что нам нужно разобрать скобки, а они не являются бинарным оператором? Должны ли мы принять (2) как один токен, который оценивается как 2?

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

    +
   / \
  +   3
 / \
1   2

против

    +
   / \
  1   +
     / \
    2   3

Круглые скобки являются «подсказкой» парсеру (например, per superjoe30, «рекурсивно спуститься»)

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

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

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

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

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

       +
      / \
  node   node
  

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

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

      ( )
       |
      node
  

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

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

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

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

Я не буду раскрывать ответ, но стандартное плохое решение предполагает использование оператора switch или case (или просто старых добрых каскадных if). Несколько лучшее решение предполагает использование таблицы указателей на функции, а вероятно лучшее решение предполагает использование полиморфизма.

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

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

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

Пуск -> E1
E1 -> E1+E1 | E1-E1
E1 -> E2*E2 | Е2/Е2 | E2
E2 -> число | (Е1)

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

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

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

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

• инт плюс, минус = 1;
• инт мул, дел = 2;

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

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

Re: Джастин

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

  +
 / \
2  ( )
    |
    2

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

  +
 / \
2   2

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

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

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

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

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

Или, может быть, это настоящий вопрос: как вы можете представить (2) как BST? Это та часть, которая сбивает меня с толку.

Рекурсия.

@Джастин:

Посмотрите на мою заметку о представлении узлов. Если использовать эту схему, то

2 + (2)

может быть представлен как

           .
          / \
         2  ( )
             |
             2

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

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

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

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

Я написал такой синтаксический анализатор с некоторыми базовыми методами, такими как Infix -> RPN и Маневровая станция и Обход дерева. Вот реализация, которую я придумал.
Это написан на C++ и компилируется как в Linux, так и в Windows.
Приветствуются любые предложения/вопросы.

Итак, давайте попробуем решить проблему всеми тремя способами. Как перейти от арифметического выражения (например, в строке), такого как «2 + (2)», к дереву выражений, используя каскадные операторы if, таблицу указателей на функции и/или полиморфизм?

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

Я как бы бросил это консольное приложение С# в качестве доказательства концепции. Есть ощущение, что это могло бы быть намного лучше (этот оператор 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()