Оценка экспрессии и Хождение по деревьям с использованием полиморфизма? (Ала Стив Егге)

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

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

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

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

класс номера: Num

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

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

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

    +
   / \
  +   3
 / \
1   2

против

    +
   / \
  1   +
     / \
    2   3

Скобки - это "hint" для парсера (например, per superjoe30, чтобы " рекурсивно спуститься")

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

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

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

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

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

       +
      / \
  node   node
  

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

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

      ( )
       |
      node
  

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Основная структура решения "polymorphic" (это еще один способ сказать, что мне все равно, с чем вы это строите, я просто хочу расширить его, переписав наименьшее количество кода) - это десериализация иерархии объектов из потока с (динамическим) набором известных типов.

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

Re: Джастин

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

  +
 / \
2  ( )
    |
    2

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

  +
 / \
2   2

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

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

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

Рекурсия.

@Justin:

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

2 + (2)

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

           .
          / \
         2  ( )
             |
             2

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

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

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

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

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

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

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