recursion — рекурсивная оценка префиксного выражения в переполнении стека

Question

recursion — рекурсивная оценка префиксного выражения в переполнении стека

Я пытаюсь написать рекурсивный алгоритм на C ++, который оценивает выражение типа: «оператор», «переменная», «переменная» и возвращает операцию (пример: input = + 3 4; output = 7). Операторы являются только основными (+, -, *, /), а переменные являются целыми числами от 1 до 9. Проблема в том, что я не знаю, как начать и какой метод использовать. Я не могу использовать стеки или списки.

РЕДАКТИРОВАТЬ: я готовлюсь к экзамену по введению в C ++, поэтому мне не разрешается использовать какой-либо сложный метод для решения проблемы. Я могу использовать только процедуры, циклы, рекурсивность и методы поиска и потока.

Благодарю.

0

c++evaluation expression prefix recursion

Решение

Другие решения

Попробуйте это так. псевдокод:

double Process(Parser & parser)
{
Token token = parser.GetToken();

if (token.Type == number)
return (NumberToken)token.value;
else if (token.Type == operator)
{
double left = Process(parser);
double right = Process(parser);

switch (OperatorToken)token.op:
{
case '+' :
{
return left + right;
}
// ...
}
}
}

Однако такого рода проблемы легче решить, используя стек.

1

Вот решение с использованием рекурсии (в выражении не должно быть пробелов):

#include <cstdio>

int eval(const char *s, const char **outptr)
{
int a, b, y;
const char *out;

switch (*s) {
case '+':
a = eval(s + 1, &out);
b = eval(out, &out);
y = a + b;
*outptr = out;
break;
case '-':
a = eval(s + 1, &out);
b = eval(out, &out);
y = a - b;
*outptr = out;
break;
case '*':
a = eval(s + 1, &out);
b = eval(out, &out);
y = a * b;
*outptr = out;
break;
case '/':
a = eval(s + 1, &out);
b = eval(out, &out);
y = a / b;
*outptr = out;
break;
default: /* '0'...'9'assumed */
y = *s - '0';
*outptr = s + 1;
break;
}

return y;
}

int main(int argc, char *argv[])
{
const char *end;
int x;

x = eval(argv[1], &end);
printf("%d\n", x);

return 0;
}

Пример:

./eval +3+*45/62
26

1

Предполагая, что у вас есть входной итератор (например, указатель на входную строку или векторный итератор), вы можете использовать что-то вроде этого:

compute (input.iterator it) {
if (it != input.end() and is_operator(*it)) {
operator op = *it;
int v1, v2;
it++;
v1 = is_operator(*it) ? compute(it) : *it;
it++;
v2 = is_operator(*it) ? compute(it) : *it;
return operator_exec(op, v1, v2)
}
return *it;
}

0

Источник

Accepted Answer

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

Основной шаблон выглядит примерно так:

int apply(char op, int a, int b) {
switch (op) {
case '+': return a + b;
case '-': return a - b;
case '/': return a / b;
case '*': return a * b;
default: throw bad_operator(op);
}
}

int expression(char *&input) {
char op = *input++;

if (isdigit(op))
return op - '0';

int a = expression(input);
int b = expression(input);
return apply(op, a, b);
}

Программа быстрого тестирования:

#include <ctype.h>
#include <iostream>
#include <exception>
#include <string>

struct bad_operator : public std::logic_error {
bad_operator(char ch)  :
std::logic_error(std::string("Bad operator: ") + ch)
{}
};

int main() {
char *input="+/42-43";
std::cout << expression(input);
return 0;
}

2