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

Перевод в обратную польскую нотацию на Python после рефакторинга

Запись от Konst2016 размещена 28.04.2019 в 14:36

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

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

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
def op_prior(str_char_op):
    """
        Приоритет арифметической операции
    """
 
    if str_char_op=="^":
 
        return 6
    elif str_char_op=="*":
 
        return 5
    elif str_char_op=="/":
 
        return 5
    elif str_char_op=="%":
 
        return 3
    elif str_char_op=="+":
 
        return 2
    elif str_char_op=="-":
 
        return 2
 
def isOp(c):
    """
        Это арифметическая операция?
    """
 
    if c=="-" or c=="+" or c=="*" or c=="/" or c=="%"or c=="^" :return True
    return False
 
isa = isinstance
import re
def opn(exp):
    """
        Перевод в обратную польскую запись
        @param exp строка инфиксного выражения type str
        @return список  постфиксного выражения  type list
    """
 
    item_i=0
 
    # Операндовый стек
    OperatStack=[]
    # Выходной список
    resOpn=[]
 
    while (item_i<len(exp)):
       
        elem=exp[item_i]
        item_i+=1
        # определить тип члена
        if re.match("[0-9]+",elem):
            assert (re.match("[0-9]+",elem)!= None)
 
            resOpn.append(elem)
        
        elif  re.match("[A-Za-z]+",str(elem)):
            assert isa(elem,str)
 
            resOpn.append(elem)
 
        elif isOp(elem):
                
                isOperatorStackNotEmpty = len(OperatStack)>0
 
                if isOperatorStackNotEmpty:
 
                    haveNoBracketOnTop = OperatStack[-1]!='('
                    isCurrentOpPrioritetLessOpPrioritetOnTop = op_prior(elem)<=op_prior(OperatStack[-1])
 
                while(isOperatorStackNotEmpty and  haveNoBracketOnTop and isCurrentOpPrioritetLessOpPrioritetOnTop ):
                    """
                        Добавляем оператор в выходную строку(список)
                    """
                    resOpn.append(OperatStack.pop())
 
                    isOperatorStackNotEmpty = len(OperatStack)>0
 
                    if isOperatorStackNotEmpty:
                        isOperatorStackNotEmpty = len(OperatStack)>0
                        haveNoBracketOnTop = OperatStack[-1]!='('
                        isCurrentOpPrioritetLessOpPrioritetOnTop = op_prior(elem)<=op_prior(OperatStack[-1])
 
                OperatStack.append(elem)
        elif elem==')':
            
            
            isOperatStackNotEmpty = len(OperatStack)>0
            while isOperatStackNotEmpty:
 
                x=OperatStack.pop()
                if x=='(':
 
                    break
                resOpn.append(x)
                
                isOperatStackNotEmpty = len(OperatStack)>0  
 
        elif elem=="(":
            OperatStack.append(elem)
 
    isOperatStackNotEmpty = len(OperatStack)>0
    while isOperatStackNotEmpty :
 
           resOpn.append(OperatStack.pop())
          
           isOperatStackNotEmpty = len(OperatStack)>0
 
    return resOpn
 
def test():
  print(opn("1+2"))
  print(opn("1+2*3"))
  
  print(opn("(3+3)/7")) 
 
  print(opn("3^6/8"))
 
  print(opn("3%3*8+(5+6)"))
 
 
if __name__=="__main__":
  test()
Bash
1
2
3
4
5
['1', '2', '+']
['1', '2', '3', '*', '+']
['3', '3', '+', '7', '/']
['3', '6', '^', '8', '/']
['3', '3', '8', '*', '%', '5', '+', '6', '+']
Размещено в Без категории
Просмотров 156 Комментарии 2
Всего комментариев 2
Комментарии
  1. Старый комментарий
    Что-то я не совсем понял для чего всё это нужно. Если необходимо вычислить арифметическое выражение, то наверное проще будет так.
    1. заключаем всё выражение в круглые скобки (для использования рекурсии)
    2. извлекаем все числа в массив, оставляя в строке индексы массива этих чисел, чтобы знать их местонахождение (однозначные индексы типа 0 лучше записать так 00)
    3. обозначение функций можно тоже сократить (например sin на s)
    4. кроме всего прочего обязательно следует переобозначить унарный минус (во избежание проблем)
    5. и задать рекурсивную функцию (по числу пар скобок)
    6. если скобки кончились, то всё сосчитано.
    Запись от нтч размещена 29.04.2019 в 07:08 нтч вне форума
  2. Старый комментарий
    По моему то что вы описали делалось в Fortran.А это алгоритм Дейкстры называется сортировочная станция,потом выходной
    список можно подать в стековую машину для вычисления результата.
    Запись от Konst2016 размещена 29.04.2019 в 09:44 Konst2016 вне форума
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru