Обратная польская запись

@Junoir · Регистрация: 24.06.2019

Студворк — интернет-сервис помощи студентам

программа не переводит выражение в обратную польскую запись

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
list = input("Введите выражение -  ")
a = list
t = ['+', '-', '*', '/']
stroka = []
stek = []
c = 0
for i in a:
    if i == t[0]:
       stek.append(i)
       c += 1
    elif i == t[1]:
       stek.append(i)
       c += 1
    elif i == t[2]:
       stek.append(i)
       c += 1
    elif i == t[3]:
       stek.append(i)
       c += 1
    else : stroka.append(i)
    while c > 1: 
        for v in stek[1:]:
            for i in stek:
                if v == t[0] and i == t[0] or i == t[1] or i == t[2] or i == t[3]:
                    stroka.append(v)
                    stek.remove(i)
                    c -= 1
                elif v == t[1] and i == t[0] or i == t[1] or i == t[2] or i == t[3]:
                    stroka.append(v)
                    stek.remove(i)
                    c -= 1
                elif v == t[2] and i == t[3] or i == t[2]:
                    stroka.append(v)
                    stek.remove(i)
                    c -= 1
                elif v == t[3] and i == t[2] or i == t[3]:
                    stroka.append(v)
                    stek.remove(i)
                    c -= 1
                else : c = 0
                
print(stroka)
print(stek)

@Welemir1 · 01.10.2019, 18:10

Сообщение от Junoir

программа не переводит выражение в обратную польскую запись

а должна?
что нужно ввести и что получить на выходе? что получаем вместо этого?

@Junoir · 01.10.2019, 23:59 **[ТС]**

нужно ввести a+b*c+d
получить abc*+d+

@Welemir1 · 02.10.2019, 06:16

Junoir, трудно понять что ты вообще делаешь, учитывая твою нехватку знаний основ

Сообщение от Junoir

list = input("Введите выражение - *")

переменные нельзя называть как встроенные функции, сделай просто

Python
1
a = input("Введите выражение -  ")

Сообщение от Junoir

for i in a:
* * if i == t[0]:
* * * *stek.append(i)
* * * *c += 1
* * elif i == t[1]:
* * * *stek.append(i)
* * * *c += 1
* * elif i == t[2]:
* * * *stek.append(i)
* * * *c += 1
* * elif i == t[3]:
* * * *stek.append(i)
* * * *c += 1
* * else : stroka.append(i)

меняем на

Python
1
2
3
4
5
6
for i in a:
    if i in t:
       stek.append(i)
       c += 1    
    else : 
        stroka.append(i)

Сообщение от Junoir

if v == t[0] and i == t[0] or i == t[1] or i == t[2] or i == t[3]:

меняем на

Python
1
if v == t[0] and i in t:

уверен, что ты и в других местах намудрил, я просто не понимаю, почему ты в стеке с 1 элемента начинаешь перебор и что вообще делаешь.

@Junoir · 02.10.2019, 10:21 **[ТС]**

хочу сделать чтобы при вводе функции мне выводила обратную польскую запись

@Welemir1 · 02.10.2019, 10:27

Junoir, спасибо, Капитан Очевидность! стало яснее.

как конкретно ты этого хочешь добиться, каков твой алгоритм, зачем стек с 1 элемента перебираешь а не с начала?

@Junoir · 02.10.2019, 10:30 **[ТС]**

Я начинаю перебирать с первого элемента чтобы он сравнивал мне предыдущий элемент и 1

Добавлено через 28 секунд
Я просто не хочу импортировать другие библиотеки очистка алгоритмом написать обратную польскую запись, а у меня плохо получается

@Welemir1 · 02.10.2019, 11:23

Сообщение от Junoir

очистка алгоритмом написать обратную польскую запись

тебе русский не родной язык?

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

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
PRIORITY = {1: ['+', '-'], 2: ['*', '/']}
 
 
def priority(value: str) -> int:
    for k, v in PRIORITY.items():
        if value in v:
            return k
    return -1
 
 
def pol_notation(expr: str) -> str:
    result = []
    stack = []
    for element in expr:
        if element not in '+-*/':
            result.append(element)
        else:
            last = None if not stack else stack[-1]
            while priority(last) >= priority(element):
                result.append(stack.pop())
                last = None if not stack else stack[-1]
            stack.append(element)
    for e in reversed(stack):
        result.append(e)
    return ''.join(result)
 
 
