oop - ポリモーフィズムを使用した式評価とツリー ウォーキング? (スティーブ・イェッジ)

Question

今朝、私はSteve Yegge の: When Polymorphism Failsを読んでいたとき、彼の同僚が Amazon での面接に来た潜在的な従業員に尋ねていた質問に出くわしました。

実際のポリモーフィズムの例として、古典的な「eval」インタビューの質問を見てみましょう。これは (私の知る限り) Ron Braunstein によって Amazon にもたらされました。OOP 設計、再帰、バイナリ ツリー、ポリモーフィズムとランタイム タイピング、一般的なコーディング スキル、および (さらに難しくしたい場合は) 解析理論など、さまざまな重要なスキルを調べることができるため、この質問は非常に豊富です。 .

ある時点で、志願者は、「+」、「-」、「*」、「/」などの二項演算子のみを使用していると仮定して、算術式を二分木として表現できることに気付きます。リーフ ノードはすべて数値であり、内部ノードはすべて演算子です。式を評価することは、木を歩くことを意味します。候補者がこれに気付いていない場合は、そっと誘導するか、必要に応じて伝えることができます。

と言ってしまっても、やはり面白い問題です。

質問の前半は、一部の人々 (名前は息が詰まるまで守りますが、イニシャルはウィリー・ルイスです) は、自分自身を開発者と呼んで Amazon で働きたい場合の仕事の要件であると感じていますが、実際にはちょっと難しいです。 . 問題は、「2 + (2)」などの算術式 (文字列など) から式ツリーにどのように移行するかです。ある時点で、この質問に対する ADJ チャレンジが行われる可能性があります。

後半は、これが 2 人のプロジェクトで、あなたのパートナー ("ウィリー" と呼びます) が文字列式をツリーに変換する責任があるとしましょう。簡単な部分を取得します。ウィリーがツリーを構築するクラスを決定する必要があります。任意の言語で実行できますが、いずれかを選択するようにしてください。そうしないと、ウィリーがアセンブリ言語を渡してくれます。彼が気難しいと感じているのは、もはや生産されていないプロセッサーのためでしょう。

どれだけ多くの候補者がこれを好んでいるかに驚かれることでしょう。

答えは言いませんが、Standard Bad Solution には、switch または case ステートメント (または単に古き良きカスケード if) の使用が含まれます。Slightly Better Solution には、関数ポインターのテーブルの使用が含まれ、おそらく最善の解決策には、ポリモーフィズムの使用が含まれます。いつかやり遂げることをお勧めします。楽しいもの！

それでは、3 つの方法すべてで問題に取り組みましょう。"2 + (2)" などの算術式 (文字列など) から、カスケード if、関数ポインターのテーブル、および/またはポリモーフィズムを使用した式ツリーにどのように移行しますか?

1 つ、2 つ、または 3 つすべてに自由に取り組んでください。

[更新: ほとんどの回答に一致するようにタイトルを変更しました。]

Answer 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)

テストは、コンストラクターを使用してバイナリ ツリーを構築しているだけです。

プログラム構造:

抽象基本クラス: ノード

• すべてのノードはこのクラスから継承します

抽象基本クラス: BinaryNode

• すべての二項演算子はこのクラスから継承します
• process メソッドは、式を評価して結果を返す作業を行います

二項演算子クラス: Plus、Minus、Mul、Div

• 左側と右側の部分式にそれぞれ 1 つずつ、2 つの子ノード

数値クラス: Num

• 17 や 42 などのリーフノードの数値を保持します

Answer 2

これは、うさぎの穴のような構文解析/コンパイラ理論に入ります... Dragon Bookは、コンパイラ構築の標準テキストであり、これを極端なものにします。この特定のケースでは、基本的な算術のための文脈自由文法を構築し、その文法を使用して抽象構文木を解析したいとします。次に、ツリーを反復処理して、ツリーを下から上に縮小します（この時点で、ポリモーフィズム/関数ポインター/ switchステートメントを適用してツリーを縮小します）。

これらのメモは、コンパイラーと構文解析の理論で非常に役立つことがわかりました。

Answer 3

ノードの表現

括弧を含める場合は、次の5種類のノードが必要です。

• バイナリノード：マイナスMul Divを追加します。
  これらには、左側と右側の2つの子があります。

       +
      / \
  node   node
  

• 値を保持するノード：Val
  子ノードはなく、数値のみ

• 親を追跡するノード：
  部分式の単一の子ノードを親

      ( )
       |
      node
  

多態的なソリューションの場合、次のようなクラスの関係が必要です。

• ノード
• BinaryNode：ノードから継承
• プラス：バイナリノードから継承
• マイナス：バイナリノードから継承
• Mul：バイナリノードから継承
• Div：バイナリノードから継承
• 値：ノードから継承
• パレン：ノードから継承

eval（）と呼ばれるすべてのノードの仮想関数があります。その関数を呼び出すと、その部分式の値が返されます。

Answer 4

問題は、括弧を解析する必要があるのに、それらが二項演算子ではないことだと思います。(2) を 2 に評価される単一のトークンとして使用する必要がありますか?

かっこは式ツリーに表示する必要はありませんが、その形状に影響を与えます。たとえば、(1+2)+3 のツリーは 1+(2+3) とは異なります。

    +
   / \
  +   3
 / \
1   2

対

    +
   / \
  1   +
     / \
    2   3

括弧はパーサーへの「ヒント」です (たとえば、superjoe30 では、「再帰的に下降する」ため)。

Answer 5

答えは言いませんが、標準的な悪い解決策には、switch ステートメントまたは case ステートメント (または単に古き良きカスケード if) の使用が含まれます。Slightly Better Solution には、関数ポインターのテーブルの使用が含まれ、おそらく最善の解決策には、ポリモーフィズムの使用が含まれます。

過去 20 年間のインタープリターの進化は、逆方向に進んでいると見なすことができます。ポリモーフィズム (単純な Smalltalk メタサーキュラー インタープリターなど) から関数ポインター (単純な Lisp 実装、スレッド化されたコード、C++) への切り替え (単純なバイト コード インタープリター)、そしてそれ以降。 JITなどに-非常に大きなクラスを必要とするか、（単一ポリモーフィック言語では）ポリモーフィズムをタイプケースに減らすダブルディスパッチが必要であり、ステージ1に戻ります。ここで使用されている「最高」の定義は何ですか?

単純なものについては、ポリモーフィック ソリューションで問題ありません。これは私が以前に作成したものですが、たとえば、数千のデータ ポイントを持つ関数をプロットする場合は、スタックとバイトコード/スイッチ、またはランタイムのコンパイラを利用する方が通常は優れています。

Answer 6

String Tokenizer + LL(1) Parser は式ツリーを提供します... ポリモーフィズムの方法には、関連する演算子ごとにオーバーライドされる「evaluate(a,b)」関数を持つ抽象算術クラスが含まれる場合があります (追加、減算など) を使用して適切な値を返し、ツリーには整数および算術演算子が含まれており、これらはツリーのポスト (?) オーダー トラバーサルによって評価できます。

Answer 7

うーん...バックトラックなしでトップダウンのパーサーを書くことはできないと思うので、ある種のシフト削減パーサーでなければなりません。もちろん、LR(1) または LALR でさえ、次の (アドホックな) 言語定義で問題なく機能します。

スタート -> E1
E1 -> E1+E1 | E1-E1
E1 -> E2*E2 | E2/E2 | E2
E2 ->数| (E1)

E1 と E2 に分けることは、+ と - よりも * と / の優先順位を維持するために必要です。

しかし、パーサーを手で書かなければならない場合は、次のようにします。

• 2 つのスタック。1 つはツリーのノードをオペランドとして格納し、もう 1 つは演算子を格納します。
• 入力を左から右に読み取り、数値のリーフ ノードを作成し、それらをオペランド スタックにプッシュします。
• スタックに 2 つ以上のオペランドがある場合は、2 をポップし、それらをオペレーター スタックの最上位のオペレーターと組み合わせて、この構造をオペランド ツリーにプッシュします。
• 次の演算子は、現在スタックの一番上にある演算子よりも優先されます。

これにより、ブラケットの処理の問題が残ります。洗練された (私が思った) 解決策の 1 つは、各演算子の優先順位を数値として変数に格納することです。だから最初は、

