75671

Задача синтаксичного аналізу формули

Практическая работа

Информатика, кибернетика и программирование

На початку програми користувачу пропонується ввести вираз. Потім вираз перевіряється на коректність за допомогою функції bool CheckExp(string s). Спочатку відбувається перевірка використаних символів. Потім перевірка правильності розставлення дужок, знаків, запису функції у виразі...

Украинкский

2015-01-24

267.86 KB

1 чел.

Міністерство  освіти  і  науки України

Вінницький національний технічний університет

Інститут інформаційних технологій та комп’ютерної інженерії

Кафедра ПЗ

Практична робота №7 варіант №9

з дисципліни Алгоритми та структури даних

Виконала: ст. гр. 1 ПІ-13б                            Лілик Л. С.

Перевірив:                                                       Власюк В. Х.

Вінниця, 2013


Тема: Задача синтаксичного аналізу формули.

 

Мета:  Закріпити знання про рекурсивні методи, а саме про непряму рекурсію. Сформувати навички синтаксичного аналізу формул. Сформувати уміння застосовувати синтаксичні діаграми і синтаксичний аналіз для обчислення значення виразів.

Завдання:

Варіант № 9.

Напишіть програму синтаксичного аналізу правильності арифметичного виразу, що містить ще операцію піднесення в степінь і функції від однієї або декількох змінних. Ім'я функції містить три букви.

Опис алгоритму виконання

На початку програми користувачу пропонується ввести вираз. Потім вираз перевіряється на коректність за допомогою функції bool CheckExp(string s). Спочатку відбувається перевірка використаних символів. Потім перевірка правильності розставлення дужок, знаків, запису функції у виразі. CheckExp(string s) повертає true (правильно) і відповідно false (неправильно) в залежності від результатів перевірки виразу.

Складність алгоритму

Складність алгоритму дорівнює О(4N) від t,

де tчас виконаня,

Nкількість символів у стрічці виразу.


Блок-схема алгоритму


Лістинг фрагментів програми

#include "stdafx.h"

using namespace std;

bool CheckExp(string s)