assert pol_notation('a+b*c+d') == 'abc*+d+'
assert pol_notation('3+5') == '35+'
assert pol_notation('5*2+10') == '52*10+'

@Catstail · 02.10.2019, 18:17

Вот еще реализация ОПЗ для формул со скобками:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
def rpn(s):
    lex=parse(s)
    s2=[]
    r=[]
    oper=["+","-","*","/","(",")"]
    for a in lex:
        if a=="(":
            s2=[a]+s2
        elif a in oper:
            if s2==[]:
                s2=[a]
            elif a==")":
                while(True):
                    q=s2[0]
                    s2=s2[1:]
                    if q=="(":
                        break
                    r+=[q]
            elif prty(s2[0]) < prty(a):
                s2=[a]+s2
            else:
                while(True):
                    if s2==[]:
                        break
                    q=s2[0]
                    r+=[q]
                    s2=s2[1:]
                    if prty(q)==prty(a):
                        break
                s2=[a]+s2
        else:
            r+=[a]
    while(s2 != []):
        q=s2[0]
        r+=[q]
        s2=s2[1:]
    return r
 
def prty(o):
    if o=="+" or o=="-":
        return 1
    elif o=="*" or o=="/":
        return 2
    elif o=="(":
        return 0
 
def parse(s):
    delims=["+","-","*","/","(",")"]
    lex=[]
    tmp=""
    for a in s:
        if a != " ":
            if a in delims:
                if tmp != "":
                    lex+=[tmp]
                lex+=[a]
                tmp=""
            else:
                tmp+=a
    if tmp != "":
        lex+=[tmp]
    return lex
    
print(rpn("2+44*(56-12)/a-66"))

Вывод: ['2', '44', '56', '12', '-', '*', 'a', '/', '+', '66', '-']

https://ideone.com/Aje2dI

@Welemir1 · 02.10.2019, 18:26

Не по теме:

Catstail, ухх! Я за скобки даже боялся браться, уважаю!

@TazZerR · 23.07.2021, 06:57

Catstail, а что обозначают переменные в квадратных скобках? В коде это [a], [q] и [tmp]

@Catstail · 23.07.2021, 08:02

Сообщение от TazZerR

а что обозначают переменные в квадратных скобках?

- это не "переменные в скобках", а одноэлементные списки... Рекомендую ознакомиться

@TazZerR · 25.07.2021, 01:21

Извините, немного перед Вами неудобно, но не могли бы вы написать код для подсчета обратной польской записи? Спасибо.

@Catstail · 25.07.2021, 07:08

Перевод и вычисление:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
def rpn(s):
    lex=parse(s)
    s2=[]
    r=[]
    oper=["+","-","*","/","(",")"]
    for a in lex:
        if a=="(":
            s2=[a]+s2
        elif a in oper:
            if s2==[]:
                s2=[a]
            elif a==")":
                while(True):
                    q=s2[0]
                    s2=s2[1:]
                    if q=="(":
                        break
                    r+=[q]
            elif prty(s2[0]) < prty(a):
                s2=[a]+s2
            else:
                while(True):
                    if s2==[]:
                        break
                    q=s2[0]
                    r+=[q]
                    s2=s2[1:]
                    if prty(q)==prty(a):
                        break
                s2=[a]+s2
        else:
            r+=[a]
    while(s2 != []):
        q=s2[0]
        r+=[q]
        s2=s2[1:]
    return r
 
def prty(o):
    if o=="+" or o=="-":
        return 1
    elif o=="*" or o=="/":
        return 2
    elif o=="(":
        return 0
 
def parse(s):
    delims=["+","-","*","/","(",")"]
    lex=[]
    tmp=""
    for a in s:
        if a != " ":
            if a in delims:
                if tmp != "":
                    lex+=[tmp]
                lex+=[a]
                tmp=""
            else:
                tmp+=a
    if tmp != "":
        lex+=[tmp]
    return lex
    
