Уведомления

Группа в Telegram: присоединиться

#1 Июнь 27, 2020 17:12:44

Python_newbie13
Зарегистрирован: 2020-06-27
Сообщения: 13
Репутация: +  0  -
Профиль   Отправить e-mail  

Польская нотация.

 perators = ["+", "-",]
operators1 = ["*", "/"]
def priority(operator):
    if operator in operators:
        x = 1
    if operator in operators1:
        x = 2
    return x
def transformation(expression):
    l = []
    s = ''
    n = 0
    for i in expression:
        if i.isdigit():
            s = s + i
            n = n + 1
        if i in operators or i in operators1:
            l.append(s)
            s = ''
            l.append(i)
            n = n + 1
        if len(expression) == n:
            l.append(s)
    return l
def polish_notation():
    exit = []
    stack = []
    list = transformation("8+4*3-2*2+9*9*2")
#Цикл, отвечащий за преобразование в нотацию
    for i in list:
        #Если операнда кидаем на выход
        if i.isdigit():
            exit.append(int(i))
        #Cдесь обрабываем операторы    
        else:
            #Если это первый оператор, то кидаем в стек 
            if len(stack) == 0:
                stack.append(i)
            #Если нет, то кидаем его в стек и сравниваем приоритеты, пока стек имеет 2 и более элементов.
            #Если приоритет предпоследнего оператора в стеке больше или равен, то кидаем предпоследний элемент на выход
            else:
                stack.append(i)
                while len(stack)>1 and priority(stack[-2]) >= priority(stack[-1]):
                    exit.append(stack.pop(-2))
        #Если мы обрабатываем последний элемент, то выгружаем стек. 
        if i is list[-1]:
            while len(stack)>0:
                exit.append(stack.pop())
        print(exit)
        print(stack)
    return exit
Я преобразую обычную запись в польскую. При этом если в (8+4*3-2*2+9*9*2 ), я заменю последнюю 2ку на нечетное число, то он преобразовывает правильно. А если четные, то неправильно. Это так же касается других операнд. При их замене на другие числа, алгоритм, то работает, то нет. Но я не прописывал зависимости выгрузки из стека от операнд. Есть добрые люди, которые могут пояснить: где тут собака зарыта?



Попробовал разные варианты. Проблема возникает под конец цикла, если между оператором одинаковые операнды. Алгоритм тогда не обрабатывает стек согласно приоритету. Если мы заменим наше выражение на более простое например 2+2*2 то он преобразует неправильно. Но если мы возьмем 2+2*n, где n любое число отличное от двойки все заработает. Если мы добавим операцию 2+2*2+3. То все тоже будет правильно. Добавим еще операцию 2+2*2+3*3. До 2+2*2 алгоритм работает правильно потом сбой неправильно распределяет операторы после. Вообщем какой-то бред и я не понимаю причину.

Отредактировано Python_newbie13 (Июнь 27, 2020 19:57:00)

Онлайн

#2 Июнь 28, 2020 18:07:29

Python_newbie13
Зарегистрирован: 2020-06-27
Сообщения: 13
Репутация: +  0  -
Профиль   Отправить e-mail  

Польская нотация.

Нашел ошибку.

 if i is list[-1]:
Данная строка проверяет должна проверять, что это последний элемент. Но одинаковые строки в списке это один и тот же обьект. Отюсда и проблема.

Онлайн

#3 Июнь 28, 2020 19:18:54

Python_newbie13
Зарегистрирован: 2020-06-27
Сообщения: 13
Репутация: +  0  -
Профиль   Отправить e-mail  

Польская нотация.

Возникает вопрос. Как проверить, что это последний элемент списка? Я использую переменную счетчик

  for i in list:
        n = n + 1
        if n == len(list):
            do smth 
 
Есть ли боле pythonic решения?

Отредактировано Python_newbie13 (Июнь 28, 2020 19:19:43)

Онлайн

#4 Июнь 29, 2020 00:12:48

py.user.next
От:
Зарегистрирован: 2010-04-29
Сообщения: 6981
Репутация: +  633  -
Профиль   Отправить e-mail  

Польская нотация.

Python_newbie13
Есть ли боле pythonic решения?
Тут нужно не в pythonic смотреть, а в алгоритм. Проверить, является ли взятый элемент последним, можно по той структуре данных, из которой он берётся. Соответственно, тебе нужно поместить элементы в очередь и брать из неё по элементу. Когда взятый элемент окажется последним, очередь станет пустой и это можно будет проверить.

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

Пример проверки на последний элемент, где список используется как очередь
  
>>> queue = [1, 2, 3, 4, 5]
>>> 
>>> while queue:
...     e = queue.pop(0)
...     print('See element:', e)
...     if not queue:
...         print('See last element:', e)
... 
See element: 1
See element: 2
See element: 3
See element: 4
See element: 5
See last element: 5
>>>

Думаю, тебе надо освоить pdb (дебаггер для питона)
https://docs.python.org/3/library/pdb.html
так как твой алгоритм настолько запутан, что вряд ли ты знаешь, как он работает на самом деле. В дебаггере тебя ждёт много сюрпризов, так как при просвечивании переменных на каждом шаге ты увидишь, что всё работает совсем не так, как ты планировал и как тебе казалось.

В частности, при вставке print'а в функцию priority() видно, что она не срабатывает ни разу для выражений
'1*1*1*1'
'1+1+1+1'
'1+1*1+1'
При этом при обработке выражения
'1+1+1'
всё раскладывается правильно, только функция priority() всё равно не срабатывает.

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



Отредактировано py.user.next (Июнь 29, 2020 00:22:13)

Офлайн

#5 Июнь 29, 2020 02:42:51

Python_newbie13
Зарегистрирован: 2020-06-27
Сообщения: 13
Репутация: +  0  -
Профиль   Отправить e-mail  

Польская нотация.

Спасибо за совет про дебагер. Будет полезно на будущее. Используя его, я бы разобрался намного быстрее. Проверка с помощью очереди тоже лучше, чем мой вариант через переменную счетчик.

После того, как я добавил в алгоритм скобки он стал еще сложнее, но сейчас все работает, как надо.

Отредактировано Python_newbie13 (Июнь 29, 2020 03:35:08)

Онлайн

Board footer

Модераторировать

Powered by DjangoBB

Lo-Fi Version