{

bool qwerty=true;

if(s.find("!",0)<=s.size()||s.find("@",0)<=s.size()||s.find("#",0)<=s.size()||

s.find("$",0)<=s.size())

 qwerty=false;

if(s.find("%",0)<=s.size()||s.find("_",0)<=s.size()||s.find("=",0)<=s.size()||

s.find("?",0)<=s.size())

 qwerty=false;

if(s.find("[",0)<=s.size()||s.find("]",0)<=s.size()||s.find("{",0)<=s.size()||

s.find("}",0)<=s.size())

 qwerty=false;

if(s.find("|",0)<=s.size()||s.find("`",0)<=s.size()||s.find("<",0)<=s.size()||

s.find(">",0)<=s.size())

 qwerty=false;

int countClB=0;

int countOpB=0;   

bool Brackets=false;

bool Br=true;

for (int i=0; i<s.size(); ++i)

{

 if(s[i]==')')

  ++countClB;

 if (countClB>countOpB)

  Br = false;

 if(s[i]=='(')

  ++countOpB;

}

for (int i=0; i<s.size()-1; ++i)

{

 if(s[i]=='('&&s[i+1]==')')

  Br=false;

}

for (int i=0; i<s.size()-1; ++i)

{

 if(s[i+1]=='('&&s[i]==')')

  Br=false;

}

if((countOpB==countClB)&&(Br==true))

 Brackets=true;

bool Sign=false;

bool Si=true;

for (int i=0; i<s.size()-1; ++i)

{

 if(s[i]==')'&&(s[i+1]!='+'&&s[i+1]!='/'&&s[i+1]!='*'

&&s[i+1]!='^'&&s[i+1]!='-'))

  Si=false;

}

if (s.size()>1)

if(s[0]=='('&&(s[1]=='+'||s[1]=='/'||s[1]=='*'||s[1]=='^'))

 Si=false;

if (s.size()>0)

if(/*s[1]=='('&&*/(s[0]=='+'||s[0]=='/'||s[0]=='*'||s[0]=='^'))

 Si=false;

if (s.size()>1)

if(s[0]==','&&(s[1]=='+'||s[1]=='/'||s[1]=='*'||s[1]=='^'))

 Si=false;

if (s.size()>0)

if(s[1]==','&&(s[0]=='+'||s[0]=='/'||s[0]=='*'||s[0]=='^'))

 Si=false;

if (s.size()>0)

if((s[s.size()-1]=='+'||s[s.size()-1]=='/'||s[s.size()-1]=='*'||s[s.size()-1]=='^'||

s[s.size()-1]=='-'))

 Si=false;

for (int i=1; i<s.size(); ++i)

{

 if((s[i]=='-'||s[i]=='+'||s[i]=='/'||s[i]=='*'||s[i]=='^')&&(s[i-1]=='-'||

s[i-1]=='+'||s[i-1]=='/'||s[i-1]=='*'||s[i-1]=='^'))

  Si=false;

 if(s[i-1]=='('&&(s[i]=='+'||s[i]=='/'||s[i]=='*'||s[i]=='^'))

  Si=false;

 if(s[i]==')'&&(s[i-1]=='+'||s[i-1]=='/'||s[i-1]=='*'||s[i-1]=='-'||s[i-1]=='^'))

  Si=false;

 if(s[i-1]==','&&(s[i]=='+'||s[i]=='/'||s[i]=='*'||s[i]=='^'))

  Si=false;

 if(s[i]==','&&(s[i-1]=='+'||s[i-1]=='/'||s[i-1]=='*'||s[i-1]=='-'||s[i-1]=='^'))

  Si=false;

}

if(Si) Sign=true;

 

bool Function=false;

bool Fu=true;

if (s.size()>=6)

for(int i=4; i<s.size()-2; ++i)

{

 if(s[i]=='('&&(s[i-1]!='+'&&s[i-1]!='/'&&s[i-1]!='*'&&s[i-1]!='-'&&

s[i-1]!='^'&&s[i-1]!='('&&s[i-1]!=')'&&s[i-1]!='='))

 {

  if(s[i]=='('&&(s[i-4]=='+'||s[i-4]=='/'||s[i-4]=='*'||s[i-4]=='-'||s[i-4]=='^'))

  {

   if(s[i-3]=='+'||s[i-3]=='/'||s[i-3]=='*'||s[i-3]=='-'||s[i-3]=='^'||

s[i-3]=='('||s[i-3]==')'||s[i-3]=='=')

    Fu=false;

   if(s[i-2]=='+'||s[i-2]=='/'||s[i-2]=='*'||s[i-2]=='-'||s[i-2]=='^'||

s[i-2]=='('||s[i-2]==')'||s[i-2]=='=')

    Fu=false;

  }

  else Fu=false;

 }

}

if (s.size()>1)

if(s[1]=='('&&(s[0]!='+'&&s[0]!='/'&&s[0]!='*'&&s[0]!='-'&&

s[0]!='^'&&s[0]!='('&&s[0]!=')'&&s[0]!='='))

 Fu=false;

if (s.size()>2)

if(s[2]=='('&&(s[1]!='+'&&s[1]!='/'&&s[1]!='*'&&s[1]!='-'&&

s[1]!='^'&&s[1]!='('&&s[1]!=')'&&s[1]!='='))

 if(((s[0]!='+'&&s[0]!='/'&&s[0]!='*'&&s[0]!='-'&&

s[0]!='^'&&s[0]!='('&&s[0]!=')'&&s[0]!='='))||s[0]=='-')

  Fu=false;

if (s.size()>3)

if(s[3]=='('&&(s[2]!='+'&&s[2]!='/'&&s[2]!='*'&&s[2]!='-'&&

s[2]!='^'&&s[2]!='('&&s[2]!=')'&&s[2]!='='))

 if((s[1]!='+'&&s[1]!='/'&&s[1]!='*'&&s[1]!='-'&&

s[1]!='^'&&s[1]!='('&&s[1]!=')'&&s[1]!='='))

  if(s[0]=='-')

   Fu=false;

if(Fu) Function=true;

if(Brackets&&Sign&&Function&&qwerty)

 return true;

else return false;

}

int _tmain(int argc, _TCHAR* argv[])

{

string str;

cout<<"Input arithmetic expression: ";

getline(cin, str);

int n=str.size();

if (n>2)

{

 for(int i=0; i<n; ++i)

 {

  size_t pos=str.find(" ",0);

  if(pos<=n&&pos>=0)

   str.erase(pos,1);

 }

 cout<<endl<<str<<endl;

 if(!CheckExp(str))

  cout<<"\nERROR! Expression isn't correct!\n";

 else cout<<"\nExpression is correct.\n";

}

else cout<<"\nERROR! Expression isn't correct!\n";

getch();

}

Результат виконання

Висновки

Сформували навички синтаксичного аналізу формул. Сформували уміння застосовувати синтаксичні діаграми і синтаксичний аналіз для обчислення значення виразів. В ході виконання практичної роботи було створено програму для синтаксичного аналізу  арифметичного виразу, що містить знаки +, -, *, /, ^ (піднесення до степеня) та передбачає використання функцій.


 

А также другие работы, которые могут Вас заинтересовать

45218. Опыт пропаганды и агитации советского периода 41.5 KB
  Опыт пропаганды и агитации советского периода И. Но для того чтобы проводить работу наиболее эффективно необходимо создание системы понастоящему массовой пропаганды которая . В 1939 году было создано управление пропаганды и агитации при ЦК ВКПб По словам Сталина: .сосредоточить в одном месте дело партийной пропаганды и агитации и объединить отделы пропаганды и агитации и отделы печати в едином Управлении с организацией соответствующего отдела пропаганды и агитации в составе каждой республики краевой и областной парторганизации.
