式ツリーを作成するときに後置に変換する必要がありますか？

Question

与えられた表現ツリーを中置形式で作成したいと思います。式を後置に変換してからツリーを作成する必要がありますか？私は何とか問題自体に依存していることを理解しています。しかし、それは未知数と演算子を持つ数学関数の単純な表現であると仮定します：/ *^+ - 。

Answer 1

いいえ。式ツリーを構築する場合は、式を後置に変換する必要はありません。解析するときに式ツリーを作成するほうが簡単になります。

私は通常、式のための再帰的降下パーサを書きます。その場合、各再帰呼び出しは、それが解析する部分式のツリーを返します。反復的なshunting-yardのようなアルゴリズムを使いたいなら、それも可能です。

import re 

def toTree(infixStr): 
    # divide string into tokens, and reverse so I can get them in order with pop() 
    tokens = re.split(r' *([\+\-\*\^/]) *', infixStr) 
    tokens = [t for t in reversed(tokens) if t!=''] 
    precs = {'+':0 , '-':0, '/':1, '*':1, '^':2} 

    #convert infix expression tokens to a tree, processing only 
    #operators above a given precedence 
    def toTree2(tokens, minprec): 
     node = tokens.pop() 
     while len(tokens)>0: 
      prec = precs[tokens[-1]] 
      if prec<minprec: 
       break 
      op=tokens.pop() 

      # get the argument on the operator's right 
      # this will go to the end, or stop at an operator 
      # with precedence <= prec 
      arg2 = toTree2(tokens,prec+1) 
      node = (op, node, arg2) 
     return node 

    return toTree2(tokens,0) 

print toTree("5+3*4^2+1") 

この版画：

ここでのノードのタプルで木を作るPythonで簡単な再帰下降パーサの

（ '+'、（ '+'、 '5' 、（ '*'、 '3'、（ '^'、 '4'、 '2'）））、 '1'）

は、ここでそれを試してみてください。

https://ideone.com/RyusvI

上記の再帰的降下スタイルは、多くのパーサーを記述した結果であることに注意してください。今私はかなり多くの場合、常にこのように式を解析します（トークン化ではなく再帰的な部分）。式パーザーが可能なだけの簡単さで、括弧を扱いやすくしたり、代入演算子のように右から左に関連付ける演算子も簡単にできます。