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