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

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

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

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

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

Рекурсия.

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

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

    +
   / \
  +   3
 / \
1   2

против

    +
   / \
  1   +
     / \
    2   3

Скобки являются «подсказкой» для синтаксического анализатора (например, для суперджо30, «рекурсивно спускаться»)

Re: Джастин

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

  +
 / \
2  ( )
    |
    2

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

  +
 / \
2   2

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

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

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

@Justin:

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

2 + (2)

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

           .
          / \
         2  ( )
             |
             2

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

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

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

       +
      / \
  node   node
  

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

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

      ( )
       |
      node
  

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Я написал такой парсер с некоторыми базовыми методами, такими как Infix -> RPN и Shunting Yard и Tree Traversals . Вот реализация, которую я придумал .
Он написан на C ++ и компилируется как в Linux, так и в Windows.
Любые предложения / вопросы приветствуются.

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

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

Я как бы собрал это консольное приложение на 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()