Структури даних. Стек

Стек у Python реалізований за допомогою списку. У даному прикладі зміст зчитується з файлу, назва якого задана у командному рядку при запуску програми. Зчитаний рядок розділяється на окремі слова, з розбиттям за пробілами, вилучаючи слово, зустрівши символи (-).

to be or - - not - - to - be

import sys
a=sys.argv[1]
stek=[]
text=open(a,'r')
message = text.read()
for slovo in message.split():
    if slovo!='-':
        stek.append(slovo)
    else:
        stek.pop()
print(stek)

Розглянемо покрокову роботу програми, задаючи значення змінної message безпосередньо у коді link

Задача 1. Перевірка правильності розстановки дужок одного типу ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ). 

Підказка: зчитаний рядок потрібно переглядати посимвольно.

##створити порожній список
##змінній-показнику читання з порожнього стеку присвоїти значення False
##для кожного символу змісту рядка файлу
##     якщо символ є (, то додати його у стек
##     інакше якщо символ є ), то 
##         якщо стек не порожній, то видалити з нього символ
##         інакше змінити показник на True та вийти з циклу break
## якщо показник true або стек не порожній (залишились дужки):
##    надрукувати Ні
## інакше:
##    надрукувати Так

Показати алгоритм

Тестові дані до задачі 1

1	(((A)*(B-C)-D)/2)		так
2	(A+B*(C-D)			ні
3	X-((A-B)*C)+(D/(E+F))/Y		так
4	A-(X/(B*C)+D/(E+F))		так
5	(D+(F-(A-B)*C)+D/(E+F)))(	ні
6	)((A-B)*C)+(D/(E+F)))		ні
7	D+(F-(A-B)/F+(K))*C+(D/(E+F)	ні	
8	D+(F-(A-B/F)+K)*C)/D/(E+F)	ні	
9	(A+(C+B))/(K-D)*(B+F)/(A+B*C)	так
10 	(A+B*(C-D))			так

Показати дані

Задача 2. Перевірка правильності розстановки дужок різних типів ( [ ) ] - помилка

При записуванні у стек потрібно враховувати всі типи відкриваючих дужок.
При видаленні зі стеку - можна видаляти лише дужку такого ж типу, як остання записана. Інакше - помилка

Показати підказку

Тестові дані до задачі 2

1	(((A)*[B-C]-D)/2)		так
2	(A-(B*[(C+D)-E])/F))		ні
3	([()[]()])()			        так
4	([([]()]))()			        ні
5	([([]())])()			        так

Показати дані

Перевірка задачі онлайн https://www.e-olymp.com/uk/problems/2479

Задача 3. Постфіксний запис виразу означає, що спочатку записуються операнди (числа), а потім оператори (арифметичні знаки), які потрібно застосувати до цих чисел. Наприклад, вираз a+b*c записується як a b c * +,  а вираз (a+b)*(z+x) записується як a b + z x + *

Вхідними даними програми є рядок з виразом у постфіксному записі. Вивести значення виразу, або слово ERROR, якщо у записі є помилка.

Для всіх символів робимо наступне:
Якщо зчитуємо число, то вкласти його у стек;
Якщо зчитуємо оператор, то:
Витягуємо із стеку два числа;
Виконуємо дію із числами і результат вкладаємо в стек.
В кінці роботи в стеку знаходитиметься результат виразу.

Алгоритм обчислення значення виразу

Тестові дані до задачі 3

5 15 + 4 7 + 1 - /
2
5 15 + 4 7 + 1 -
ERROR
12 2 3 4 * 10 5 / + * +
40
5 6 + 8 * 2 9 - -
95

Показати тести

Перевірка задачі онлайн: https://www.e-olymp.com/uk/problems/1586

Задача 4. Дано слово. Записати його зі зворотнім порядком літер

Додаткове завдання: визначати номер помилкового символу рядка у задачах 1-3

import sys
a=sys.argv[1]
text=open(a,'r')
for message in text:
    stek=[]
    pok=False
    for slovo in message:
        if (slovo=='(') or (slovo=='['):
            stek.append(slovo)
        elif slovo==')':
            if len(stek)>0:
                k=stek.pop()
                if k!='(':
                    pok=True 
                    break
            else:
                pok=True 
                break
        elif slovo==']':
            if len(stek)>0:
                k=stek.pop()
                if k!='[':
                    pok=True 
                    break
            else:
                pok=True 
                break
    if (len(stek)>0) or (pok==True):
        print("No")
    else:
        print("Yes")
=========================
line=input().split()
stek=[]
znaky=['+','-','*','/']
pok=False
for slovo in line:
    if slovo not in znaky:
        stek.append(int(slovo))
    else:
        if len(stek)>0:
            a=stek.pop()
            if len(stek)>0:
                b=stek.pop()
            else:
                pok=True
                break
        else:
            pok=True
            break
        if slovo=="+":
            rezult=a+b
        if slovo=="-":
            rezult=b-a            
        if slovo=="*":
            rezult=a*b
        if slovo=="/":
            rezult=b//a
        stek.append(rezult)
if (len(stek)>1) or (pok==True):
    print("ERROR")
else:
    print(stek[0])