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

@WLRA · Регистрация: 24.11.2020

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

Такой тип записи арифметических выражений позволяет однозначно определять последовательность действий, не используя скобки. При такой записи (постфиксная форма) выражения вычисляются слева направо. Алгоритм такой.

Идем по строке, пока не встретим арифметический оператор. Берем два расположенных перед ним числа (операнда) и производим с ними действие, которое записано в этом операторе. Порядок операндов не меняем. Полученное число записываем в строку вместо этих трех элементов – двух операндов и арифметического оператора. Повторяем действия, пока в строке не останется только одно число – это и есть результат вычислений.

Напишите класс RPN (Reverse Polish Notation) для составления и вычисления арифметического выражения, записанного в обратной польской нотации. Класс инициализируется с аргументом – строкой, в которой записано арифметическое выражение, которое может содержать числа, знаки арифметических операций (+-*/) и круглые скобки, составленное по правилам математики; все числа и знаки разделены пробелами. Если это выражение не преобразовано к обратной польской записи, то при вызове метода вычислений, нужно его сначала преобразовать, и только потом вычислять.

Класс реализует методы:

check() – проверяет переданную при инициализации строку; если она записана в постфиксной форме, то возвращает False, то есть преобразование не требуется; иначе возвращает True.
postfix() – преобразует строку, переданную экземпляру класса при инициализации, к обратной польской записи; возвращает выражение в постфиксной форме.
calculate() – вычисляет значение выражения, переданного экземпляру класса при инициализации; если выражение записано не в постфиксной форме, сначала его нужно к ней преобразовать; возвращает число – результат вычислений. Поскольку среди операций присутствует деление, на всякий случай всегда результат возвращаем в вещественном виде.

Пример 1
Ввод Вывод

Python
1
2
3
4
rpn = RPN("( ( 9 - ( 5 + 2 ) ) * 3 ) * ( 1 + 7 )")
print(rpn.check())
print(rpn.postfix())
print(rpn.calculate())

True
9 5 2 + - 3 * 1 7 + *
48.0
Пример 2
Ввод Вывод

Python
1
2
3
4
rpn = RPN("16 7 2 - 8 * + 8 /")
print(rpn.check())
print(rpn.postfix())
print(rpn.calculate())

False
16 7 2 - 8 * + 8 /
7.0

@idealist · 13.03.2022, 10:28

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
class RPN:
    # ==========================================================================
    def is_op(symb):
        return symb in '+-*/'
    # ==========================================================================
    def prior( op ):
        match op:
            case '*' | '/':
                return 2
            case '+' | '-':
                return 1
    # ==========================================================================
    def __init__(self, expr):
        self.expr_lis = expr.split()
    #==========================================================================
    def check(self):
        return not RPN.is_op( self.expr_lis[-1] )
    # ==========================================================================
    def postfix(self):
        if self.check():
            try:
                out = []
                st  = []
                for symb in self.expr_lis:
                    if symb.isdigit():
                        out.append( symb )
                    elif symb == '(':
                        st.append( symb )
                    elif symb == ')':
                        if not st:
                            raise ValueError
                        while st and st[-1] != '(':
                            out.append( st.pop() )
                            if not st:
                                raise ValueError
                        st.pop()
                    elif RPN.is_op( symb ):
                        while st and RPN.is_op( st[-1] ) and RPN.prior( st[-1] ) >= RPN.prior( symb ):
                            out.append( st.pop() )
                        st.append( symb )
                while st:
                    out.append( st.pop() )
                return out
            except ValueError:
                print( 'Задано некорректное выражение.' )
        else:
            return self.expr_lis
    # ==========================================================================
    def calculate(self):
        self.expr_lis = self.postfix()
        st = []
        try:
            for symb in self.expr_lis:
                if symb.isdigit():
                    st.append( symb )
                elif RPN.is_op( symb ):
                    if not st:
                        raise ValueError
                    b = int( st.pop() )
                    if not st:
                        raise ValueError
                    a = int( st.pop() )
                    match symb:
                        case '+':
                            st.append( str(a + b) )
                        case '-':
                            st.append( str(a - b) )
                        case '*':
                            st.append( str(a * b) )
                        case '/':
                            st.append( str(a / b) )
            if len(st) != 1:
                raise ValueError
            return float( st.pop() )
        except ValueError:
            print( 'Задано некорректное выражение.' )
