Обратная пользовательская запись в языке Си

- 2 -

ОГЛАВЛЕНИЕ

Введение

1. Анализ существующих методов решения задачи

2. Детальное описание используемых методов

3. Описание программы

3.1 Постановка задачи

3.2 Интерфейс пользователя

3.3 Детальное описание основной функции

3.4 Детальное описание функции ChartoInt

3.5 Детальное описание функции Scobka

3.6 Детальное описание функции Sumin

3.7 Общая структура программного средства

4. Блок схема программы

4.1 Основная блок схема

4.2 Блок схема функции ChartoInt

4.3 Блок схема функции Sumin

4.4 Блок схема функции Scobka

5. Заключение

6. Программная поддержка

7. Список литературы

8. Приложение 1

9. Приложение 2

Введение

Язык "C" является универсальным языком программирования. Язык "C" - это язык относительно "низкого уровня". Это означает, что "C" имеет дело с объектами того же вида, что и большинство ЭВМ, а именно, с символами, числами и адресами. Они могут объединяться и пересылаться посредством обычных арифметических и логических операций, осуществляемых реальными ЭВМ.

В языке "C" отсутствуют операции, имеющие дело непосредственно с составными объектами, такими как строки символов, множества, списки или с массивами, рассматриваемыми как целое. Язык не предоставляет никаких других возможностей распределения памяти, кроме статического определения и механизма стеков, обеспечиваемого локальными переменных функций; здесь нет ни "куч"(heap), ни "сборки мусора". Наконец, сам по себе "C" не обеспечивает никаких возможностей ввода-вывода: здесь нет операторов read или write и никаких встроенных методов доступа к файлам. Все эти механизмы высокого уровня должны обеспечиваться явно вызываемыми функциями.

Аналогично, язык "C" предлагает только простые, последовательные конструкции потоков управления: проверки, циклы, группирование и подпрограммы, но не мультипрограммирование, параллельные операции, синхронизацию или сопрограммы. Язык "C" не является языком со строгими типами в смысле паскаля.

Наконец, язык "C", подобно любому другому языку, имеет свои недостатки. Некоторые операции имеют неудачное старшинство; некоторые разделы синтаксиса могли бы быть лучше; существует несколько версий языка, отличающихся небольшими деталями. Тем не менее, язык "C" зарекомендовал себя как исключительно эффективный и выразительный язык для широкого разнообразия применений программирования. [1]

Одной из главных причин, лежащих в основе появления языков программирования "высокого уровня", явились вычислительные задачи, требующие больших объёмов рутинных вычислений. Поэтому к языкам программирования предъявлялись требования максимального приближения формы записи вычислений к естественному языку математики. В этой связи одной из первых областей системного программирования сформировалось исследование способов трансляции выражений. Наибольшее распространение получил метод трансляции с помощью обратной пользовательской записи. [4] Методы решения задачи использования обратной пользовательской записи детально рассмотрены в данной курсовой работе.

1. Анализ существующих методов решения задачи

Существует множество решений данной задачи. На данный момент нам известно 3 метода решения задачи. 1 - с использованием стека, 2 - это, так называемое двойное использование стека, 3 - метод использование массивов.

Для сравнения приведу один из примеров использования стека для решения данной задачи:



Очевидно, что одним из недостатков данного метода является сложность использования методов, которые без преувеличения можно назвать устаревшими.

Так как сегодня стек используется при помощи классов. Рассмотрим пример использования стека при помощи классов:

class Stek

{ int something;

public:

Stek(); // конструктор

~Stek(); // деструктор

void pop (int); // поместить

int push(void); // вытащить

void print(); // распечатать

}

Использование стека эффективно вследствии того, что в ассемблере не эффективно использовались массивы и имеются регистры стека:

ss - сегментный регистр стека,

sp/esp- регистр указателя стека,

bd/ebd- регистр указателя базы кадра стека,

