Модифицируйте фрагмент кода, чтобы разрешить значения с плавающей запятой и отрицательные числа, а также произвольное количество пробелов между символами во введенной строке - PullRequest
Новая
       105

Модифицируйте фрагмент кода, чтобы разрешить значения с плавающей запятой и отрицательные числа, а также произвольное количество пробелов между символами во введенной строке

0 голосов
/ 12 марта 2020

Следующий фрагмент кода получает инфиксную строку и преобразует ее в постфикс и выводит это новое выражение в виде строки. Однако он не поддерживает отрицательные числа или числа с плавающей запятой. В следующем коде допускаются только одиночные значения di git:

Например, (0-9), не похожее на 10 или 11. В противном случае выдается «ошибка ключа» . Кроме того, если я добавляю знак минус, он также выдает ошибку ключа. 

class Stack:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

    def peek(self):
        return self.items[len(self.items)-1]

    def size(self):
        return len(self.items)

    def isNumber(self, txt):
        if not isinstance(txt,str) or len(txt.strip())==0:
            print("Argument error in isNumber")
            return False
        # YOUR CODE STARTS HERE
        try:
            float(txt)
            return True
        except ValueError:
            return False

#########################################################################################################

    def infixToPostfix(infixexpr):
        prec = {}
        prec["^"] = 4
        prec["*"] = 3
        prec["/"] = 3
        prec["+"] = 2
        prec["-"] = 2
        prec["("] = 1
        opStack = Stack()
        postfixList = []
        tokenList = infixexpr.split()

        for token in tokenList:
            if token in "0123456789":
                postfixList.append(token)
            elif token == '(':
                opStack.push(token)
            elif token == ')':
                topToken = opStack.pop()
                while topToken != '(':
                    postfixList.append(topToken)
                    topToken = opStack.pop()
            else:
                while (not opStack.isEmpty()) and \
                   (prec[opStack.peek()] >= prec[token]):
                      postfixList.append(opStack.pop())
                opStack.push(token)

        while not opStack.isEmpty():
            postfixList.append(opStack.pop())
        return " ".join(postfixList)

Так что вот мое исправление, чтобы также разрешать поплавки:

Я добавил эту функцию: 

def isNumber(x):
    try:
        float(x)
        return True
    except ValueError:
        return False

И изменил эту строку: if token in "0123456789": на эту: if Stack.isNumber(token):

А теперь код позволяет плавать.

Так в чем же другая проблема? Ну, другая проблема заключается в том, что мой код предполагает, что входная строка будет иметь ровно один пробел между каждым из символов, поэтому я использую string.split (), чтобы поместить все символы в список. За исключением того, что во входной строке может быть произвольное количество пробелов между символами, и если пробелов нет, мой код будет сравнивать что-то вроде "((" с моим списком символов и не найдет его, и выдаст Key error . Так как я должен разрешить отрицательные числа (отмеченные знаком минус). Как я могу изменить свой код так, чтобы он больше не выбрасывал keyerror и позволял мне иметь отрицательные числа?

Когда я делаю это:

print(Stack.infixToPostfix("( ( 1 + 3 ) ) * 4 - ( 9.2 - 0 ) * ( 5 + 8 )"))

Мой код выводит это: 1 3 + 4 * 9.2 0 - 5 8 + * -

, что прекрасно работает, однако, если я уберу один пробел:

"(( 1 + 3 ) ) * 4 - ( 9.2 - 0 ) * ( 5 + 8 )"

Мой код больше не работает. Key error '((' Я знаю, почему выдает эту ошибку (объяснение выше), но я не уверен как это исправить.

Итак, последний вопрос TL: DR

Как изменить мой код infixtopostfix, чтобы разрешить произвольное количество пробелов между символами и допускать отрицательные числа?

Ответы [ 2 ]

1 голос
/ 12 марта 2020

Вы можете просто проверить целые числа или числа с плавающей запятой с помощью try-кроме, и это также будет обрабатывать отрицательные числа. Проблема в том, что разбиение по пробелам намного менее гибко и надежно, чем фактический анализ токенов, и это накладывает огромную нагрузку на любого, кто использует функцию.

