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

  • 26 сент. 2011 г.
  • 1265 Слова
Федеральное агентство по образованию
ГОУВПО «Удмуртский Государственный университет»
Факультет информационных технологий и вычислительной техники

Лабораторная работа
на тему «Реализация конечных автоматов».



Выполнил: ст. гр. 39-41
Дурнев С.Е.

Проверил: старший преподаватель Анисимов А.Е.




Ижевск 2010г.

Оглавление
Постановка задачи 4Определение конечного автомата 5
Графический вид 5
Табличный вид 5
Примеры входных цепочек 6
Тексты программной реализации 7
1. Рекурсия 7
2. Циклы 10
3. Функции 13
4. Метки 16

Постановка задачи

Вариант 28
Сумма слагаемых - целых чисел или их произведений

Примеры допускаемых входных цепочек
1+2*3+5*2*1
100
5+3+1

Определение конечного автомата
Графический вид

Табличный вид  | Условие | Действие | Переход |
start |   | s = 0 |   |
| | m = 1 | |
| | do = '+' | |
| | res = 0 | |
q0 | d | k = d | q2 |
q1 | d | k = k*10 + d | q1 |
  | + | '*' : { s += m*k } | q0 |
| | '+' : { s += k } | |
| | do = '+' | |
| | m = 1 | |
| * | do = '*' | q0 |
| | m = m*k | |
| ¶ | '*' : { m=m*k } | q2 |
| | '+' : { s+=k; m=0; } | |
|| | |
| | return (m+s) | |

Примеры входных цепочек
№ | Входная цепочка | Результат |
1 | 1 + 2 * 3 + 5 * 2 * 1 | 17 |
2 | 100 | 100 |
3 | 5 + 3 + 1 | 9 |
4 | 595 * 2 + 300 | 1490 |
5 | 2 * 40 + 0 + 35 * 1 | 115 |
6 | 2*49*1*0 | 0 |
7 | 1+3*1+2 | 6 |
8 | 1++99 | Error//Ошибка синтаксиса |
9 | 1*0*1312 | 0 |
10 | 1 + 3 – 1 | Error//Неверная операция |

Текстыпрограммной реализации
1. Рекурсия

// recurse.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "iostream"

using namespace std;

char ch, to_do; //Объявление переменных, начальное состояние
int n;
int s = 0;
int res = 0;
int m = 1;

void q0(); // Объявление функций состояний
void q1();
void q2();
void error();

int is_digit(char c)
{return'0'<=c && c<='9';}

int digit(char c)
{return int(c-'0');}

void q0()
{
if (is_digit(ch)) //Проверка ввода цифры
{
n = digit(ch);
ch = getchar();
q1();
}
else
{
error();
return;
}
return;
}

void q1()
{
if (is_digit(ch))
{
n = n * 10 + digit(ch); //Создание числа из последовательности цифр
ch =getchar();
q1();
}
else
{
if (ch=='+') //Действие сложение
{
if (to_do=='*') //Реализация «приоритета» действий
{
s += m*n;
}
if (to_do=='+')
{
s +=n;
}
to_do = '+'; //Текущее действие - сложение
m = 1;
ch = getchar();
q0(); //Переход в 0-состояние
}
else{
if (ch == '*') //Действие умножение
{
to_do = '*';
m *= n; //Домножение накопленного произведения на введенноечисло
ch = getchar();
q0();
}
else
if (ch=='\n') // Конец строки
{
if ( to_do=='*') //Вычисление последнего действия
{
m *=n;
}
else
if (to_do == '+')
{s += n;
m = 0;
}
s = s+m; //Сложение накопленных «суммы» и «произведения»
q2();
}
else
{
error(); //Ошибка синтаксиса введеной строки
return;
}
}
}
return;
}

void q2()
{
return; //Конечное состояние
}

void error()
{
printf("Error\n");

return;
}

int _tmain(int argc, _TCHAR* argv[])
{
s = 0;
m = 1;to_do = '+';
res = 0;
cout << "Enter the formula, pls. \n";
ch = getchar();
q0(); //Переход в начальное состояние
cout <<"Result: "<<s;
cout <<"\nPress any key";
while ( ! cin.get(ch))
return 0;
}

2. Циклы

// Lab_r_1.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "iostream"...
tracking img