Следовательно, реализация массивов через стек была очень эффективна. Теперь же эта проблема не критична для разработки программ, так как производительность ЭВМ велика. В С++ "свободно" используются массивы. В языках "среднего" и "высокого" уровня использование стека не принесёт значимого ускорения, а даже может замедлить выполнение программы. Вследствии того, что поддежка реализация стека на аппаратном уровне в языке Си ++ отсутствует, команды pop и push реализуются через функции или классы(см. пример использования стека при помощи классов).[6] К тому же использование массивов более удобно, чем использования стека, а так же легко переносимо на другие языки программирования и довольно просто для понимания.

2. Детальное описание используемых методов

Рассмотрим детальное описание используемых методов на примере задачи реализации калькулятора при помощи метода обратной пользовательской записи.

В программе вводится строка символов

Пример: (1+1)/2+12/(8/2)=

Программе необходимо оценить состав строки. Это реализуется через различные циклы, которые определяют, является ли i-символ цифрой или знаком, затем скомпоновывают цифры в числа и конечным результатом этих действий, являются 2 массива.

Пример:

Далее программа должна распознать все выражения в скобках и преобразовать их в числовое значение.

Пример: …+(1+2/2)/… …+2/…

Для решения данной задачи, необходимо использовать сдвиги (детально описано в разделе 3.5)

Когда же все скобки будут преобразованы в числовые значения, программа начинает преобразовывать все выражения "*" - умножение, затем "/" - деление, затем "+" - сложение и, наконец "-" - вычитание в числовые значения.

Пример:

И в конце программа выдаёт ответ.

Детально работа функций описана в следующем разделе.

3. Описание программы

3.1 Постановка задачи

С клавиатуры вводится математическое выражение в виде строки символов а) числовых - 1234567890 и б) специальных */+-()= . В конце выражения ставится `=' или ничего(/0 - терминатор ноль). Программа оценивает выражение и если ошибок нет - выдаёт целочисленный результат.

3.2 Интерфейс пользователя

В начале программы выводится диалог выбора режима работы: отладочный или простой:

Do you want to look the debugging information? (y/Any key)

Если же будет нажата любая клавиша кроме `y', то включится простой режим работы. Отладочный режим рассматриваться не будет.

Далее показывается логотип и информация об авторе. После всего этого выводится строка нумерации расчёта:

<<<-------------[ Расчёт N:1 ]------------->>>

И на следующей строке пользователь пишет некоторое выражение:

1+1+(555/111)/5+(3/3+6/6+9/9)=

Или

1+1+(555/111)/5+(3/3+6/6+9/9)

Программа оценит выражение и в случае отсутствия ошибок, выдаст целочисленный результат:

----------------------------

OTBET = 10

----------------------------

и выведет диалог повторения:

3AHOBO? (Any key/n)

Если пользователь нажмёт `n' или `N', то работа программы завершится. Если же будет нажата любая другая клавиша, то цикл повторится:

<<<-------------[ Расчёт N:2 ]------------->>>

И так далее.

Вывод результатов проиллюстрирован в приложении 2.

3.3 Детальное описание основной функции

Перейдём непосредственно к рассмотрению методов решения данной задачи.

В программе вводится строка символов, например : (1+1)/2+12/(8/2)=

Программа сканирует данную строчку с помощью scanf("%s",&S);

Далее необходимо определить состав строки:

for (i=0; i<(m+1); i++){

if (S[i]=='1'){ buf[i]=1;l++;}

else if (S[i]=='2'){ buf[i]=2;l++;}

else if (S[i]=='3'){ buf[i]=3;l++;}

else if (S[i]=='4'){ buf[i]=4;l++;}

else if (S[i]=='5'){ buf[i]=5;l++;}

else if (S[i]=='6'){ buf[i]=6;l++;}

else if (S[i]=='7'){ buf[i]=7;l++;}

else if (S[i]=='8'){ buf[i]=8;l++;}

else if (S[i]=='9'){ buf[i]=9;l++;}

else if (S[i]=='0'){ buf[i]=0;l++;}

else if (l!=0)

С помощью функции ChartoInt преобразуем набор цифр в число, пример: 1,2,4 в 124.

a[iKol]=ChartoInt (p,i,l);

iKol++; //счетчик кол-ва чисел

l=0;//обнуление счетчика длинны числа

}}

Далее проводится вылавливание знака

