Хорошая реализация Infix to Prefix в Python, которая охватывает больше операторов (например, ‹, ‹= и т. д.) программы C?

Я безуспешно искал реализацию 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]

python c conditional-operator prefix infix-notation
person Oeufcoque Penteano    schedule 30.07.2012    source источник

Ответы (2)


arrow_upward
0
arrow_downward

У меня нет времени писать реализацию прямо сейчас, но вот реализация, которую я написал, которая преобразует инфиксную нотацию в постфиксную (обратная полировка) (ссылка: Алгоритм маневровой станции). Не должно быть слишком сложно изменить этот алгоритм, чтобы вместо этого сделать префикс:

  • ops — это set() токенов оператора.
  • 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
person Community    schedule 30.07.2012

arrow_upward
0
arrow_downward

Я читаю «Введение в структуры данных и алгоритмы» — Жан-Поль Трембле и написал на 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/+*
person jdhall    schedule 28.08.2018