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

}

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

Висновки

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


 

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

74840. Хождение за три моря тверского купца Афанасия Никитина 17.94 KB
  Хождение за три моря Афанасия Никитина. является Хождение за три моря тверского купца Афанасия Никитина помещенное под 1475 г. Да станет Русская земля благоустроенной и да будет в ней справедливость Православная вера является для Никитина символом родины.
74841. Памятник Муромо-Рязанской литературы – «Повесть о Петре и Февронии» Поэтичность, демократизм повести. Образ крестьянки Февронии 17.58 KB
  Герои повести — исторические лица: Петр и Феврония княжили в Муроме в начале XIII века, они умерли в 1228 г. Однако в повести историчны только имена, вокруг которых был создан ряд народных легенд, составивших основу сюжета повести. Как указывает М. О. Скрипиль, в повести объединены два народнопоэтических сюжета: волшебной сказки об огненном змее и сказки о мудрой деве.
74842. Домострой – книга, утвердившая нормы семейной жизни 15.89 KB
  Следует отнести также Домострой составление которого приписывается благовещенскому попу Сильвестру входившему в Избранную раду. Домострой регламентировал поведение человека как в государственной так и в семейной жизни.
74843. Бытовая повесть. Повесть о Горе и Злочастии 17.34 KB
  Основу сюжета повести составляет трагическая история жизни Молодца отвергнувшего родительские наставления и пожелавшего жить по своей воле как ему любо. Постоянная опека родителей не научила Молодца разбираться в людях понимать жизнь и он платится за свою доверчивость за слепую веру в святость уз дружбы. Губит Молодца похвальба своим счастьем и богатством. В сознании Молодца еще живучи традиционные представления.
74844. Житие протопопа Аввакума, им самим написанное. Автобиография «Жития». Демократизм и публицистичность «Жития». Традиция и новаторство в жанре Жития 21.16 KB
  Житие протопопа Аввакума им самим написанное. Аввакум так определяет рамки своего повествования. Центральная тема жития тема личной жизни Аввакума неотделимая от борьбы за древлее благочестие против Никоновых новшеств.
74845. Публицистика петровского времени. Юности честное зерцало 14.87 KB
  Зерцало было издано в соответствии с духом петровских реформ когда основу всей книгопечатной продукции составляли разного рода руководства и наставления. Вторая часть это собственно зерцало то есть правила поведения для младых отроков и девушек дворянского сословия.
74846. Екатерина II. «Всякая всячина». Н.И. Новиков, его литературные труды и сатирические журналы. Сатира на лица и на пороки 16.52 KB
  Новиков его литературные труды и сатирические журналы. Предполагают что свои материалы в журнал посылали Фонвизин князь Щербатов и даже Новиков. Новикова. В Трутне под подписью Правдолюбов Новиков упрекает Екатерину.
74847. Классицизм как литературное направление. А.Д. Кантемир, В.К. Тредьяковский, М.В. Ломоносов 15.87 KB
  Сын астраханского священника он подобно Ломоносову охваченный жаждой знаний ушел из родительского дома учился в Славяно-греколатинской академии а затем – за границей в Сорбонне. Одновременно с Ломоносовым был удостоен звания профессора Академии наук. Как поэта его при жизни затмили Сумароков и Ломоносов.
74848. Творчество Д.И. Фонвизина. «Недоросль» 14.62 KB
  Фонвизина Недоросль создателя подлинно самобытной национальной комедии который заложил внутри этой системы основы критического реализма. В комедии сочетаются яркие и правдивые сцены из жизни поместного дворянства и страстная проповедь просветительских идей об обязанностях правительства прямого честного гражданина. Хотя в основе сюжета лежит любовный конфликт стремление героев жениться на богатой наследнице все же основной конфликт комедии намного глубже. Другая проблема комедии истинное и ложное воспитание.