45219. Современные политические ПР-технологии России: опыт, тенденции и проблемы развития 48 KB
  Задачи: формирование и продвижение имиджа доведение до избирателя правдивой информации о кандидатах донесение до кандидата реальных проблем и ожиданий групп населения. Особенность воздействия на массовое сознание состоит в том что с помощью него можно усилить роль тех черт кандидата его способностей внешности которые могут привлечь симпатии избирателей. Для персонального консультирования специалист должен уметь: провести адекватную диагностику ситуации видеть явные и скрытые проблемы и ресурсы; выстроить стратегию наращивания...
45220. Интегрированные коммуникации в деятельности современных бизнес-структур: опыт, проблемы, перспективы развития 36.5 KB
  ИМК - это новая организационная технология способная решить многие проблемы связанные с ростом всех типов коммуникаций. Это новая форма организации маркетинга это новая философия и стратегия бизнес-коммуникаций следуя которой можно вывести на новый качественный уровень все виды взаимодействия с потребителем. ИМК практика унификации всех средств маркетинговых коммуникаций начиная с рекламы и заканчивая упаковкой для передачи целевой аудитории последовательного убедительного сообщения способствующего наиболее полной реализации целей...
45221. Российский опыт использования ПР-технологий в деятельности государственных структур 25 KB
  Российский опыт использования ПР-технологий в деятельности государственных структур. В случае государственных структур объектом воздействия становится налогоплательщик гражданин который хочет и имеет право знать обо всех действиях государственных органов разного уровня. Эта технология используется в российских государственных ПР для корректировки проблемы после того как коммуникация начала развертываться в нежелательном направлении и события приняли нежелательный оборот. Основная задача государственных ПР создание образа компетентного и...
45222. Специфика ПР деятельности общественных объединений 29 KB
  Цель ПР в третьем некоммерческом секторе помощь в реализации различных социальных проектов привлечение внимания общественности к важным социальным проблемам формирование общественного мнения относительно необходимости решения данных проблем. Взаимоотношения социальных служб и СМИ также является одной из сложных задач. Ведь несмотря на то что в любой газете есть отдел социальных проблем журналисты не часто пишут об НКО поскольку плохо знают их работу. Деятельность по связям с общественностью в социальных службах включает в себя: 1.
45223. Подготовка РК специалистов в России: специфика, проблемы, перспективы развития ПР образования 26.5 KB
  Подготовка РК специалистов в России: специфика проблемы перспективы развития ПР образования. Российская подготовка ПРспециалистов учитывает опыт их подготовки в других странах что позволило избежать ряда крупных ошибок. Например данная специальность на была помещена на факультеты журналистики как в США 2 3 всех специалистов против этого выступает Э. Но мы стоим в преддверии такой проблемы как перепроизводство специалистов которые вопервых могут быть просто не нужны потому что столько не нужно и вовторых которые могут быть не...
45224. Миссия, идеология и направления деятельности профессиональных международных объединений ПР-специалистов: IРRА,СЕRР,IАВС,IРR,РRSА 44.5 KB
  Рост числа профессиональных ассоциаций отражает серьезность усилий предпринимаемых многими специалистами в области ПР в целях придания этой функции должного статуса и дальнейшей ее профессионализации. IРRА пропагандирует престиж профессий специалиста в области РR высокие стандарты и соблюдение этических норм среди специалистов которым приходится иметь дело с международными аспектами РR. IPR издает так называемые Золотые страницы по важнейшим проблемам представляющим интерес для мирового сообщества специалистов в области PR. Это...
45225. Миссия, идеология и направления деятельности российских профессиональных организаций ПР-специалистов: РАСО 33.5 KB
  Миссия идеология и направления деятельности российских профессиональных организаций ПРспециалистов: РАСО РАСО была создана в июле 1991. Декларация профессиональных и этических принципов в области связей с общественностью РАСО. В основу поведений членов РАСО легли общечеловеческие ценности и универсальные права личности: свобода слова свобода печати и собраний на свободный доступ к информации; ответственность перед обществом в том числе за достоверность точность и честность распространяемой информации. Члены РАСО руководствуются...
45226. Кодексы профессионального поведения профессиональных зарубежных сообществ: этическая основа, ценностно-нормативная специфика 61.5 KB
  Положения кодекса приняты с целью пропаганды и активного внедрения высоких стандартов общественной деятельности и этики поведения членов РRSА. Член обязан сохранять в тайне конфиденциальную информацию доверенную ему нынешними или бывшими клиентами или служащими. Член не должен представлять интересы одной из конфликтующих сторон без согласия на то всех заинтересованных сторон. Член не должен заниматься никакой деятельностью которая имеет тенденцию к нанесению ущерба репутации СМИ.