Язык Си в примерах/Калькулятор выражений в обратной польской нотации: различия между версиями
Karagota (обсуждение | вклад) Нет описания правки |
Karagota (обсуждение | вклад) |
||
Строка 6: | Строка 6: | ||
а затем знак операции. Например: |
а затем знак операции. Например: |
||
{|border=1 |
|||
|'''Обратная польская нотация'''|'''Обычная нотация'''| |
|'''Обратная польская нотация'''|'''Обычная нотация'''| |
||
|- |
|||
| 2 3 + | 2 + 3 | |
| 2 3 + | 2 + 3 | |
||
|- |
|||
| (2 3 *) (4 5 *) + | (2 * 3) + (4 * 5) | |
| (2 3 *) (4 5 *) + | (2 * 3) + (4 * 5) | |
||
|- |
|||
| 2 3 4 5 6 * + - / | 2 / (3 - (4 + (5 * 6))) | |
| 2 3 4 5 6 * + - / | 2 / (3 - (4 + (5 * 6))) |} |
||
Версия от 19:59, 28 марта 2006
Калькулятор выражений в обратной польской нотации
Рассмотрим запись арифметческих выражений, в которых сначала следуют два операнда арифметической операции, а затем знак операции. Например:
Обычная нотация| |
2 + 3 | |
(2 * 3) + (4 * 5) | |
2 / (3 - (4 + (5 * 6))) |}
Транслятор этих выражений основан на стэке. Каждое следующее число помещается в стэк. Если встречается знак операции, то два числа из стэка извлекаются (a = pop(), b = pop()), для них вычисляется значение соответствующей бинарной арифметической операции и результат помещается в стек ( push(a * b) ). НИже приведена постая реализация такого калькулятора на C. Заметим, что в ней нет никаких проверок ошибок ввода (если первый символ есть знак операции, она "умрёт"), а также стэк с его операциями pop и push не выделен в явную структуру. Роль стэка играет обычный массив (stack[256]) с указателем на вершину стэка (sp — stack pointer)
#include <stdio.h> int main() { int stack[256]; char buf[256]; int sp = 0; printf("Sample:\n7 5 * 3 4 * + =\nResult = 47\n\nInput expression:\n") while(!feof(stdin)) { if(scanf ("%s", buf) != 1 ) break; switch(buf[0]) { case '\0': break; case '=': printf("Result = %d\n", stack[--sp]); break; case '+': stack[sp-2] = stack[sp-2] + stack[sp-1]; sp--; break; case '-': stack[sp-2] = stack[sp-2] - stack[sp-1]; sp--; break; case '*': stack[sp-2] = stack[sp-1] * stack[sp-2]; sp--; break; case '/': stack[sp-2] = stack[sp-1] / stack[sp-2]; sp--; break; default: stack[sp++] = atoi(buf); } } printf("Result = %d\n",stack[sp-1]); return 0; }
Реализация калькулятора на C++ с явным использованием стэка#include <stdio.h> #include <malloc.h> class Stack { int *m_data; int m_size; int m_pt; public: Stack(int size) { m_size = size; m_data = (int*)malloc(m_size * sizeof(int)); 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); } }; int main() { class Stack s(3); int i; while(!feof(stdin)) { int c = getchar(); 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); if(scanf("%d", &x) != 1) { fprintf(stderr, "Can't read integer\n"); return -1; } else { s.push(x); } break; } } RESULT: i = 0; while(!s.empty()){ printf("Stack[%d] = %d\n", i, s.pop()); i++; } return 0; } |