Untitled diff
146 lines
/* Компиля:
#include <locale.h>
* gcc -o rpn rpn.c
#include <vector>
*
* Использование:
* ./rpn <выражение>
*
* Пример:
* ./rpn 3 5 +
*
* Замечание: знак умножения `*' заменен на `x', т.к. символ `*' используется
* командной оболочкой.
**/
#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#define STKDPTH 32 /* Глубина стека */
#define STKDPTH 32 /* Глубина стека */
/* Значения, возвращаемые функцией parse */
/* Значения, возвращаемые функцией parse */
#define VAL 0 /* В стек занесено новое значение */
#define VAL 0 /* В стек занесено новое значение */
#define ADD 1 /* Сложение */
#define ADD 1 /* Сложение */
#define SUB 2 /* Вычитание */
#define SUB 2 /* Вычитание */
#define MUL 3 /* Умножение */
#define MUL 3 /* Умножение */
#define DIV 4 /* Деление */
#define DIV 4 /* Деление */
#define SOF -1 /* Переполнение стека */
#define SOF -1 /* Переполнение стека */
#define SUF -2 /* В стеке недостаточно операндов */
#define SUF -2 /* В стеке недостаточно операндов */
#define UNK -3 /* Неопознанное значение */
#define UNK -3 /* Неопознанное значение */
#define NODEBIT (size_t(1) << (sizeof(size_t) * 8 - 1))
struct node {
size_t left;
size_t right;
int type;
node(int type, size_t left, size_t right)
: type(type), left(left), right(right)
{
}
};
/* Глобальные переменные */
/* Глобальные переменные */
int scount;
int scount;
double stack[STKDPTH];
std::vector<node> tree;
std::vector<double> operands;
size_t stack[STKDPTH];
/* Функция распознавания аргументов */
/* Функция распознавания аргументов */
int parse(char *);
int parse(char *);
/* Функция печати дерева */
void printTree();
/* Точка входа */
/* Точка входа */
int main(int argc, char **argv)
int main(int argc, char **argv)
{
{
setlocale(LC_ALL, "Russian");
/* Организуем цикл для перебора аргументов командной строки */
/* Организуем цикл для перебора аргументов командной строки */
while (*++argv) {
while( *++argv ) {
/* Пытаемся распознать текущий аргумент как число или
/* Пытаемся распознать текущий аргумент как число или
* символ арифметической операции */
* символ арифметической операции */
switch (parse(*argv)) {
int type = parse(*argv);
case VAL: continue;
switch( type ) {
case VAL: continue;
/* Вычисляем */
/* Вычисляем */
case ADD:
case ADD:
stack[scount - 1] += stack[scount];
case SUB:
break;
case MUL:
case DIV:
case SUB:
tree.emplace_back(type, stack[scount - 1], stack[scount]);
stack[scount - 1] -= stack[scount];
stack[scount - 1] = NODEBIT | (tree.size() - 1);
break;
break;
case MUL:
stack[scount - 1] *= stack[scount];
break;
case DIV:
if (stack[scount] != 0) {
stack[scount - 1] /= stack[scount];
break;
} else {
fprintf(stderr, "Деление на ноль!\n");
return(1);
}
/* Обработка ошибок */
/* Обработка ошибок */
case SUF:
case SUF:
fprintf(stderr, "Недостаточно операндов!\n");
fprintf(stderr, "Недостаточно операндов!\n");
return(1);
return(1);
case SOF:
case SOF:
fprintf(stderr, "Переполнение стека!\n");
fprintf(stderr, "Переполнение стека!\n");
return(1);
return(1);
case UNK:
case UNK:
fprintf(stderr, "Неопознанный аргумент!\n");
fprintf(stderr, "Неопознанный аргумент!\n");
return(1);
return(1);
}
}
}
}
/* Вывести результат */
/* Вывести результат */
auto int i;
printTree();
for (i = 0; i < scount; i++) printf("%0.3f\n", stack[i]);
return(0);
return(0);
}
}
int parse(char *s)
int parse(char *s)
{
{
double tval = 0;
double tval = 0;
char * endptr;
char * endptr;
/* Распознаем знаки арифметических операций */
/* Распознаем знаки арифметических операций */
switch (*s) {
switch( *s ) {
case '-':
case '-':
/* Если минус является первым и не последним символом аргумента,
/* Если минус является первым и не последним символом аргумента,
* значит пользователь ввел отрицательное число и опознавать его
* значит пользователь ввел отрицательное число и опознавать его
* как операцию вычитания не нужно */
* как операцию вычитания не нужно */
if (*(s+1) != '\0') break;
if( *(s + 1) != '\0' ) break;
if (scount >= 2) {
if( scount >= 2 ) {
scount -= 1;
scount -= 1;
return(SUB);
return(SUB);
}
} else return(SUF);
else return(SUF);
case '+':
case '+':
if (scount >= 2) {
if( scount >= 2 ) {
scount -= 1;
scount -= 1;
return(ADD);
return(ADD);
}
} else return(SUF);
else return(SUF);
case 'x':
case 'x':
if (scount >= 2) {
if( scount >= 2 ) {
scount -= 1;
scount -= 1;
return(MUL);
return(MUL);
}
} else return(SUF);
else return(SUF);
case '/':
case '/':
if (scount >= 2) {
if( scount >= 2 ) {
scount -= 1;
scount -= 1;
return(DIV);
return(DIV);
}
} else return(SUF);
else return(SUF);
}
}
errno = 0;
errno = 0;
/* Пытаемся сконвертировать строковый аргумент в число */
/* Пытаемся сконвертировать строковый аргумент в число */
tval = strtod(s, &endptr);
tval = strtod(s, &endptr);
/* Вернуть ошибку `неопознанный аргумент' в случае неудачи */
/* Вернуть ошибку `неопознанный аргумент' в случае неудачи */
if (errno != 0 || *endptr != '\0') return(UNK);
if( errno != 0 || *endptr != '\0' ) return(UNK);
/* Проверяем, есть ли свободное место в стеке
/* Проверяем, есть ли свободное место в стеке
* и сохраняем в нем операнд, иначе возвращаем ошибку переполнения */
* и сохраняем в нем операнд, иначе возвращаем ошибку переполнения */
if (scount < STKDPTH) stack[scount++] = tval;
operands.push_back(tval);
if( scount < STKDPTH ) stack[scount++] = operands.size() - 1;
else return(SOF);
else return(SOF);
return(VAL);
return(VAL);
}
}
void printTree()
{
std::vector<std::pair<size_t, int>> local;
for( int i = 0; i < scount; i++ ) {
local.emplace_back(stack[i], 0);
while( !local.empty() ) {
auto st = local.back();
local.pop_back();
// indent
for( int i = st.second; i--; putc('\x20', stdout), putc('\x20', stdout) );
if( (st.first & NODEBIT) != 0 ) {
auto &n = tree[st.first & ~NODEBIT];
local.emplace_back(n.right, st.second + 1);
local.emplace_back(n.left, st.second + 1);
switch( n.type ) {
case ADD:
printf("+ (add)\n");
break;
case SUB:
printf("- (sub)\n");
break;
case MUL:
printf("x (mul)\n");
break;
case DIV:
printf("/ (div)\n");
break;
default:
printf("unexpected\n");
}
} else {
printf("%0.3f\n", operands[st.first]);
}
}
}
}