def rpn_calc(formula):
    s=[]
    for lex in formula:
        if lex[0].isdigit():
            s.append(float(lex))
        else:
            a2=s.pop()
            a1=s.pop()
            if lex=='+':
                s.append(a1+a2)
            if lex=='-':
                s.append(a1-a2)
            if lex=='*':
                s.append(a1*a2)
            if lex=='/':
                s.append(a1/a2)
    return s.pop()            
 
print(rpn("2+44*(56-12)/8-66"))    
print(rpn_calc(rpn("2+44*(56-12)/8-66"))) 
print(eval("2+44*(56-12)/8-66"))

@Viktorrus · 26.07.2021, 13:05

Catstail, Не знал, что один элемент в списке можно указывать так. Лутц пишет, что в этом случае нужно использовать запятую.
Не помню, может он это говорит в качестве рекомендации, что бы не путать с индексацией?
Во всяком случае Вы показали, что можно и без запятой. Спасибо.

Python
1
2
3
4
5
6
7
>>> a = 1
>>> lst1 = [a]
>>> lst1
[1]
>>> lst = [a,]
>>> lst
[1]

@Arsegg · 26.07.2021, 14:19

Сообщение от Viktorrus

Лутц пишет, что в этом случае нужно использовать запятую.

Полагаю, это для tuple:

Python
1
2
3
4
5
In [1]: type((1337,))
Out[1]: tuple
 
In [2]: type((1337))
Out[2]: int

P. S. А можно вообще без скобок (круглых, квадратных):

Python
1
2
3
value = 1337
singleton = value,
assert type(singleton) == tuple

@Viktorrus · 26.07.2021, 19:08

Сообщение от Arsegg

Полагаю, это для tuple

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

Python
1
2
3
4
5
6
7
8
>>> a = 1
>>> b = (a)
>>> b
>>> 
1
>>> c = (a,)
>>> c
(1,)

Да так и есть. Я видимо перепутал кортеж со списком.
Но как я показал выше, список из одного элемента тоже можно с запятой. Для меня по крайней мере с запятой нагляднее.

@alilxxey · 04.04.2022, 22:11

Catstail, (((12-7)*15-1)/2+35)*6/13

Добавлено через 5 часов 41 минуту
Довел до ума преобразование инфиксной(обычной математической) в постфиксную(обратную польскую) форму

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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 conv(expr):
    prec = {'*': 3, '/': 3, '+': 2, '-': 2, '(': 1}
    a = Stack()
    pl = []
    tl = expr.split()
 
    for t in tl:
        if t.isdigit():
            pl.append(t)
        elif t == '(':
            a.push(t)
        elif t == ')':
            top = a.pop()
            while top != '(':
                pl.append(top)
                top = a.pop()
        else:
            while (not a.isempty()) and (prec[a.peek()] >= prec[t]):
                pl.append(a.pop())
            a.push(t)
    while not a.isempty():
        pl.append(a.pop())
    return " ".join(pl)

Добавлено через 12 минут
Catstail, у Вас как я понял с вложенностью скобок где то ошибка. Пытался разобраться в Вашем коде, но решил сделать все заново, вроде как у меня универсальный пример (до универсальности только общий вид, но для этого нужно просто дописать допущение в 25 строке)

@Catstail · 05.04.2022, 08:16

alilxxey, да, была ошибочка...

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
def rpn(s):
    lex=parse(s)
    s2=[]
    r=[]
    oper=["+","-","*","/","(",")"]
    for a in lex:
        if a=="(":
            s2=[a]+s2
        elif a in oper:
            if s2==[]:
                s2=[a]
            elif a==")":
                while(True):
                    q=s2[0]
                    s2=s2[1:]
                    if q=="(":
                        break
                    r+=[q]
            elif prty(s2[0]) < prty(a):
                s2=[a]+s2
            else:
                while(True):
                    if s2==[]:
                        break
                    q=s2[0]                     # вот здесь !
                    if prty(q)<prty(a):
                        break
                    r+=[q]
                    s2=s2[1:]
                s2=[a]+s2
        else:
            r+=[a]
    while(s2 != []):
        q=s2[0]
        r+=[q]
        s2=s2[1:]
    return r
 
def prty(o):
    if o=="+" or o=="-":
        return 1
    elif o=="*" or o=="/":
        return 2
    elif o=="(":
        return 0
 
