ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 13.03.2024
Просмотров: 5
Скачиваний: 0
Федеральное агентство связи
Ордена Трудового Красного Знамени
Федеральное государственное бюджетное образовательное учреждение высшего образования
«Московский технический университет связи и информатики»
Кафедра Математической Кибернетики и Информационных Технологий
Отчет по лабораторной работе
по предмету «СиАОД»
на тему:
«Стек, очередь и дек»
Выполнил: студент группы УБСТ2204
Становов Роман Андреевич
Руководитель:
Кутейников Иван Алексеевич
Москва 2021
Цель работы
Используя технологию модульного программирования разработать программу обработки данных, содержащихся в заранее подготовленном файле, в соответствии с индивидуальным заданием. Применить динамическую структуру указанного в задании вида: стек, очередь или дек. Программа должна включать модуль, содержащий набор всех необходимых средств (типов, подпрограмм и т.д.) для решения поставленной задачи.
Вариант 19
В текстовом файле хранится выражение, записанное в инфиксной форме. Используя стек, перевести его в постфиксную форму и в таком виде записать в новый текстовый файл.
Пример выражения: a + b / c / d * e => a b c / d / e * +
Выполнение
Реализация cтека на языке программирования python.
class Stack:
def __init__(self): #__init__: Инициализация стека.
self.items = []
def is_empty(self): #is_empty: Проверка, пуст ли стек.
return len(self.items) == 0
def push(self, item): #push: Добавление элемента в стек
self.items.append(item)
def pop(self): #pop: Извлечение элемента из стека.
if not self.is_empty():
return self.items.pop()
def peek(self): #peek: Получение верхнего элемента стека без извлечения.
if not self.is_empty():
return self.items[-1]
def precedence(self, op): #precedence: Определение приоритета операторов для использования при преобразовании инфиксного выражения в постфиксное.
if op == '+' or op == '-':
return 1
elif op == '*' or op == '/':
return 2
return 0
Код программы
import os
import sys
class Stack:
def __init__(self):
self.items = []
def is_empty(self):
return len(self.items) == 0
def push(self, item):
self.items.append(item)
def pop(self):
if not self.is_empty():
return self.items.pop()
def peek(self):
if not self.is_empty():
return self.items[-1]
def precedence(self, op):
if op == '+' or op == '-':
return 1
elif op == '*' or op == '/':
return 2
return 0
def infix_to_postfix(infix_expression):
stack = Stack()
postfix_expression = []
operators = "+-*/"
for symbol in infix_expression:
if symbol.isalnum() or '.' in symbol:
postfix_expression.append(symbol)
elif symbol in operators:
while (not stack.is_empty() and
stack.precedence(stack.peek()) >= stack.precedence(symbol)):
postfix_expression.append(stack.pop())
stack.push(symbol)
elif symbol == '(':
stack.push(symbol)
elif symbol == ')':
while not stack.is_empty() and stack.peek() != '(':
postfix_expression.append(stack.pop())
stack.pop()
while not stack.is_empty():
postfix_expression.append(stack.pop())
return "".join(postfix_expression)
def evaluate_postfix(postfix_expression, variables):
stack = Stack()
operators = "+-*/"
for symbol in postfix_expression:
if symbol.isalnum() or '.' in symbol:
stack.push(symbol)
elif symbol in operators:
operand2 = stack.pop()
operand1 = stack.pop()
result = perform_operation(operand1, operand2, symbol, variables)
stack.push(str(result))
return stack.pop()
def perform_operation(operand1, operand2, operator, variables):
operand1_value = get_operand_value(operand1, variables)
operand2_value = get_operand_value(operand2, variables)
if operator == '+':
return operand1_value + operand2_value
elif operator == '-':
return operand1_value - operand2_value
elif operator == '*':
return operand1_value * operand2_value
elif operator == '/':
if operand2_value != 0:
return operand1_value / operand2_value
else:
print(f"Ошибка: деление на ноль при операции {operand1} / {operand2}.")
sys.exit(1)
def get_operand_value(operand, variables):
try:
return float(operand)
except ValueError:
if operand in variables:
return variables[operand]
else:
print(f"Ошибка: переменная {operand} не определена.")
sys.exit(1)
def restart_script():
python = sys.executable
os.execl(python, python, *sys.argv)
def main():
while True:
variables = {}
infix_expression = input("Введите инфиксное выражение: ")
# Предварительное определение переменных
var_definition = input("Введите определение переменных (например, a=2 b=3): ")
for definition in var_definition.split():
var, value = definition.split('=')
variables[var] = float(value)
postfix_expression = infix_to_postfix(infix_expression)
with open("output.txt", "w") as file:
file.write(postfix_expression)
print("Постфиксная форма: ", postfix_expression)
result = evaluate_postfix(postfix_expression, variables)
print("Результат вычисления: ", result)
choice = input("Хотите ввести новое выражение? (yes/no): ")
if choice.lower() != 'yes':
break
else:
choice_restart = input("Хотите перезапустить программу? (yes/no): ")
if choice_restart.lower() != 'yes':
break
else:
restart_script()
if __name__ == "__main__":
main()
Результаты работы
Выходные данные в файле output.txt
Результат работы:
Вывод
Я изучил структуру данных стек и понял, как ее реализовать. Данная структура данных является очередью. Таким образом, она позволяет довольно просто реализовать добавление и удаление элементов, которые в свою очередь добавляются поверх остальных, и удаляются, начиная с последнего добавленного.