switch (S[i]) {

case '+' :b[k]=1; k++; break;

case '-' :b[k]=2; k++; break;

case '*' :b[k]=3; k++; break;

case '/' :b[k]=4; k++; break;

case '\0' : break; //Завершение сканирования если '\0'

case '(' :b[k]=5; u1++; k++; break;

case ')' :b[k]=6; u2++; k++; break;

default : break;}

Если встречаем "=" то завершаем сканирование

if(S[i]=='=') { break;} // Завершение сканирования

Если количество открытых скобок не равно количеству закрытых скобок то выход

if(u1!=u2){goto m1;} // Проверка на кол-во скобок

Если всё нормально, то используем функцию Scobka

Scobka(a1,b1,iKol,k);

После расчётов выражений в скобках продолжаем расчёт в функции Sumin

c=Sumin(a1,b1,iKol,k);

Получаем результат и переводим его в целое значение s=(int)c;

И выводим результат

printf("\r OTBET=[ %i ]\n",s);

Рассмотрим работу функций: ChartoInt , Scobka, Sumit.

3.4 Детальное описание основной функции ChartoInt

Функция ChartoInt преобразует набор символов из строки, набранной пользователем в числа. Преобразование происходит следующим образом, имеем некоторые символы XYZ, программа преобразует их так:

Определяется разрядность числа, скажем сотни, следовательно, 1 число умножается на 100 + следующее число, умноженное на 10 + следующее число, умноженное на 1.

Пример:

x,y,z x*100+y*10+z*1 = xyz

1,2,3 1*100+2*10+3*1 = 123

3.5 Детальное описание основной функции процедуры Scobka

Функция Scobka преобразует все выражения в скобках в числа, например (2+4/2) будет преобразовано в 4.

Получаем массив данных и знаков через указатели, сканируем массив знаков на открытые и закрытые скобки и обозначаем начало скобок через N, а конец через N1. Числа и знаки, входящие в этот промежуток, образуют два новых массива данных и знаков, но уже без скобок, после чего вызывается функция Sumin и возвращается численное значение скобок, которое вставляется в исходный массив чисел с проведением сдвига данных и чисел.

Пример:

Как мы видим, вначале раскрывается 1 скобка, выражение в ней рассчитывается и следовательно в массивах значений и чисел происходит сдвиг. Затем тоже проделывается со второй скобкой. В конце мы имеем массив значений состоящий только из знаков +, -, * и /.

3.6 Детальное описание основной функции процедуры Sumin

Функция Sumin производит компоновку числовых и знаковых массивов с использованием приоритета операций и последуйщего расчёта результата.

Т.е в выражении последовательно выполняются все операции, сперва с умножением "*", затем с делением "/", затем с сложением "+" и затем с вычитанием "-".

Пример: 12+2*7-10/2 12+14-10/2 12+14-5 6-5 21

Детально работа функций описана в приложении 1.

3.7 Общая структура программного средства

- 2 -

4. Блок схема

4.1 Основная блок схема

- 2 -



- 2 -



- 2 -

4.2 Блок схема функции ChartoInt

- 2 -

4.3 Блок схема функции Sumin

- 2 -



- 2 -

4.4 Блок схема функции Scobka

- 2 -



- 2 -



- 2 -

5. Заключение

Данный метод не является оптимальным, так как:

· Не использует классы.

· "Сдвиг" не вынесен в отдельную функцию, что затрудняет модернизацию.

· Сложность при попытке включения вложенных скобок

· Сложность при попытке включения математических операций таких как cos(), sin(), степень и другие.

· Строгое ограничение числового диапазона расчётов

· Отсутствие "дружественного" - оконного интерфейса.

Возможное решение данных проблем - это переход на другую платформу, Microsoft® Visual C++ или Borland® Delphi.

Приложение 1

Основной код программы

#include <stdio.h>

#include <conio.h>

#include <string.h>

#include <math.h>

int ChartoInt (int*,int,int);

double Sumin (int*,int *,int ,int );

void Scobka (int*,int *,int ,int );

char OTLADKA[1];

void main (void)

/*======================[Начало]=======================*/