def parse(s):
    delims=["+","-","*","/","(",")"]
    lex=[]
    tmp=""
    for a in s:
        if a != " ":
            if a in delims:
                if tmp != "":
                    lex+=[tmp]
                lex+=[a]
                tmp=""
            else:
                tmp+=a
    if tmp != "":
        lex+=[tmp]
    return lex
    
def rpn_calc(formula):
    s=[]
    for lex in formula:
        if lex[0].isdigit():
            s.append(float(lex))
        else:
            a2=s.pop()
            a1=s.pop()
            if lex=='+':
                s.append(a1+a2)
            if lex=='-':
                s.append(a1-a2)
            if lex=='*':
                s.append(a1*a2)
            if lex=='/':
                s.append(a1/a2)
    return s.pop()            
 
print(rpn("(((12-7)*15-1)/2+35)*6/13"))    
print(rpn_calc(rpn("(((12-7)*15-1)/2+35)*6/13"))) 
print(eval("(((12-7)*15-1)/2+35)*6/13"))
 
print(rpn("2+44*(56-12)/8-66"))    
print(rpn_calc(rpn("2+44*(56-12)/8-66"))) 
print(eval("2+44*(56-12)/8-66"))

Вывод:

['12', '7', '-', '15', '*', '1', '-', '2', '/', '35', '+', '6', '*', '13', '/']
33.23076923076923
33.23076923076923
['2', '44', '56', '12', '-', '*', '8', '/', '+', '66', '-']
178.0
178.0

@VistaSV30 · 25.04.2022, 21:00

Имеет ли смысл, для ускорения вычислений использовать принцип ОПЗ применительно к выражениям в обычной (инфиксной) записи?
Например, не использовать скобки. Возможно запись выражения будет длиннее, но зато выражение будет выполняться за один проход.

Время выполнения: 0.39083 с

Python
1
2
3
4
5
6
import time
 
start_time = time.time()
for i in range(10000000):
    (1+2) * (3+4) +5
print("--- %s seconds ---" % (time.time() - start_time))

Время выполнения: 0.38996 с

Python
1
2
3
4
start_time = time.time()
for i in range(10000000):
    1*3 + 2*3 + 1*4 + 2*4 + 5
print("--- %s seconds ---" % (time.time() - start_time))

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11680&d=1772460536 Одним из. . .	Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .

Обратная польская запись

Решение

Решение

Решение

@Junoir 0 / 0 / 0 Регистрация: 24.06.2019 Сообщений: 7
	01.10.2019, 23:59 [ТС]
	нужно ввести a+bc+d получить abc+d+ 0

@Junoir 0 / 0 / 0 Регистрация: 24.06.2019 Сообщений: 7
	02.10.2019, 10:21 [ТС]
	хочу сделать чтобы при вводе функции мне выводила обратную польскую запись 0

@Welemir1 Автоматизируй это! 7391 / 4818 / 1246 Регистрация: 30.03.2015 Сообщений: 13,693 Записей в блоге: 29
	02.10.2019, 10:27
	Junoir, спасибо, Капитан Очевидность! стало яснее. как конкретно ты этого хочешь добиться, каков твой алгоритм, зачем стек с 1 элемента перебираешь а не с начала? 0

@Junoir 0 / 0 / 0 Регистрация: 24.06.2019 Сообщений: 7
	02.10.2019, 10:30 [ТС]
	Я начинаю перебирать с первого элемента чтобы он сравнивал мне предыдущий элемент и 1 Добавлено через 28 секунд Я просто не хочу импортировать другие библиотеки очистка алгоритмом написать обратную польскую запись, а у меня плохо получается 0

@Welemir1
	02.10.2019, 18:26
	Не по теме: Catstail, ухх! Я за скобки даже боялся браться, уважаю! 0

@TazZerR 0 / 0 / 0 Регистрация: 04.11.2019 Сообщений: 22
	23.07.2021, 06:57
	Catstail, а что обозначают переменные в квадратных скобках? В коде это [a], [q] и [tmp] 0

@TazZerR 0 / 0 / 0 Регистрация: 04.11.2019 Сообщений: 22
	25.07.2021, 01:21
	Извините, немного перед Вами неудобно, но не могли бы вы написать код для подсчета обратной польской записи? Спасибо. 0