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();

}

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

Висновки

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


 

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

32997. Философская концепция человека 20.64 KB
  Б Жизнь человека подчиняется биологическим законам Биоорганизация человека есть результат развития длинного ряда его предков животное обезъяналюди гомениды современный человек Человек в отличие от животных имеет такие биологические структуры которые служат материальными предпосылками для развития чисто человеческих особенностей: возникают органы позволяющие человеку трудиться рука мозг и прямая походка 2. Человек обладает качественными надбиологическими образованиями которые формируют социальную характеристику человека....
32998. Понятие науки, её функции 20.99 KB
  Теоретические уровни отдельных наук смыкаются в общетеоретическом философском объяснении открытых принципов и законов в формировании мировоззренческих и методологических сторон научного познания в целом. Социологический анализ деятельности института науки в современном обществе дает основание утверждать что главной функцией науки является производство и умножение достоверного знания позволяющего раскрывать и объяснять закономерности окружающего мира Указанная выше основная функция науки в современном обществе может быть конкретизирована и...
32999. Философия техники, Исследование первопричин техники 24.35 KB
  Исследование первопричин техники. Основоположником этого раздела философии является Эрнст Капп написавший Основные направления философии техники 1877. философия техники во-первых исследует феномен техники в целом во-вторых не только ее имманентное развитие но и место в общественном развитии в целом в-третьих принимает во внимание широкую историческую перспективу.
33000. Философия и ее предмет. Исторические условия возникновения философии 42.2 KB
  Философия - любовь к мудрости (от греч. phileo - люблю и sophia - мудрость) - возникает в VII-VI веках до н.э. в Древней Греции и на Востоке - в Индии и Китае. С тех пор не утихают споры о предмете философских размышлений, назначении философии, ее соотношении с другими формами человеческой духовной деятельности.
33001. ФИЛОСОФИЯ ДРЕВНЕГО ВОСТОКА 35.04 KB
  РВ вобрала в себя миф и ритуал в таком виде она несла зачаток как религиозного так и философского видения мира и человека. Есть там и идея макрокосмической эмбриогонии согласно которой рождение космоса рассматривается по аналогии с зачатием и рождением человека в материнском лоне. Космос порождает человека. В рамках древнеиндийской философии подчёркивается значение духовной стороны человека она приобретает здесь космический смысл.
33002. Милетская школа. Милетская школа философии 26.78 KB
  Обратимся к наиболее известному опровержению возможности движения знаменитым апориям Зенона которого Аристотель назвал изобретателем диалектики. Но для философа вопрос ставиться не в плоскости эмпирического существования движения а в плане мыслимости его противоречивости и в системе понятия в диалектике его соотношения с пространством и временем. Элиатам не удалось доказать что движения нет. Они своими тонкими рассуждениями показали то что едва ли кто из их современников осмысливал что такое движение Сами они в своих размышлениях...
33003. Платон и Аристотель 17.61 KB
  Философскоэтические взгляды Платона изложены в многочисленных диалогах главное действующее лицо которых как правило его учитель Сократ. В дошедших до нас произведениях нет законченной философской системы поэтому воззрения Платона на те или иные вопросы служили и продолжают служить предметом спора между исследователями. Образы идеи по мнению Платона находятся вне времени и пространства недоступны восприятию но их может созерцать разум который и связывает два мира: потусторонний и реальный. Трудно назвать область знаний которая не...
33004. Философия поздней античности 17.13 KB
  В смысловой мир человека вторгалось чувство безосновности и негарантированности существования. Именно они порабощают человека. Его основатель Зенон из Китая утверждал что основная цель человека жить в согласии с природой и это то же самое что жить согласно с добродетелью. Стоический мудрец идеал человека является воплощенным разумом.
33005. Философия средневековья, монотеизм как основа философии средневековья 20.82 KB
  Для философии это был период когда изменились цель и характер философствования. Философы могли свободно создавать свои мировоззренческие концепции как в области онтологии так и в гносеологии этике эстетике социальной философии. А тот факт что тенденция к союзу философии и теологии к их взаимодействию проявилась еще в конце античности...