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

}

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

Висновки

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


 

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

3965. Основные объекты и действия в испанском языке. Грамматика испанского языка 380.09 KB
  Имя существительное в испанском языке имеет два рода: мужской и женский, и два числа: единственное и множественное. Род существительного в испанском языке может не совпадать с родом соответствующего слова в русском языке (так, например, слово “libro” – мужского рода, а его русский эквивалент «книга» – женского рода).
3966. Пакет Swing компонувальники LayoutManager 379.45 KB
  Лабораторна робота (Пакет Swing – компонувальники (LayoutManager)) Тема роботи: Пакет Swing – компонувальники (LayoutManager). Мета роботи: Дослідити роботу, одного з компонентів пакету Swing, компонувальники (LayoutManager). План ро...
3967. Определение момента инерции маятника Максвелла 379.34 KB
  определить момент инерции маятника экспериментально и сравнить его с теоретическим значением. Установка маятника Максвелла может отличаться от ниже описанной, но принцип работы тот же
3968. МОБІЛЬНІ ГЕНЕТИЧНІ ЕЛЕМЕНТИ ГЕНОМУ ЛЮДИНИ: СТРУКТУРА, РОЗПОДІЛ І ФУНКЦІОНАЛЬНА РОЛЬ 377.25 KB
  Наведено дані про мобільні генетичні елементи (МГЕ) людини, на частку яких припадає майже 45% геному. Поряд із класифікацією і локалізацією МГЕ особливу увагу приділено їхній ролі у функціонуванні геному, зокрема участі у рекомбінаційних процесах, регуляції ак тивності генів та в утворенні нових генів.
3969. Типове положення про службу захисту інформації в автоматизованій системі 375.74 KB
  «Типове положення про службу захисту інформації в автоматизованій системі» Виконала: ст. гр. СН-41 Ковальчук Лариса У загальному випадку «Типове положення про службу захисту інформації (СЗІ) в автоматизованій системі (АС)» складається з таких розділ...
3970. Схемотехніка логічних елементів та їх реалізація на мікропроцесорі 365.86 KB
  Специфіка програмування мікроконтролера PIC16F628. Рішення задач. Створення проекту в MPLAB. Створення проекту в PROTEUS. Схемотехніка логічних елементів та їх реалізація на базі мікропроцесорів. Прості висловлення – логічний елемент (змінна) – входить до складу складного висловлення логічної функції, яка залежить від істинності чи помилковості аргументів.
3971. ІНФОРМАЦІЙНА БЕЗПЕКА WEB 2.0 359.9 KB
  ІНФОРМАЦІЙНА БЕЗПЕКА WEB 2.0. Що таке Web 2.0 WEB 2.0 – це методика проектування систем, котрі шляхом врахування мережевих взаємодій стають тим краще, чим більше ними користуються. Web 2.0 - не технологія і не особливий ...
3972. АЭРОНАВИГАЦИЯ Методические указания по изучению дисциплины и выполнению контрольных работ 355.61 KB
  Дисциплина «Аэронавигация» является профилирующей, которая определяет уровень профессиональной подготовки студентов специализации «Летная эксплуатация гражданских воздушных судов». Она является основой для изучения других дисциплин, формирующих профессиональную подготовку.
3973. Знайомство з пакетом Swing 350.08 KB
  Лабораторна робота №7 (Знайомство з пакетом Swing) Тема роботи: Знайомство з пакетом Swing Мета роботи: Дослідити пакет Swing. План роботи. Ознайомлення з компонентами бібліотеки Swing. Навчитися добавляти компоненти до контейнерів Озн...