Префиксная нотация для инфиксной нотации в Python - PullRequest
Новая
       40

Префиксная нотация для инфиксной нотации в Python

3 голосов
/ 28 июня 2011

Я пишу небольшой калькулятор (с префиксной нотацией), и мне интересно, как бы я конвертировал префиксную нотацию в инфиксную нотацию. В настоящее время у меня есть функция, но она странная, и я не знаю, как это исправить. Будучи странным, я имею в виду, что если дать ['+', x, y], то вернется (() + x + () + y), что меня смущает. Вот код. 

def pre_in(read):
    #print read
    tempOp = read[0]
    body = read[1:]
    expr = []
    for i in range(len(body)-1):
        if not isinstance(body[i], list) and body[i] != " ":
            expr.append(str(body[i]))
            expr.append(tempOp)
        else:
            expr.append(str(pre_in(body[i])))
            expr.append(tempOp)
    try:
        if not isinstance(body[-1], list):
            expr.append(str(body[-1]))
        else:
            expr.append(str(pre_in(body[-1])))
    except:
        pass
    if expr != None: return "("+' '.join(expr)+")"

Что я делаю не так?

Ответы [ 4 ]

4 голосов
/ 28 июня 2011

На самом деле ваш код работает нормально. 

print pre_in ( ['+', 8, 9] )

дает 

(8 + 9)

РЕДАКТИРОВАТЬ: Как уже говорили другие, возможно, вы хотите использовать стек.Вот простая реализация с песочницей с некоторыми примерами (она выводит много скобок, но те не мешают): 

class Calculator:
    def __init__ (self):
        self.stack = []

    def push (self, p):
        if p in ['+', '-', '*', '/']:
            op1 = self.stack.pop ()
            op2 = self.stack.pop ()
            self.stack.append ('(%s %s %s)' % (op1, p, op2) )
        elif p == '!':
            op = self.stack.pop ()
            self.stack.append ('%s!' % (op) )
        elif p in ['sin', 'cos', 'tan']:
            op = self.stack.pop ()
            self.stack.append ('%s(%s)' % (p, op) )
        else:
            self.stack.append (p)

    def convert (self, l):
        l.reverse ()
        for e in l:
            self.push (e)
        return self.stack.pop ()

c = Calculator ()

print c.convert ( ['+', 8, 9] )
print c.convert ( ['!', 42] )
print c.convert ( ['sin', 'pi'] )
print c.convert ( ['+', 'sin', '/', 'x', 2, 'cos', '/', 'x', 3] )
1 голос
/ 28 июня 2011

Риск быть немного излишним для такого рода простых заданий разбора / преобразования, вы можете посмотреть на pyparsing .

1 голос
/ 28 июня 2011

Если ваша цель не состоит в том, чтобы разработать алгоритм самостоятельно, перейдите на эту страницу . Есть ссылки на две страницы, которые объясняют алгоритм infix-> postfix и postfix-> infix. (А также, если вы хотите узнать, как алгоритмы реализованы в javascript, вы можете взглянуть на исходный код страницы.)

0 голосов
/ 23 июня 2012

Вот довольно простое рекурсивное решение. 

def prefix_to_infix(expr):
    if type(expr) != type([]):
        # The expression is a number or variable.
        return str(expr)
    elif len(expr) == 2:
        # This is an operator expression with 1 argument.
        return str(expr[1])
    else:
        # This is an operator expression with 2 or more arguments.
        operator = expr[0]
        left_arg = prefix_to_infix([operator] + expr[1:-1])
        right_arg = prefix_to_infix(expr[-1])
        return "({0}{1}{2})".format(left_arg, operator, right_arg)

# prefix_to_infix(['+',1,2,3,4,5]) = '((((1+2)+3)+4)+5)'
# prefix_to_infix(['+',1,2,['*',3,4,5],6,7,8]) = '(((((1+2)+(3*4*5))+6)+7)+8)'
...