Форум программистов, компьютерный форум, киберфорум
Наши страницы
Konst2016
Войти
Регистрация
Восстановить пароль
Оценить эту запись

Преобразование из инфиксной нотации в постфиксную нотацию-реализация Python

Запись от Konst2016 размещена 13.07.2018 в 00:00

Обра́тная по́льская запись (ОПЗ) — форма записи математических и логических выражений, в которой операнды расположены перед знаками операций.
Также именуется как обратная польская запись,
обратная бесскобочная запись (ОБЗ), постфиксная нотация, бесскобочная символика Лукасевича, польская инверсная запись, ПОЛИЗ.
Стековой машиной называется алгоритм, проводящий вычисления по обратной польской записи.
Алгоритм
(Префиксный-перед,инфиксный-между,посфиксный-после)

Пока есть ещё символы для чтения:

Читаем очередной символ.
Если символ является числом или постфиксной функцией (например, ! — факториал), добавляем его к выходной строке.
Если символ является префиксной функцией (например, sin — синус), помещаем его в стек.
Если символ является открывающей скобкой, помещаем его в стек.
Если символ является закрывающей скобкой:

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

Если существуют разные виды скобок, появление непарной скобки также свидетельствует об ошибке. Если какие-то скобки одновременно являются функциями (например, [x] — целая часть), добавляем к выходной строке символ этой функции.

Если символ является бинарной операцией о1, тогда:

1) пока на вершине стека префиксная функция…

… ИЛИ операция на вершине стека приоритетнее o1
… ИЛИ операция на вершине стека левоассоциативная с приоритетом как у o1

… выталкиваем верхний элемент стека в выходную строку;

2) помещаем операцию o1 в стек.

Когда входная строка закончилась, выталкиваем все символы из стека в выходную строку. В стеке должны были остаться только символы операций; если это не так, значит в выражении не согласованы скобки.
Входную строку пишем с минимум одним пробелом.
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
import re#регулярные выражения
#Приоритет операций-символов
def op_prior(o):
    if o=='*' :
        return 4
    elif o=='/' :
        return 3
    elif o=='%' :
        return 2
    elif o=='+' :
        return 1
    elif o=='-' :
        return 1
def opn(expr):#входной параметр -инфиксная строка арифметического выражения
    co=[]#выходная строка
    op_steck=[]#стек операторов
    list_tokens=re.split('[ ]+',expr)#разбиваем в список по пробелам
    for i in list_tokens:#цикл по списку- i елемент число,() или знак операции
        if i.isdigit():#i-число
            co.append(int(i))#в стек  
        elif i in ['*','/','%','+','-']:#i -бинарная операция
            token_tmp=''#смотрим на вверх стека
            if len(op_steck)>0:
                token_tmp=op_steck[len(op_steck)-1]#смотрим на вверх стека
                while(len(op_steck)>0 and token_tmp!='('):#пока стек >0
                    if (op_prior(i)<=op_prior(token_tmp)):#сравнием приоритет токена в строке и приоритет операци  в стеке операций
                        co.append(op_steck.pop())#если в стеке операция выше,то выталкиваем его в выходную строку
                    else:#bиначе выходим из данного цикла
                        break     
            op_steck.append(i)#тогда выйдя из цикла,добавим операцию в стек
        elif i=='(':#открывающая (
            op_steck.append(i)#в стек 
        elif i==')':#закрывающая )
            token_tmp=op_steck[len(op_steck)-1]#смотрим на вверх стека
            while(token_tmp!='('):#пока не всретим открывающию скобку
                co.append(op_steck.pop())#выталкиваем операторы в выходную строку-раз мы работаем с группированием чисел-со скобками
                token_tmp=op_steck[len(op_steck)-1]#смотрим на вверх стека внутри цикла
                if len(op_steck)==0:
                    raise RuntimeError('V virajenii propushena (')                  
                if token_tmp=='(':
                    op_steck.pop()                        
                  
    while(len(op_steck)>0):#мы должны вытолкнуть оставшиеся операторы
        token_tmp=op_steck[len(op_steck)-1]
        co.append(op_steck.pop())
        if token_tmp=='(':
            raise RuntimeError('V virajenii propushena )')
    return co#вернем постфиксную запись
 
print(opn('57 * 6 + 35 * 5 + 2'))
#<--[57, 6, '*', 35, 5, '*', '+', 2, '+']
print(opn('( 45 + 45 ) / ( 180 - 90 )'))
#<--[45, 45, '+', 180, 90, '-', '/']
print(opn('( 45 + 45  / ( 180 - 90 )'))
#<--RuntimeError: V virajenii propushena )
Размещено в Без категории
Просмотров 142 Комментарии 0
Всего комментариев 0
Комментарии
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru