Теоретические исследования

ОТЧЕТ

По лабораторной работе № 2

«Калькулятор»

по дисциплине «Методы программирования»

Выполнил

студент гр. xxxxx/x И.И. Иванов

<подпись>

Проверил

В. Б. Вагисаров

<подпись>

Санкт-Петербург

Формулировка задания

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

Требования к программе:

- программа НЕ ИМЕЕТ меню. Она сразу после ввода принимает и немедленно обрабатывает единственный параметр (строку со скобочной последовательностью).

- После подсчета значения выражения выводится ответ в десятичном виде БЕЗ каких-либо иных слов - только результат разбора выражения ЛИБО фраза "wrong format" в том случае, если последовательность синтаксически неверная

- числа могут быть со сист. счисления до 16. Числа записываются либо как xyz..za_<какая система счисления>, либо без указания системы счисления, если число десяточное.

- гарантируется, что числа, в какой бы они ни были системе отсчета, помещаются в long int

- поддерживается 5 операций (+-*/%), приоритет повышается слева направо.

- Делать нужно через построение обратной польской записи и с реализацией стека

ТЕОРЕТИЧЕСКИЕ ИССЛЕДОВАНИЯ

Стек— абстрактный тип данных, представляющий собой список элементов, организованных по принципу LIFO (англ. last in — first out, «последним пришёл — первым вышел»).

Зачастую стек реализуется в виде однонаправленного списка (каждый элемент в списке содержит помимо хранимой информации в стеке указатель на следующий элемент стека).

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

При организации стека в виде однонаправленного списка значением переменной стека является указатель на его вершину — адрес вершины. Если стек пуст, то значение указателя равно NULL.

Рис. 1— Организация стека в виде однонаправленного списка

Возможны три операции со стеком: добавление элемента (иначе проталкивание, push), удаление элемента (pop) и чтение головного элемента (peek).

При проталкивании (push) указывается новый элемент, указывающий на элемент, бывший до этого головой. Новый элемент теперь становится головным.

При удалении элемента (pop) убирается первый, а головным становится тот, на который был указатель у этого объекта (следующий элемент). При этом значение убранного элемента возвращается.

Преобразование выражения в ОПЗ:

  • Пока есть ещё символы для чтения:

· Читаем очередной символ.

· Если символ является числом, добавляем его к выходной строке.

· Если символ является символом функции, помещаем его в стек.

· Если символ является открывающей скобкой, помещаем его в стек.

· Если символ является закрывающей скобкой:

До тех пор, пока верхним элементом стека не станет открывающая скобка, выталкиваем элементы из стека в выходную строку. При этом открывающая скобка удаляется из стека, но в выходную строку не добавляется. Если после этого шага на вершине стека оказывается символ функции, выталкиваем его в выходную строку. Если стек закончился раньше, чем мы встретили открывающую скобку, это означает, что в выражении либо неверно поставлен разделитель, либо не согласованы скобки.

Если символ является оператором о1, тогда:

1) пока…

… (если оператор o1 право-ассоциированный) приоритет o1 меньше приоритета оператора, находящегося на вершине стека…

… (если оператор o1 ассоциированный, либо лево-ассоциированный) приоритет o1 меньше либо равен приоритету оператора, находящегося на вершине стека…

… выталкиваем верхние элементы стека в выходную строку;

2) помещаем оператор o1 в стек.

· Когда входная строка закончилась, выталкиваем все символы из стека в выходную строку. В стеке должны были остаться только символы операторов; если это не так, значит в выражении не согласованы скобки.

Результаты работы

Вычисление выражений происходит с помощью обратной польской записи. Наибольшие затруднения в процессе написания работы вызывал унарный минус. Число -5 по сути представляет собой выражение «0 – 5». Поэтому при встрече унарного минуса в строке мы помещаем в выходную строку 0 и 5, а в стек помещаем минус, который не выталкивает никакие предыдущие знаки операций из стека.

Рис.2. – Работа калькулятора.

Рис.3. – Работа калькулятора.

Рис.4. – Контроль ошибок.

ВЫВОды

