Сложение-вычитание
и умножение-деление (без скобок).
Теперь начнем программировать. Сперва – один из самых простых случаев – формула со сложением-вычитанием и умножением-делением, причем без скобок. Форма Бэкуса-Наура такая:
<expr> := <term>
{<add_op><term>}
<term> :=
<factor>{<mul_op><factor>}
<factor> := <integer>
Обозначения такие: term – это слагаемое, add_op – это плюс или минус (+ или -), factor – это множитель, mul_op – это * или /. А expr – это формула. Integer – это целое число.
Сперва нужен сканер, который будет «доставлять» нам очередную лексему. Здесь мы пойдем наиболее простым путем (вернее одним из наиболее простых). Если программировать настоящий сканер, то легко запутаться. Сделаем так: пусть все лексемы уже записаны в текстовом файле Pr.txt, например так:
1
+
2
То-есть в каждой строчке строго одна лексема. Далее составим функцию, которая будет увеличивать на единицу глобальную переменную J и выдавать J-ю строчку файла. Насчет быстродействия озабочиваться не будем, главное – чтобы четко работал принцип.
Роль сканера выполняет функция NextLexema.
В этой функции используется написанная мной функция FindStrN. Она непосредственно достает определенную строчку из текстового файла. Поконкретнее ее описание можно найти, зайдя на мой сайт kiteev2005.narod.ru, ссылка «Библиотеки функций», далее – «Функции для обработки строк».
В дальнейшем я часто буду
использовать свои «личные» функции. Возможно иногда буду забывать пояснять, что
они делают. Но мы здесь стараемся останавливаеться на основных принципах
работы, а не на частностях. В конце концов вы можете какую-то «частную» функцию
запрограммировать и сами.
Далее идет программный аналог (отображение) форм Бэкуса-Наура (рекурсивные функции fact, term, expr). Программа бешено крутится, ныряя в эти функции. Интересно было бы знать момент этих движений (это конечно шутка, см. классическую и квантовую механику).
Насчет выполняемых действий. По ходу дела можно было бы сразу вычислять выражение (формулу). Но я предпочел записывать все обработанные лексемы в строку с обратной польской записью. Через разделитель, роль которого выполняет пробел. Зачем? Для «разделения полномочий». Может мы захотим потом не вычислить результат, а сделать что-нибудь другое. Строка с обратной польской записью будет удобным входным выражением для дальнейшей обработки.
Обратим внимание, что перед очередным вызовом сканера нужно обязательно спасать содержимое строки Lex в другой строке.
Потом функция PostFix будет обрабатывать эту обратную
польскую строку и вычислять выражение. Результат будет в текстовом файле Result.txt (как и сама польская строка). Да,
кстати, хотя исходные числа – целые, результат вычисляется в виде
действительного числа.
Что такое обратная польская запись, я здесь не поясняю. Приведу лишь простейший пример.
Выражение в обычной записи:
3+2
Теперь в обратной польской:
3, 2, +
(разделителем служит запятая).
А как
обработать «польскую» строку (ОПЗ – обратную польскую запись) и все вычислить?
Процитирую статью из Интернета:
Для реализации
алгоритма используется стек для чисел (или для переменных, если они
встречаются в исходном выражении). Алгоритм очень прост. В качестве входной
строки мы теперь рассматриваем выражение, записанное в ОПЗ:
1. Если очередной символ входной строки - число, то кладем его в стек.
2. Если очередной символ - знак операции, то извлекаем из стека два верхних
числа, используем их в качестве операндов для этой операции, затем кладем
результат обратно в стек.
Когда вся входная строка будет разобрана в стеке должно остаться одно число,
которое и будет результатом данного выражения.
Таким образом нужен стек. Его мы запрограммируем сами. Для работы со стеком я также использую свои, ранее написанные функции (смотри их в тексте – по названию можно понять, что они делают). Отмечу, что создается стек для 100 лексем максимум по сто символов в каждой. И занимает он чуть более 10000 байт.
Вот программа (для Visual C++ 5.0, файл recurs1.cpp, нужны еще файлы библиотек с моими «личными» функциями):
/***************************************/
#include <stdio.h>
#include <stdlib.h>
#include "Str_ex.h"
#include "QnS.h"
int
I=0;
int
n=5;
char Lex[150]; /* Это для лексем */
char Res[250]; /* Это для результирующей постфиксной
польской строки */
char End[3]; /* Это конец строки в текстовом файле */
char Sign1[2]={43,0};
char
Sign2[2]={45,0};
char
Sign3[2]={42,0};
char
Sign4[2]={47,0};
/******************************/
/* sprintf(A,"n=%d",n);*/
/******************************/
/* Это - обработка формулы
со сложением-вычитанием и
умножением-делением.
Результат - в польской постфиксной
записи */
int J=1;
void NextLexema() /* Получает очередную лексему */
{
int R;
*Lex=0;
R=FindStrN("Pr.txt",End,Lex,100,J);
J++;
if(R<0)
{
*Lex=0;
WrStr("Lexema.txt",End," THE END! ",1); /* В тестовых
целях
пишем в файл */
return;
}
else
{
WrStr("Lexema.txt",End,Lex,1); /* В тестовых целях
пишем в файл */
};
}
void fact() /* Это множитель - конечный пункт рекурсии */
{
if(testnum_l(Lex)==0&&(*Lex>47&&*Lex<58)) /* Проверка - является ли целым числом */
{
StrCat(Lex,Res);
StrCat(" ",Res);
NextLexema();
}
else
{
CpStr("ERROR",Res);
};
}
void term() /* Обработка умножения-деления */
{
char
Lex1[150];
Lex1[0]=0;
fact();
/*while(COMPstr("*",Lex)==0||COMPstr("/",Lex)==0)*/
while(*Lex==42||*Lex==47)
{
CpStr(Lex,Lex1);
NextLexema();
fact();
StrCat(Lex1,Res);
StrCat(" ",Res);
}
}
void expr() /* Обработка сложения-вычитания */
{
char
Lex1[150];
Lex1[0]=0;
term();
/*while(COMPstr("+",Lex)==0||COMPstr("+",Lex)==0)*/
while(*Lex==43||*Lex==45)
{
CpStr(Lex,Lex1);
NextLexema();
term();
StrCat(Lex1,Res);
StrCat(" ",Res);
}
}
/********************************/
/* Обработка строки с польской обратной
записью */
int
iPF=1;
int
PostFix(char *S,int L,int N,char *Dest)
{
void * pSt;
char St[100];
int i,res;
int iPF1;
int iPF2;
int iPF3;
char *S1;
void *pS1;
/*char S2[50];
char S3[50];
char S4[100];*/
int r=0;
double F1,F2,F3;
if(*S==0)
{
WrStr("PostFix.txt",End,"Empty!",1);
return -2;
}
pS1=malloc(L);
if(pS1==NULL)
{
return
-1;
}
S1=(char *)pS1;
*S1=0;
/*WrStr("PostFix.txt",End,"Coming",1);*/
pSt=CreateStack(L*N);
while(iPF>0)
{
/*WrStr("PostFix.txt",End,"Cycle",1);*/
iPF1=CpWordN(S,S1,32,iPF);
if(iPF1<0)
{
break;
}
iPF++;
if(!(COMPstr(S1,Sign1)==0||COMPstr(S1,Sign2)==0||COMPstr(S1,Sign3)==0||COMPstr(S1,Sign4)==0))
/* Если символ не знак, помещаем в стек */
{
for(i==0;i<100;i++)
*(St+i)=0;
CpStr(S1,St);
res=AddArrayToStackNoPart(pSt,St,100);
if(res!=100)
{
r=-3;
WrStr("PostFix.txt",End,"Stack
error!",1);
}
}
else /* Если символ - знак */
{
for(i==0;i<100;i++) *(St+i)=0;
res=GetArrayFromStack(pSt,St,100);
if(res!=100)
{
r=-4;
WrStr("PostFix.txt",End,"Stack
error (getting)!",1);
}
F1=atol(St);
for(i==0;i<100;i++) *(St+i)=0;
res=GetArrayFromStack(pSt,St,100);
if(res!=100)
{
r=-5;
WrStr("PostFix.txt",End,"Stack
error (getting)!",1);
}
F2=atol(St);
if(COMPstr(S1,Sign1)==0) /* Если сложение */
{
F3=F2+F1;
}
if(COMPstr(S1,Sign2)==0) /* Если вычитание */
{
F3=F2-F1;
}
if(COMPstr(S1,Sign3)==0) /* Если умножение */
{
F3=F2*F1;
}
if(COMPstr(S1,Sign4)==0) /* Если деление */
{
F3=F2/F1;
}
sprintf(St,"%f",F3);
/*Кладем результат в стек*/
for(i==0;i<100;i++) *(St+i)=0;
res=AddArrayToStackNoPart(pSt,St,100);
if(res!=100)
{
r=-6;
WrStr("PostFix.txt",End,"Stack
error!",1);
}
}
}
/*Извлекаем из стека результат*/
for(i==0;i<100;i++) *(St+i)=0;
res=GetArrayFromStack(pSt,St,100);
if(res!=100)
{
r=-7;
WrStr("PostFix.txt",End,"Stack
error (getting)!",1);
}
*S1=0;
StrCat(St,S1);
WrStr("PostFix.txt",End,"Result
in stack: ",1);
WrStr("PostFix.txt",End,S1,1);
/* Конец извлечения результата из стека*/
CpStr(S1,Dest);
DeleteStack(pSt);
free(pS1);
return r;
}
/*******************/
void
main(void)
{
Lex[0]=0;
Res[0]=0;
End[0]=13;
End[1]=10;
End[2]=0;
char dest[200];
NextLexema();
expr(); /* Это вход в разбор формулы */
WrStr("Result.txt",End,Res,1); /* Записываем результирующую
польскую постфиксную строку
в файл */
PostFix(Res,100,100,dest);
WrStr("Result.txt",End,"А число:",1);
WrStr("Result.txt",End,dest,1);
return;
}
/****************************************/
Здесь – конец программы.
Да, кстати, обратим внимание на строчку (вызов функции) PostFix(Res,100,100,dest);
У меня все работало на Win2000, но в 98-м Windows работать отказалось. Какой-то загадочный глюк. Пришлось оба параметра убрать, и создавать стек внутри функции с заданными в тексте функции параметрами (100*100=10000).
И наконец в качестве напоминания самому себе – это проект Gramm1.