Вам нужна функция токенизатора. К счастью, в python есть модуль токенизатора, хотя в первый раз перейти не так просто. Или вы можете написать свой собственный.

Вот быстрая реализация с использованием библиотеки 

from io import StringIO
from tokenize import generate_tokens, NUMBER, OP

def tokenizer(s):
    generator = generate_tokens(StringIO(s).readline)
    for toknum, tokval, _, _, _ in generator:
        if toknum in (NUMBER, OP):
            yield tokval

Просто измените свой код на использование 

for token in tokenizer(infixexpr):

Это исправляет более длинные числа и десятичные числа числа и обрабатывает ваш тестовый пример со всеми удаленными пробелами: 

print (infixToPostfix("((1+3))*4-(9.2-0)*(5+8)"))
1 3 + 4 * 9.2 0 - 5 8 + * -

(я думал, что это должна быть отдельная функция, а не член класса. Возможно, вы захотите сделать это, отменив отступ функции. )

Отрицательные числа потребуют немного больше, потому что токенизатор немедленно вернет "-" как оператор. Вы можете написать свою собственную функцию токенизатора, которая читает -55 как один токен, или вы можете отслеживать состояние и понимать, что если вы не ожидаете оператора, то знак минус должен сигнализировать, что следующий токен является отрицательным числом , См. Как отличить оператор '-' от отрицательного числа для токенизатора

Еще одна проблема, помимо вопросов, которые вы задавали, - это унарные операторы. Если вы позволите знак минус перед выражением, то вы должны обрабатывать его как оператор. Алекс обработал их в другом ответе, и вы можете посмотреть на Алгоритм инфикса в постфикс, который заботится об унарных операторах В некоторых реализациях отрицательные числа выводятся как "(-5)" в постфиксе. Некоторые используют пробелы, хотя это экономит место, если у вас нет пробелов - в любом случае, это не очень удобно для чтения человеком.

1 голос
/ 12 марта 2020

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

def tokenize(s):
    s = re.sub(r"\s+", "", s)
    result = []
    while (s):
        if s[0] in "0123456789":
            number = s[0]
            s = s[1:]
            while (s and s[0] in "0123456789."):
                number += s[0]
                s = s[1:]
            result.append(number)
            if s:
                result.append(s[0])
                s = s[1:]
        else:
            result.append(s[0])
            s = s[1:]
    return result

Тогда вам нужно будет отслеживать унарные операции плюс и минус. Для этого мы вводим специальную операцию 'neg' - когда вы обрабатываете эту операцию в постфиксной нотации, вы просто отрицаете значение в верхней части стека операндов.

Вы ожидаете одинарные операции плюс и минус в начале строки или сразу после открытия '('. После обработки числового операнда или закрытия ')' вы сбрасываете унарный флаг в False, потому что унарный плюс или минус не могут появляться в этих позициях. Когда унарный флаг равен true, вы должны отслеживать входящие «+» и «-», используйте для него логический флаг «neg». Измените состояние 'neg' на каждом '-'. Когда вы, наконец, найдете операнд - проверьте состояние флага 'neg'. Если это правда, то вам нужно поставить нашу специальную операцию 'neg' после операнда. Помещение операции 'neg' после закрытия ')' немного сложно и требует использования opStack. 

def infixToPostfix(infixexpr):
        prec = {}
        prec["^"] = 3
        prec["*"] = 3
        prec["/"] = 3
        prec["+"] = 2
        prec["-"] = 2
        prec["("] = 1
        prec["neg"] = 1
        opStack = Stack()
        postfixList = []
        tokenList = tokenize(infixexpr)
        print(tokenList)

        unary = True
        neg = False

        for token in tokenList:
            if unary and token in "+-":
                if token == '-':
                     neg = not neg
            elif isNumber(token):
                postfixList.append(token)
                if neg:
                    postfixList.append("neg")
                    neg = False
                unary = False
            elif token == '(':
                if neg:
                    opStack.push("neg")
                    neg = False
                opStack.push(token)
                unary = True
            elif token == ')':
                topToken = opStack.pop()
                unary = False
                while topToken != '(':
                    postfixList.append(topToken)
                    topToken = opStack.pop()
                if not opStack.isEmpty() and opStack.peek() == "neg":
                    postfixList.append(opStack.pop())
            else:
                while (not opStack.isEmpty()) and \
                   (prec[opStack.peek()] >= prec[token]):
                      postfixList.append(opStack.pop())
                opStack.push(token)

        while not opStack.isEmpty():
            postfixList.append(opStack.pop())
        return " ".join(postfixList)