{

char S[125];

int i, iKol,m, buf[125],a[100],b[100],k,*p,l,*a1,*b1,u1,u2,s,ABC;

double c;

mr:

puts("Do Want to look the debugging information? (y/Any key)");

if (getch()!='y') {puts("Debugging information OFF"); OTLADKA[1]='N'; }

else {puts("Debugging information ON");printf("\a"); OTLADKA[1]='Y'; }

ABC=1;

…

m1:

printf("\rЭ <<<-------------[ Расчёт N:%i ]------------->>> Э \n",ABC);

scanf("%s",&S);

…

if (OTLADKA[1]=='Y') printf("\n**** Отладочная информация *****\n");

m=strlen(S);

p=buf;a1=a; b1=b; //указатели

k=0;iKol=0;l=0;u1=0;u2=0;

/*Получение числа спомощью функции и запись в массив а, где l-счетчик-длинны числа*/

for (i=0; i<(m+1); i++)

{

if (S[i]=='1'){ buf[i]=1;l++;}

else if (S[i]=='2'){ buf[i]=2;l++;}

else if (S[i]=='3'){ buf[i]=3;l++;}

else if (S[i]=='4'){ buf[i]=4;l++;}

else if (S[i]=='5'){ buf[i]=5;l++;}

else if (S[i]=='6'){ buf[i]=6;l++;}

else if (S[i]=='7'){ buf[i]=7;l++;}

else if (S[i]=='8'){ buf[i]=8;l++;}

else if (S[i]=='9'){ buf[i]=9;l++;}

else if (S[i]=='0'){ buf[i]=0;l++;}

else { if (l!=0) {

a[iKol]=ChartoInt (p,i,l);

iKol++; //счетчик кол-ва чисел

l=0; //обнуление счетчика длинны числа

}

}

/*Вылавливание знака и присваивания ему номера 1-6 */

switch (S[i]) {

case '+' :b[k]=1; k++; break;

case '-' :b[k]=2; k++; break; // к-счетчик кол-ва знаков

case '*' :b[k]=3; k++; break;

case '/' :b[k]=4; k++; break;

case '\0' : break; //Завершение сканирования если конец

case '(' :b[k]=5; u1++; k++; break;

case ')' :b[k]=6; u2++; k++; break;

default :break;}

if(S[i]=='=') { break;} // Завершение сканирования

}

if(u1!=u2){goto m1;} // Проверка на кол-во скобок

Scobka(a1,b1,iKol,k); // получение ответа

c=Sumin(a1,b1,iKol,k);// присваивание ответа

s=(int)c; // округление до целого числа

if (OTLADKA[1]=='Y') printf("\n ***** OTLADKA INFO [END]*******\n");

puts("Э ---------------------------- Э");

printf("\r OTBET=[ %i ]\n",s); // вывод ответа

puts("Э ---------------------------- Э");

printf("\ [ 3AHOBO? (Any key/n) ]\r"); if (getch()!=='n') {goto m1;}

…

}

}

/*==================[Конец программы]==================*/

int ChartoInt (int *p, int i, int l)

{

int a,j,b,b2,m;

a=0;

m=i+1-l;//Вычисление начала работы с массивом данных xx>[m]YYY>xxx

for (j=m; j<= (i+1); j++) // `1 2 3' => 100+20+3=123

{

b=pow(10,(i-j)); //кол-во нулей

b2=p[j-1]; // извлекаемая цифра

a=a+(b2*b); //число1+ число2+… числоN= число

}

return (a);

}

double Sumin (int *pa1,int *pb1,int j,int k)

