-
Notifications
You must be signed in to change notification settings - Fork 49
/
polsk_calc.py
81 lines (61 loc) · 3.79 KB
/
polsk_calc.py
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
"""
ПРИНЦИП РАБОТЫ
Для вычисления значения выражения, записанного в обратной польской нотации,
нужно считывать выражение слева направо и придерживаться следующих шагов:
- Обработка входного символа:
- - Если на вход подан операнд, он помещается на вершину стека.
- - Если на вход подан знак операции, то эта операция выполняется над требуемым количеством значений,
взятых из стека в порядке добавления. Результат выполненной операции помещается на вершину стека.
- Если входной набор символов обработан не полностью, перейти к шагу 1.
- После полной обработки входного набора символов результат вычисления выражения находится в вершине стека.
ДОКАЗАТЕЛЬСТВО КОРРЕКТНОСТИ
Стек (англ. stack - стопка) - одна из простейших структур данных,
представляющая собой скорее ограничение простого массива, чем его расширение.
Классический стек поддерживает всего лишь три операции:
- Добавить элемент в стек;
- Извлечь элемент из стека;
- Проверить, пуст ли стек.
Для объяснения принципа работы стека часто используется аналогия со стаканом с печеньем.
Представьте, что на дне вашего стакана лежат несколько кусков печенья.
Вы можете положить наверх ещё один кусок или достать уже находящийся наверху.
Остальные куски закрыты верхним, и вы про них ничего не знаете.
Для описания стека часто используется аббревиатура LIFO (Last In, First Out),
подчёркивающая, что элемент, попавший в стек последним, первым будет из него извлечён.
Статья - https://brestprog.by/topics/datastructures/.
ВРЕМЕННАЯ СЛОЖНОСТЬ
Добавление в стек стоит O(1).
Извлечение из стека стоит O(1).
Проверить, пуст ли стек стоит O(1).
ПРОСТРАНСТВЕННАЯ СЛОЖНОСТЬ
Стек, содержащий k элементов, занимает O(k) памяти.
"""
OPERATIONS = {
'+': lambda x, y: x + y,
'-': lambda x, y: y - x,
'*': lambda x, y: x * y,
'/': lambda x, y: y // x
}
class NoItemsException(Exception):
def __init__(self):
pass
class Stack:
def __init__(self):
self._array = []
self._size = 0
@property
def is_empty(self):
return self._size == 0
def push(self, element):
self._size += 1
self._array.append(element)
def pop(self):
if self.is_empty:
raise NoItemsException
else:
self._size -= 1
return self._array.pop()
stack = Stack()
for value in input().split(' '):
operation = OPERATIONS.get(value)
stack.push(operation(stack.pop(), stack.pop()) if operation else int(value))
print(stack.pop())