Викиучебник

Язык Си в примерах/Калькулятор выражений в обратной польской нотации: различия между версиями

Интерактивная навигация по истории
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
Нет описания правки
Строка 28:
 
НИже приведена постая реализация такого калькулятора на C. Заметим, что в ней нет никаких проверок ошибок ввода (если первый символ есть знак операции, она "умрёт"), а также стэк с его операциями pop и push не выделен в явную структуру.
Роль стэка играет обычный массив (stack[2561000]). сПеременная указателем<tt>sp</tt> на(stack вершинуpointer) стэкаравна (spколичеству &mdash;элементов stackв pointer)стеке.
Число (<tt>sp</tt>-1) равно индексу ячейки, являющейся вершиной стека.
 
 
#include <stdio.h>
int main()
main()
{
int stack[2561000]; //
int sp = 0; // индекс ячейки, куда будет push-иться очередное число
char buf[256];
// (sp-1) = индекс ячейки, являющейся вершиной стека
int sp = 0;▼
 
printf("Sample:\n7 5 * 3 4 * + =\nResult = 47\n\nInput expression:\n")
while(!feof(stdin)) {
int c = sp--getchar();▼
{
if(scanfint ("%s", buf) != 1 )x;
switch(c) break;{
switch(buf[0]) case ' ':
{ case '\n':
case '\0':▼
break;
case '=':
printf("Result = %d\n", stack[--sp - 1]); sp--;
break;
case '+':
stack[sp-2] = stack[sp-2] + stack[sp-1]; sp--;
▲ sp--;
break;
case '-':
stack[sp-2] = stack[sp-2] - stack[sp-1]; sp--;
sp--;▼
break;
case '*':
stack[sp-2] = stack[sp-1] * stack[sp-2]; sp--;
sp--;▼
break;
case '/':
stack[sp-2] = stack[sp-1] / stack[sp-2]; sp--;
sp--;▼
break;
default:
stack[sp++] = atoiungetc(bufc, stdin);
if(scanf("%d", &x) != 1) {
fprintf(stderr, "Can't read integer\n");
▲ sp- return -1;
▲ sp--; } else {
stack[sp] = x; sp++;
▲ case '\0': }
}
}
Строка 74:
}
 
===Пример работы программы===
 
> ./stack
=== Реализация калькулятора на C++ с явным использованием стэка ===
1 2 3 4 + * + =
Result = 15
1 2 + 3 4 + * =
Result = 21
 
 
===Задания===
 
# Введите входные следующие входные данные <tt>1 2 3 * * * * = = = =</tt>. К чему это привело? Добавьте к приведенной программе
"защиту от дурака".
# Введите входные данные состоящие из 10000 единиц и 9999 знаков +. Сможет ли программа отработать на этих входных данных?
 
 
===Замечания===
# У данной программы есть целый ряд недостатков
:* Программа не будет работать, если количество элементов в стеке превысит 1000
:* Программа не замечает некорректные входы и отрабатывает их с непредсказуемыми последстиями.
:* В программе явно не отображено, что присутствует структура данных "стек", что затрудняет сторонним разработчикам осуществлять доработку данной программы.
 
 
 
=== Реализация калькулятора с явным определением операций со стеком ===
 
 
Введем операции работы со стеком в программу. Это повысит читаемость кода и облегчит понимание заложенной в программу логики.
 
#include <stdio.h>
#include <malloc.h>
▲ int sp = 0;
class Stack {
int *m_datastack[1000];
int pop(void) {▼
int m_size;
intif(sp m_pt;> 0) {
▲ return spstack[--sp];
public:
Stack(int} size)else {
fprintf(stderr, "Невозможно выполнить POP для пустого стека.\n");
m_size = size;
m_data =return (int*)malloc(m_size * sizeof(int))0;
m_pt = 0;▼
};
~Stack() {
free(m_data);
};
▲ int pop(void) {
if(m_pt)
return m_data[--m_pt];
else
return 0;
};
void push(int a) {▼
if(m_pt >= m_size-1) {
m_size = 10 + 2 * m_size;
m_data = (int*) realloc (m_data, m_size * sizeof(int));
}
m_data[m_pt++] = a;
};
int empty() {▼
return (m_pt == 0);▼
}
};
▲ void push(int a) {
▲ m_ptstack[sp++] = 0a;
};
▲ int empty() {
▲ return (m_ptsp == 0);
}
int main() {
main() {
class Stack s(3);
int i;
while(!feof(stdin)) {
Строка 121 ⟶ 129 :
int x;
switch (c) {
case EOF: break;
case '\n':
case ' ' : break;
case '=' : printf("Result = %d\n", s.pop()); break;
case 27 : goto RESULT;
case '+' : s.push(s.pop() + s.pop()); break;
case '-' : s.push(-s.pop() + s.pop()); break;
case '*' : s.push(s.pop() * s.pop()); break;
default:
ungetc(c, stdin);
Строка 142 ⟶ 149 :
RESULT:
i = 0;
while(!s. empty() ){
printf("Stack[%d] = %d\n", i, s.pop());
i++;
Строка 148 ⟶ 155 :
return 0;
}
 
 
В данной программе в некоторой степени реализована "защита от дурака", а именно, если вводится выражение, в котором число операций превосходит число
помещенных в стек элементов (например <tt>1 2 + *</tt>), то программа не допустить уменьшиния переменной <tt>sp</tt> до отрицательных значений, а выдаст предупреждение <tt>"Невозможно выполнить POP для пустого стека.</tt>.
 
Кроме защиты от дурака-пользователя необходима еще защита от дурака-программиста, который возьмет ваш код, решит его использовать и дорабатывать.
Точнее, нужно просто соблюдать некоторые правила, которые не позволили бы программисту, который включил ваш код в свой проект получить ошибки,
связанные с пересечением имён, испольуемых им в своих файлах и вами, в фале <tt>stack.c</tt>.
 
В первую очередь, не рекомендуется объявлять глобальные переменные, которые не являются всеобщим достоянием, а относятся к вашим личным внутренним
делам.
Источник — https://ru.wikibooks.org/wiki/Язык_Си_в_примерах/Калькулятор_выражений_в_обратной_польской_нотации