Обратная пользовательская запись в языке Си (стр. 1 из 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);