Таким образом, в данной лабораторной работе был разработан простейший целочисленный калькулятор с возможностью вычисления 5 операций над числами(+-%/*). После подсчета значения выражения выводится ответ в десятичном виде без каких-либо иных слов - только результат разбора выражения либо фраза "wrong format" в том случае, если последовательность синтаксически неверная .

Алгоритм действия основан на использования обратной польской записи и стека - абстрактного типа данных, представляющего собой список элементов, организованных по принципу LIFO.

ПРИЛОЖЕНИЕ

#include <stdio.h>

#include <conio.h>

#include <locale>

#include <math.h>

#include <string.h>

#include <stdlib.h>

#define M 4096

typedef struct STACK{

long int data;

STACK *next;

}STACK;

struct STACK * push(struct STACK * top, long int x)

{

STACK *tmp = (STACK*)malloc(sizeof(STACK));

tmp->data = x;

tmp->next = top;

return(tmp);

}

long int pop(STACK ** top)

{

STACK *vr;

long int a;

if (*top == NULL) return '\0';

else

{

vr = *top;

a = vr->data;

*top = vr->next;

vr->next = NULL;

free(vr);

return a;

}

}

void print_s(struct STACK *top)

{

if (top == NULL) return;

else

{

long int k = 0;

char f = 0;

k = pop(&top);

f = (char)k;

putchar(f);

print_s(top);

}

}

void print_n(struct STACK *top)

{

if (top == NULL) return;

else

{

long int k = 0;

k = pop(&top);

printf("%i ", k);

print_n(top);

}

}

long int get_ch(unsigned int & p, char *str,bool &error)//Получает индекс, с которого начинается число в строке, и указатель на первый элемент в строке, переводит его в дестичную систему счисления

{

long int new_numb = 0, ct = 0, z = 0, z1 = 0;

unsigned int i = p;

int syst_check = 0;

int numb[100];

int sist = 0;

while (str[i] != '(' && str[i] != ')' && str[i] != '/' && str[i] != '*' && str[i] != '%' && str[i] != '+' && str[i] != '-' && syst_check == 0 && i < strlen(str))

{

if (str[i] == '_')

{

i++;

while (str[i] != '(' && str[i] != ')' && str[i] != '/' && str[i] != '*' && str[i] != '_' && str[i] != '%' && str[i] != '+' && str[i] != '-' && i < strlen(str))

{

sist = sist * 10 + str[i] - 48;

i++;

}

syst_check++;

}

else

{

if (str[i] == 'A' || str[i] == 'a') numb[ct] = 10;

else if (str[i] == 'B' || str[i] == 'b') numb[ct] = 11;

else if (str[i] == 'C' || str[i] == 'c') numb[ct] = 12;

else if (str[i] == 'D' || str[i] == 'd') numb[ct] = 13;

else if (str[i] == 'E' || str[i] == 'e') numb[ct] = 14;

else if (str[i] == 'F' || str[i] == 'f') numb[ct] = 15;

else numb[ct] = str[i] - 48;

i++;

ct++;

}

}

if (sist == 0) sist = 10;

if (sist > 1 && sist < 17)

{

for (int k = 0; k < ct; k++)

{

if (numb[ct - k - 1] < sist && numb[ct - k - 1] >= 0 && error==0)

{

z = pow(sist, k);

z1 = numb[ct - k - 1];

new_numb += z*z1;

}

else

{

error = 1;

printf("wrong_format\n");

p = i - 1;

break;

}

}

}

else

{

error = 1;

printf("wrong_format\n");

}

p = i - 1;

return(new_numb);

}

int proverka(char *str)

{

int bracket_ct = 0;

int dl = strlen(str);

char symb[5]{ '+', '*', '/', '%', '-' };//Массив символов допустимых операций.

char numb[23]{ '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f', 'A', 'B', 'C', 'D', 'E', 'F', '_'};//Массив символов для описания чисел.

if (str[0] == '+' || str[0] == '/' || str[0] == '*' || str[0] == '%' || str[0] == ')' || (str[0] == '(' && str[1] == ')')) return(0);//Проверка первого элемента строки, так как не обрабатывается последующим алгоритмом

if (str[0] == '(') bracket_ct++;

for (unsigned int k = 1; k < dl - 1; k++)

{

int z = 0;

if (str[k] == '(')

{

for (int ct = 0; ct < 22; ct++)//Перед открывающей скобкой не должно быть числа...

if (str[k - 1] == numb[ct]) return(0);

if (str[k - 1] == ')') return(0);//...и закрывающей скобки.

for (int ct = 0; ct < 4; ct++)//После открывающей скобки не должно стоять знаков операций(кроме минуса, унарного) ...

if (str[k + 1] == symb[ct]) return(0);

if (str[k + 1] == ')') return(0);//...и закрывающей скобки.

}

else if (str[k] == ')')

{

for (int ct = 0; ct < 22; ct++)//После закрывающей скобки не должно быть числа...

if (str[k + 1] == numb[ct]) return(0);

if (str[k + 1] == '(') return(0);//...и открывающей скобки.

for (int ct = 0; ct < 5; ct++)//Перед закрывающей скобкой не должно стоять знаков операций ...

if (str[k - 1] == symb[ct]) return(0);

if (str[k - 1] == '(') return(0);//...и открывающей скобки.

}

else if (str[k] == '+' || str[k] == '-' || str[k] == '/' || str[k] == '%' || str[k] == '*')

{

for (int ct = 0; ct < 5; ct++)//Перед символом операции не должно быть еще одного символа операции...

if (str[k - 1] == symb[ct]) return(0);

for (int ct = 0; ct < 5; ct++)

if (str[k + 1] == symb[ct]) return(0);//...и после.

if (str[k - 1] == '(' && str[k] != '-') return(0);//Перед символом операции не должно быть открывающей скобки(исключение для унарного минуса) ...

if (str[k + 1] == ')') return(0);//...и закрывающей(без исключений).

}

else

{

bool prov = 0;

for (int z = 0;z<23;z++)

if(str[k] == numb[z]) prov=1;//Проверка элемента, в случае если он не является скобкой или операцией, на допустимость.

if (prov == 0)

{

return(0);

}

}

if (str[k] == '(') bracket_ct++;//Проверка правильности расположения открывающей и закрывающей скобок...

if (str[k] == ')') bracket_ct--;

if (bracket_ct < 0) return(0);//...на расположение относительно друг друга...

}

if (str[dl-1] == '+' || str[dl - 1] == '/' || str[dl - 1] == '*' || str[dl - 1] == '%' || (str[dl - 2] == '(' && str[dl - 1] == ')'))return(0);

if (str[dl-1] == '(') bracket_ct++;

if (str[dl-1] == ')') bracket_ct-=1;

if (bracket_ct != 0) return(0);//...и количество.

return(1);

}

long int preobr(long int oper, long int ch_1, long int ch_2)

{

long int rez = 0;

if (oper == 42) rez = ch_1 * ch_2;

else if (oper == 43) rez = ch_1 + ch_2;

else if (oper == 45) rez = ch_1 - ch_2;

else if (oper == 47) rez = ch_1 / ch_2;

else if (oper == 37) rez = ch_1 % ch_2;

return(rez);

}

void calc(struct STACK **symb, struct STACK **numb, bool &error)

{

long int first_ch = 0, second_ch = 0, rez = 0;

long int s = 0;

s = pop(symb);

second_ch = pop(numb);

first_ch = pop(numb);

if ((second_ch == 0 && (s == 47 || s == 37)) || ((first_ch < 0 || second_ch < 0) && s == 37 ))

{

printf("wrong_format\n");

error = 1;

}

else

{

rez = preobr(s, first_ch, second_ch);

*numb = push(*numb, rez);

}

return;

}

void main(void)

{

while (1)

{

bool error = 0;

unsigned int i = 0;

struct STACK *symb = NULL;//стек операторов

struct STACK *numb = NULL;//стек чисел

setlocale(LC_ALL, "Russian");

char str[M];

gets_s(str);

if (proverka(str) == 0)//проверка строки на правильность

{

printf("wrong_format\n");

}

else//если пройдена проверка, запуск вычислений

{

for (i = 0; i < strlen(str); i++)

{

if (symb == NULL && (str[i] == '+' || str[i] == '-' || str[i] == '*' || str[i] == '/' || str[i] == '%'))

{

symb = push(symb, str[i]);

}

else if (error == 1) break;

else if (str[i] == '(') symb = push(symb, str[i]);

else if (str[i] == ')')

{

long int k = 0;

while (symb->data != 40)

{

calc(&symb, &numb, error);

}

k = pop(&symb);

}

else if (str[i] == '*' || str[i] == '/' || str[i] == '%')

{

long int k = symb->data;

if (k == 42 || k == 47 || k == 37)

{

calc(&symb, &numb, error);

symb = push(symb, str[i]);

}

else symb = push(symb, str[i]);

}

else if (str[i] == '+' || str[i] == '-')

{

if (str[i] == '-' && ((i > 0 && str[i - 1] == '(') || i == 0))

{

numb = push(numb, 0);

symb = push(symb, str[i]);

}

else

{

while (symb != NULL && symb->data != 40)

{

calc(&symb, &numb, error);

}

symb = push(symb, str[i]);

}

}

else if (str[i] == '_')

{

printf("wrong_format\n");

error=1;

break;

}

else numb = push(numb, get_ch(i, str,error));

}

if (error != 1)

{

while (symb != NULL && error != 1)

calc(&symb, &numb, error);

if (error != 1)

{

long int rezult = 0;

rezult = pop(&numb);

printf("%i\n", rezult);

free(numb);

free(symb);

}

}

}

_getch();

}

}

Наши рекомендации