# =============================================================================
rpn = RPN("( ( 9 - ( 5 + 2 ) ) * 3 ) * ( 1 + 7 )")
print( rpn.check() )
print( rpn.postfix() )
print( rpn.calculate() )

@WLRA · 13.03.2022, 13:01 **[ТС]**

stdout:
/bin/sh ./build.sh 1>&2
Makefile:2: recipe for target 'build' failed

stderr:
./solution.py:7:15: E999 SyntaxError: invalid syntax
Код не соответствует стандарту PEP8
или в нем есть синтаксические ошибки
make: *** [build] Error 1

@idealist · 13.03.2022, 14:07

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

stdout:
/bin/sh ./build.sh 1>&2
Makefile:2: recipe for target 'build' failed
stderr:
./solution.py:7:15: E999 SyntaxError: invalid syntax
Код не соответствует стандарту PEP8
или в нем есть синтаксические ошибки
make: *** [build] Error 1

А, это наверно из-за этого:
В Python 3.10 введена новая конструкция match/case
А у вас версия наверно ниже десятой?

@WLRA · 13.03.2022, 15:21 **[ТС]**

может быть компиллятор в системе LMS не поддерживает 10 версию

@Arseniy_Ch · 22.02.2023, 22: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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
oper = {"+": 1, "-": 1, "*": 2, "/": 2}
 
 
def fflag(data):
 
    for i in range(len(data) - 1):
        if data[i].isdigit() and data[i + 1].isdigit():
            return False
        return True
 
 
def perevod(data):
    out, stek = [], []
    for i in range(len(data)):
        if data[i].isdigit():
            out.append(data[i])
        if data[i] == "(":
            stek.append(data[i])
        if data[i] == ")":
            for j in range(len(stek) - 1, -1, -1):
                if stek[j] == "(":
                    stek.pop()
                    break
                else:
                    out.append(stek.pop())
        if data[i] in oper:
            while stek != []:
                if stek[-1] != "(" and oper[data[i]] <= oper[stek[-1]]:
                    out.append(stek.pop())
                else:
                    break
            stek.append(data[i])
    return out + stek[::-1]
 
 
class RPN:
    def __init__(self, string):
        self.string = string.split()
 
    def check(self):
        return fflag(self.string)
 
    def postfix(self):
        if not fflag(self.string):
            return " ".join(self.string)
        return " ".join(perevod(self.string))
 
    def calculate(self):
        if fflag(self.string):
            self.string = perevod(self.string)
        string = self.string
        while len(string) != 1:
            for i in range(2, len(string)):
                if string[i] in oper:
                    string[i] = eval(
                        str(string[i - 2]) + str(string[i]) +
                        str(string[i - 1]))
                    del string[i - 2:i]
                    break
        return float(string[0])

Оно работает

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств 8Observer8 07.02.2026 Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .	SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .
SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .

@WLRA 0 / 1 / 0 Регистрация: 24.11.2020 Сообщений: 138
	13.03.2022, 13:01 [ТС]
	stdout: /bin/sh ./build.sh 1>&2 Makefile:2: recipe for target 'build' failed stderr: ./solution.py:7:15: E999 SyntaxError: invalid syntax Код не соответствует стандарту PEP8 или в нем есть синтаксические ошибки make: *** [build] Error 1 0

@WLRA 0 / 1 / 0 Регистрация: 24.11.2020 Сообщений: 138
	13.03.2022, 15:21 [ТС]
	может быть компиллятор в системе LMS не поддерживает 10 версию 0