ТЕОРЕТИЧЕСКИЕ ИССЛЕДОВАНИЯ
ОТЧЕТ
По лабораторной работе № 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();
}
}