2

私は、インフィックスをプレフィックスに変換し、十分な量の算術演算子と論理演算子に対応し、適切な Python 実装でそのプロパティを気にする Python の実装を探していましたが、あまり運がありませんでした。具体的には、C プログラムの条件節に現れる演算子に興味があります。a > 0 && b > 1(たとえば、接頭辞に変換されます。

私はまだPythonの初心者なので、誰かが私に実装やこれに関するヒントを提供してくれれば幸いです。

参照を失ったインターネット周辺の実装を見つけました（以下）が、より単純な演算子のみを気にします。私はこのバージョンでこれを行う方法について少し無知であり、すべての演算子が既に含まれているバージョンを誰かが知っている場合は、誤って演算子が無視されないようにしてください.

このような実装では、括弧も考慮する必要があります。

詳細が必要な場合はコメントしてください！

ありがとうございました。

def parse(s):
for operator in ["+-", "*/"]:
    depth = 0
    for p in xrange(len(s) - 1, -1, -1):
        if s[p] == ')': depth += 1
        if s[p] == '(': depth -= 1
        if not depth and s[p] in operator:
            return [s[p]] + parse(s[:p]) + parse(s[p+1:])
s = s.strip()
if s[0] == '(':
    return parse(s[1:-1])
return [s]
4

2 に答える 2

0

今は実装を書く時間があまりありませんが、ここに私が書いた infix を postfix (逆ポーランド) 記法に変換する実装があります (参照: Shunting-yard アルゴリズム)。このアルゴリズムを変更して、代わりにプレフィックスを実行するのはそれほど難しくありません。

  • opsset()演算子トークンのです 。
  • precキーとしてオペランド トークンをdict() 含み、値として演算子の優先順位の整数を含む (例: { "+": 0, "-": 0, "*": 1, "/": 1})
  • 正規表現を使用して、文字列をトークンのリストに解析します。

（本当に、ops組み合わせるprecことができます）

def infix_postfix(tokens):
    output = []
    stack = []
    for item in tokens:
        #pop elements while elements have lower precedence
        if item in ops:
            while stack and prec[stack[-1]] >= prec[item]:
                output.append(stack.pop())
            stack.append(item)
        #delay precedence. append to stack
        elif item == "(":
            stack.append("(")
        #flush output until "(" is reached
        elif item == ")":
            while stack and stack[-1] != "(":
                output.append(stack.pop())
            #should be "("
            print stack.pop()
        #operand. append to output stream
        else:
            output.append(item)
    #flush stack to output
    while stack:
        output.append(stack.pop())
    return output
于 2012-07-30T02:18:43.130 に答える
0

An Introduction to Data Structures and Algorithms - Jean-Paul Tremblay を読んでいて、その本で説明されているプログラムの Python 実装を RPN への挿入用に書きました。

SYMBOL = ['+', '-', '*', '/', '^', 'VAR', '(', ')']
INPUT_PRECEDENCE = [1, 1, 3, 3, 6, 7, 9, 0]
STACK_PRECEDENCE = [2, 2, 4, 4, 5, 8, 0, None]
RANK = [-1, -1, -1, -1, -1, 1, None, None]

INFIX = '(a+b^c^d)*(e+f/d)'
POLISH_TEST = 'abcd^^+efd/+*'

def getIndex (symbol):
    if (symbol.isalpha()):
        index = 5
    else:
        index = SYMBOL.index (symbol)
    return index

def InfixToReversePolish (INFIX):
    #initialize
    POLISH = []
    STACK = []
    #append ')' to infix
    INFIX = INFIX + ')'
    #push '(' on to the stack
    STACK.append (SYMBOL[6])
    for i in range(0, len(INFIX)):
        #read the next char in the infix
        NEXT = INFIX[i]
        #what is the index of next in the precedence and rank tables?
        index = getIndex (NEXT)
        if (len (STACK) == 0):
            print ('Invalid input string')
            return
        #if we encounter ')', we pop the stack till we find '('. we discard both '(' and ')'
        if index == 7:
            ch = STACK.pop()
            while getIndex (ch) != 6:
                POLISH.append (ch)
                ch = STACK.pop()
            continue
        #while next input precedence is less than or equal to the top stack precedence    
        while (INPUT_PRECEDENCE[index] <= STACK_PRECEDENCE[getIndex(STACK[len(STACK) - 1])]):
            POLISH.append (STACK.pop())
        #push next on to the stack
        STACK.append (NEXT)
    return POLISH

ex = ''.join (InfixToReversePolish (INFIX))
print ('Reverse Polish Expression is', ex)

Reverse Polish Expression is abcd^^+efd/+*
于 2018-08-28T12:09:53.830 に答える