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

}

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

Висновки

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


 

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

25846. Аудит расчетов с персоналом по оплате труда 59 KB
  Складываются новые отношения между государством предприятием и работником по поводу организации труда. Предприятия вправе выбирать системы и формы оплаты труда самостоятельно исходя из специфики и задач стоящих перед предприятием. На первом месте по важности среди факторов влияющих на эффективность использования рабочей силы стоит система оплаты труда.
25847. Выбор программ автоматизации бухгалтерского дела 25.5 KB
  При этом если бы покупатель мог сам оценить качество программного продукта сравнить экономическую эффективность предлагаемых программных средств провести оценку достоверности информации содержащейся в рекламных сведениях то наверняка было бы меньше разочарования после покупки программных продуктов данного направления. Наиболее важные из них следующие: функциональная полнота; завершенность разработки; быстродействие; уровень требований к комплексу технических средств; возможность перенастройки на новые условия...
25848. Документ как специальный носитель информации 27.5 KB
  Документы используются в различных областях деятельности отраслях знаний сферах жизни и являются объектом исследования многих научных дисциплин поэтому содержание понятия документ многозначно и зависит от того в какой отрасли и для каких целей он используется. По мнению специалистов – документоведов документ представляет собой результат отображения фактов событий предметов явлений объективной действительности и мыслительной деятельности человека. Документ изготавливается на специальном материале бумаге фотопленке и т.
25849. Документооборот и его организация 28 KB
  Организация работы с документами организация документооборота хранения и использования документов в текущей деятельности учреждения. Документооборот является важным звеном в организации делопроизводства в организации учреждении так как он определяет не только инстанции движения документов но и скорость движения документов. В делопроизводстве документооборот рассматривается как информационное обеспечение деятельности аппарата управления его документирования хранения и использования ранее созданных документов.
25850. Должностная инструкция бухгалтера 39 KB
  Инструкция раскрывает основные должностные обязанности бухгалтера его права и ответственность а также требования к квалификации. Предложенная типовая должностная инструкция бухгалтера может служить основой для разработки должностной инструкции содержащей более конкретный перечень должностных обязанностей бухгалтера с учетом особенностей предприятия организации производства труда и управления конкретного участка который ведет бухгалтер а также прав и ответственности бухгалтера. Должностная инструкция в которой четко сформулированы...
25851. Аудиторская палата России 38 KB
  Специалистами – членами палаты разработан и используется Кодекс профессиональной этики аудиторов. Однако практика работы за последние три года показала что реализация Палатой решений принимаемых на общероссийских конференциях сталкивается с серьезными трудностями по ряду причин к важнейшим из которых относятся: невозможность в силу правового статуса ассоциации принимать в ряды ее членов аудиторские фирмы и аудиторов; отсутствие в регионах структурных подразделений Аудиторской палаты России; недостаточный уровень взаимодействия с...
25852. Бухгалтерский аутсорсинг 29.5 KB
  Успешно осуществляющиеся на западе аутсорсинговые услуги сегодня находят своего потребителя и в Российской Федерации. Передача части работ на аутсорсинг позволяет сократить издержки так как зачастую услуги аутсорсера стоят намного дешевле чем содержание собственного персонала. По договору аутсорсинга как правило передаются такие функции как: поддержка информационных систем локальных сетей webсайта; защита информации; администрирование компьютерных сетей; разработка внедрение и последующее обслуживание корпоративных программных...
25853. Бухгалтерский аутсорсинг 39.5 KB
  Бухгалтерский аутсорсинг от outsource внешний источник или средства замена наемного труда услугами сторонней компанииспециалиста; передача компании бухгалтерской фирме функции ведения бухгалтерского учета бухгалтерское сопровождение В России бухгалтерский аутсорсинг появился сравнительно недавно 78 лет назад. Основными заказчиками бухгалтерского аутсорсинга еще недавно были иностранные организации работающие в Российской Федерации а также совместные предприятия. Однако сейчас все больше и российских организаций пользуются...
25854. Взаимосвязь финансового и управленческого учета 26 KB
  Аналитическая информация управленческого учета используется исключительно для внутреннего управления. Такое подразделение бухгалтерского учета можно объяснить тем что в принципе вся система бухгалтерского учета является составной частью управленческой системы организации. Общепринятые принципы финансового учета могут действовать также и в управленческом учете поскольку руководители предприятий в своей деятельности не могут руководствоваться исключительно непроверяемыми субъективными оценками и мнениями.