{

int i, buf1,l;

double s;

/* начало сканирования массива данных и чисел с опредилением приоретета */

for (i=0;i<=(k+1); i++)

{

if ( pb1[i]==3) //"*"

{

buf1=pa1[i]*pa1[i+1];//умножение x*y

pa1[i]=buf1; //присвоение нового числа

for(l=(i+1);l<=(j+1);l++) //сдвиг на кол-во xxx-cc*dd

{

pa1[l]=pa1[l+1]; // сдвиг цифр

if (l==j)

{

pa1[l+1]=0;

pa1[j-1]=0;//для всех

l++;

j--; //уменьшение для того, чтобы цикл не съел знаки и числа

//X*Y-u X*Y=a => <a>-<u> "-"съелся

}

}

for(l=i;l<=(k+1);l++)

{

pb1[l]=pb1[l+1]; //сдвиг знаков

if (l==k)

{

pb1[l+1]=0;

l++;

k--;// уменьшение для того, чтобы цикл не съел знаки и числа

i--; // уменьшение для того, чтобы цикл не съел знаки и числа }

}

}

if ( pb1[i]==4) //"/"

{

buf1=pa1[i]/pa1[i+1];

pa1[i]=buf1;

for(l=(i+1);l<=(j+1);l++)

{

pa1[l]=pa1[l+1];

if (l==j)

{

pa1[l+1]=0;

l++;

j--;

}

}

for(l=i;l<=(k+1);l++)

{

pb1[l]=pb1[l+1];

if (l==k)

{

pb1[l+1]=0;

l++;

k--;

i--;

}

}

}

}

s=pa1[0];

l=0;

for (i=0; i<=(k+1);i++)//Выполнение действий согласно знаку

{

if (pb1[l]==1) //"+"

{

s=s+pa1[i+1];

l++;

}

else if (pb1[l]==2) //"-"

{

s=s-pa1[i+1];

l++;

}

}

int j1=0;

return (s);

}

void Scobka (int *a1,int *b1,int l,int k1)

{

int i,n,n1,j,array[126],barray[126],*par,*pbr,iShift,p,j3,iPar,iSk;

double c1;

int as,as1;//для отладки

par=array;// указатели на массивы для передачи в функцию

pbr=barray;

iPar=0; iSk=0;

for (i=0;i<=k1;i++)//основной цикл

{

if (b1[i]==5)//поиск скобок открытых

{

if (iPar==0) n=i; // указывает на начало скобок

iPar++;

}

if (b1[i]==6) //поиск скобок закрытых

{

if (iPar!=1)

{

iPar--;

iSk++;

continue;

}

n1=i;// указывает на конец скобок

p=0;//индекс для новых массивов

for(j=n;j<n1;j++)

{

array[p]=a1[j]; //создание временных массивов чисел

p++;

as=p; //для отладки

}

p=0;

for(j=(n+1);j<n1;j++)

{

barray[p]=b1[j];//создание временных массивов знаков

p++;

as1=p; //для отладки

}

if(iSk!=0)

{

if (OTLADKA[1]=='Y') Scobka(par,pbr,as,as1);

}

iShift=n1-n; //"Сдвиг"следует обратить внимание - 1

c1=Sumin(par,pbr,iShift,(iShift-1)); //возвращаемая сумма в скобках

if (OTLADKA[1]=='Y') printf("\n Разное количество скобок N=%f\n",c1);

a1[n]=(int)c1;

for(j3=0;j3<=iShift;j3++) //очистка массивов возможно ненужна

{

par[j3]=0;

pbr[j3]=0;

}

/*====================[сдвиг]==========================*/

if(l>n1)//l-количество чисел в массиве a1 если за скобками ничего нет то для упращения не нужно

{

for(j=(n+1);j<l;j++)

{

a1[j]=a1[j+iShift-1]; //сдвиг чисел

if (j==(l-iShift+1)) //учтено что массив начинается с нуля и точто сдвиг-1

{

for (j3=(l-iShift+1);j3<l;j3++) //обнуление вышедших за предел данных

{

a1[j3]=0;

}

j=l; //Выход из сдвига цикла для массива чисел

}

} //закрытия цикла сдвига чисел

l-=(iShift-1); //количество чисел уменьшилось

for(j=n;j<k1;j++)

{

b1[j]=b1[j+iShift+1]; //сдвиг знаков

if (j==(k1-iShift-2))

{

for (j3=(k1-iShift-1);j3<k1;j3++) //обнуление вышедших за предел данных

{

b1[j3]=0;

}

j=k1;//Выход из сдвига массива }

}

k1-=(iShift+1); //количество знаков уменьшилось

i=0; //пробежать цикл с начала

}//закрывает скобки проверки на на необходимость сдвига

else if(l==n1)

{

a1[n+1]=0;

b1[n]=0;

}

}

}

}

Приложение 2

Вывод результатов.