Ввод: 

"-(( 1 + 3 ) ) * 4 - ( -9.2 - 0 ) * ( 5 + 8 ) - 4 * (-2)"

Выход: 

1 3 + neg 4 * 9.2 neg 0 - 5 8 + * - 4 2 neg * -

ОБНОВЛЕНИЕ 2020-03-12

Если вы хотите обрабатывать отрицательные числа как один отрицательный операнд, а не как положительный операнд, за которым следует операция 'neg', тогда вы просто нужна очень маленькая модификация метода infixToPostfix. Вам нужно только изменить ветку elif isNumber(token). Я поставлю это здесь полностью, хотя: 

def infixToPostfix(infixexpr):
        prec = {}
        prec["^"] = 3
        prec["*"] = 3
        prec["/"] = 3
        prec["+"] = 2
        prec["-"] = 2
        prec["("] = 1
        prec["neg"] = 1
        opStack = Stack()
        postfixList = []
        tokenList = tokenize(infixexpr)

        unary = True
        neg = False

        for token in tokenList:
            if unary and token in "+-":
                if token == '-':
                     neg = not neg
            elif isNumber(token):
                if neg:
                    postfixList.append("-" + token)
                else:
                    postfixList.append(token)
                neg = False
                unary = False
            elif token == '(':
                if neg:
                    opStack.push("neg")
                    neg = False
                opStack.push(token)
                unary = True
            elif token == ')':
                topToken = opStack.pop()
                unary = False
                while topToken != '(':
                    postfixList.append(topToken)
                    topToken = opStack.pop()
                if not opStack.isEmpty() and opStack.peek() == "neg":
                    postfixList.append(opStack.pop())
            else:
                while (not opStack.isEmpty()) and \
                   (prec[opStack.peek()] >= prec[token]):
                      postfixList.append(opStack.pop())
                opStack.push(token)

        while not opStack.isEmpty():
            postfixList.append(opStack.pop())
        return " ".join(postfixList)

Теперь вывод равен 

1 3 + neg 4 * -9.2 0 - 5 8 + * - 4 -2 * -

ОБНОВЛЕНИЕ 2020-03-13

В В исходном посте я поставил следующее предложение:

Вы ожидаете унарные операции плюс и минус в начале строки или сразу после открытия '('.

код там и в предыдущем обновлении также отражает это. Я знал, что это технически не совсем правильно. Унарную операцию можно ожидать и после операции. Однако я не хотел разрешать выражения типа 2+--+-+3, поэтому я исключил возможность для унарных операций после операции. К сожалению, это также исключает возможность для 2^-3. Если вы хотите иметь возможность разбирать выражения, такие как 2^-3, то вам просто нужно разрешить унарную операцию после другой операции, она требует добавления одиночная строка unary = True в ветви else: 

            else:
                while (not opStack.isEmpty()) and \
                   (prec[opStack.peek()] >= prec[token]):
                      postfixList.append(opStack.pop())
                opStack.push(token)
                unary = True   # This is the only new line

Теперь вы можете анализировать 2^-3 как 2^(-3). Однако он также позволяет анализировать 2+-3 как 2+(-3). I всегда в и последняя возможность очень уродливая в компьютерных языках, но если это хорошо для вас - хорошо. Конечно, вы также можете разрешить разбор унарной операции только после ^, но не после других операций. Это потребует проверки текущего токена и установки unary в значение «Истина», только если токен находится в списке операций, допускающих после него одинарный минус.

...