Оценка выражения и прохождение дерева с использованием полиморфизма? (ala Steve Yegge)

Ответ 1

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

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

двоичные классы операторов: плюс, Минус, Мул, Div

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

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

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

Ответ 2

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

Я нашел эти примечания, чтобы быть невероятно полезной в теории компилятора и анализа.

Ответ 3

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

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

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

       +
      / \
  node   node
  

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

• a node для отслеживания параметров: Paren и один дочерний node для подвыражения

      ( )
       |
      node
  

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

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

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

Ответ 4

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

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

    +
   / \
  +   3
 / \
1   2

против

    +
   / \
  1   +
     / \
    2   3

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

Ответ 5

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

Ответ 6

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

Начало → E1
E1 → E1 + E1 | E1-E1
E1 → E2 * E2 | E2/E2 | E2
E2 → номер | (Е1)

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

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

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

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

• int plus, минус = 1;
• int mul, div = 2;

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

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

Ответ 7

Re: Justin

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

  +
 / \
2  ( )
    |
    2

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

  +
 / \
2   2

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

Ответ 8

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

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

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

Ответ 9

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

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

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

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

Ответ 10

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

Ответ 11

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

Рекурсия.

Ответ 12

@Justin:

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

2 + (2)

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

           .
          / \
         2  ( )
             |
             2

Ответ 13

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

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

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

Ответ 14

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

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

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

Ответ 15

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

Ответ 16

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

#!/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()