Информационные структуры

Размещено на http://allbest.ru/

Министерство образования и науки РФ

Федеральное Государственное Бюджетное Образовательное Учреждение Высшего Профессионального Образования

Тульский Государственный Университет

Лабораторная работа №1

по дисциплине Базы данных и экспертные системы

Информационные структуры

Выполнила студентка гр. 520291 Алешина А.Д.

Принял доцент каф. ПМиИ Смирнов О.И.

Тула 2012



1. Цель работы

Изучение методов машинно-ориентированной организации информации в сложных программных системах и приобретение навыков их использования при решении инженерных и экономических задач.

2. Задание

Вариант 1.

Разработать программу получения обратной польской записи арифметических выражений, составленных из однобуквенных идентификаторов, открывающей и закрывающей скобок и операций: +, -, /, *, ^ (возведение в степень).

Алгоритм перевода, предложенный Э. Дейкстрой, основывается на использовании стека с приоритетами. Все символы операций и скобки имеют определенный приоритет. Для построения польской записи продвигаются вдоль выражения слева направо. Операнды переписываются в выходную строку, а операции запоминаются в стек. Если приоритет помещаемой в стек операции меньше приоритета операции, находящейся в вершине стека, то происходит выталкивание операций из стека по одной до тех пор, пока в вершине не окажется операция с меньшим приоритетом или стек не окажется пустым. Закрывающая скобка вызывает выталкивание всех символов до открывающей скобки (скобки в выходное выражение не переписываются). Операции имеют следующие приоритеты:

Операция	(	+, -	*, /	^
Приоритет	0	1	2	3



3. Выполнение

Алгоритм работы программы на примере.

программный инженерный ориентированный арифметический



4. Текст программы на языке С#

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.IO;

namespace lab1Console

{

class Program

{

enum ActionName

{

Addition,

Substration,

Multiplication,

Division,

OpenBracket,

CloseBracket,

Involution

}

class Action

{

public ActionName Name { get; set; }

public int Priority { get; set; }

public char Value;

Action(ActionName name, int priority, char value)

{

Name = name;

Priority = priority;

Value = value;

}

public override string ToString()

{

return Value.ToString();

}

public static Action Addition = new Action(ActionName.Addition, 1, '+');

public static Action Substration = new Action(ActionName.Substration, 1, '-');

public static Action Multiplication = new Action(ActionName.Multiplication, 2, '*');

public static Action Division = new Action(ActionName.Division, 2, '/');

public static Action OpenBracket = new Action(ActionName.OpenBracket, 0, '(');

public static Action CloseBracket = new Action(ActionName.CloseBracket, 0, ')');

public static Action Involution = new Action(ActionName.Involution, 3, '^');

}

static void Main(string[] args)

{

Console.WriteLine(GetPolIZ(GetStringFromFile("C:\\Input\\example_1.txt")));

}

static string GetStringFromFile(string path)

{

FileStream inputFile = null;

StreamReader strReader = null;

string inputString = null;

try

{

inputFile = new FileStream(path, FileMode.Open);

strReader = new StreamReader(inputFile);

inputString = strReader.ReadToEnd();

strReader.Close();

inputFile.Close();

}

catch (Exception e)

{

if (inputFile != null)

inputFile.Close();

if (strReader != null)

strReader.Close();

Console.WriteLine("Error in GetStringFromFile: " + e.Message);

}

if (inputString != null)

{

return inputString;

}

else

{

return "";

}

}

static string GetPolIZ(string str)

{

string retVal = "";

Stack<Action> stack = new Stack<Action>();

for (int i = 0; i < str.Length; i++)

{

if (IsChar(str[i]))

{

retVal += str[i];

}

else

{

switch (str[i])

{

case '+':

retVal += ChangeStack(stack, Action.Addition);

break;

case '*':

retVal += ChangeStack(stack, Action.Multiplication);

break;

case '/':

retVal += ChangeStack(stack, Action.Division);

break;

case '-':

retVal += ChangeStack(stack, Action.Substration);

break;

case ')':

retVal += ChangeStack(stack, Action.CloseBracket);

break;

case '(':

retVal += ChangeStack(stack, Action.OpenBracket);

break;

case '^':

retVal += ChangeStack(stack, Action.Involution);

break;

default:

Console.WriteLine("Incorrect symbol: " + str[i]);

return "";

}

}

}

while (stack.Count != 0)

{

retVal += stack.Pop().ToString();

}

return retVal;

}

static string ChangeStack(Stack<Action> stack, Action action)

{

string retVal = "";

if (action.Name != ActionName.CloseBracket)

{

while (stack.Count != 0 && stack.Peek().Priority >= action.Priority && action.Priority!=0)

{

if (stack.Peek().Name != ActionName.OpenBracket && stack.Peek().Name != ActionName.CloseBracket)

{

retVal += stack.Peek().ToString();

}

stack.Pop();

}

stack.Push(action);

}

else

{

while (stack.Count != 0 && stack.Peek().Name != ActionName.OpenBracket)

{

if (stack.Peek().Name != ActionName.OpenBracket && stack.Peek().Name != ActionName.CloseBracket)

{

retVal += stack.Peek().ToString();

}

stack.Pop();

}

if (stack.Count != 0)

stack.Pop();

}

return retVal;

}

static bool IsChar(char ch)

{

return ((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z'));

}

5. Результат работы программы

Размещено на Allbest.ru