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

стек

Стек у 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 ) ) ). 

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

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

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

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

Перевірка задачі онлайн 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

Перевірка задачі онлайн: 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])

Остання зміна: четвер 26 вересня 2019 7:55