• int プラス、マイナス = 1;
• int mul、div = 2;

左括弧が表示されるたびに、これらすべての変数が 2 ずつ増加し、右括弧が表示されるたびに、すべての変数が 2 ずつ減少します。

これにより、3*(4+5) の + が * よりも優先され、3*4 がスタックにプッシュされなくなります。代わりに、5 を待ち、4+5 を押してから 3*(4+5) を押します。

Answer 8

問題は、エバリュエーターではなく、パーサーの書き方だと思います。というか、文字列から式ツリーを作成する方法。

基本クラスを返す case ステートメントは正確にはカウントされません。

「ポリモーフィック」ソリューションの基本構造 (別の言い方をすれば、これを何で構築するかは気にしません。可能な限り最小限のコードを書き直して拡張したいだけです) は、オブジェクト階層を既知の型の (動的) セットを含むストリーム。

ポリモーフィック ソリューションの実装の要点は、パターン マッチャー (おそらく再帰的) から式オブジェクトを作成する方法を用意することです。つまり、BNF または同様の構文をオブジェクト ファクトリにマップします。

Answer 9

Re: ジャスティン

ツリーは次のようになると思います。

  +
 / \
2  ( )
    |
    2

基本的に、その下のツリーを評価するだけの「評価」ノードがあります。それは、次のように最適化されます。

  +
 / \
2   2

この場合、括弧は不要であり、何も追加しません。彼らは論理的に何も追加しないので、ただ立ち去ってしまいます。

Answer 10

関数型言語imoを使用する必要があります。オブジェクト指向言語では、ツリーを表現して操作するのが難しくなります。

Answer 11

わかりました、これが私の単純な実装です。申し訳ありませんが、オブジェクトを使用する気がしませんでしたが、変換は簡単です。私は少し邪悪なウィリーのように感じます (スティーブの話から)。

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

Answer 12

ちょっとした概念実証として、この C# コンソール アプリをまとめてみました。もっと良くなる可能性があると感じてください（GetNodeのswitchステートメントはちょっと不格好です（クラス名を演算子にマップしようとして空白にぶつかったのでそこにあります））。どのように改善できるかについての提案は大歓迎です。

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;
            }
        }
    }
}

Answer 13

Infix -> RPNや Shunting Yardや Tree Traversalsなどのいくつかの基本的な手法を使用して、このようなパーサーを作成しました 。 これが私が思いついた実装です。
C++ で書かれており、Linux と Windows の両方でコンパイルできます。
提案/質問は大歓迎です。

それでは、3 つの方法すべてで問題に取り組みましょう。"2 + (2)" などの算術式 (文字列など) から、カスケード if、関数ポインターのテーブル、および/またはポリモーフィズムを使用した式ツリーにどのように移行しますか?

これは興味深いですが、これはオブジェクト指向プログラミングの領域に属しているとは思いません...構文解析技術と関係があると思います。

Answer 14

あるいは、これが本当の問題です: (2) を BST としてどのように表すことができますか? それが私をつまずかせている部分です。

再帰。

Answer 15

@ジャスティン：

ノードの表現に関する私のメモを見てください。そのスキームを使用する場合は、

2 + (2)

として表すことができます

           .
          / \
         2  ( )
             |
             2

Answer 16

人々が以前に言及したように、式ツリーを使用する場合、括弧は必要ありません。式ツリーを見ていると、操作の順序は簡単で明白になります。括弧はパーサーへのヒントです。

受け入れられた答えは問題の半分の解決策ですが、残りの半分 (実際に式を解析すること) はまだ解決されていません。通常、この種の問題は再帰降下パーサーを使用して解決できます。このようなパーサーを作成することは、多くの場合楽しい作業ですが、言語解析用の最新のツールのほとんどは、それを抽象化してくれます。

文字列に浮動小数点数を許可すると、パーサーも大幅に難しくなります。C で浮動小数点数を受け入れるように DFA を作成する必要がありました。これは非常に骨の折れる詳細な作業でした。有効な浮動小数点数には、10、10.、10.123、9.876e-5、1.0f、.025 などがあります。インタビューでは、(簡潔さと簡潔さを優先して) 何らかの説明がなされたと思います。