#java #recursion #postfix-notation
#java #рекурсия #постфиксная нотация
Вопрос:
Мне нужен алгоритм для вычисления постфиксного выражения с использованием рекурсии. В этом постфиксном выражении операнд может состоять более чем из одной цифры. Пробел используется для различения двух операндов. Таким образом, выражение ’45 68 ‘ является допустимым.
Я думал оценить его в обратном направлении, но я думаю, что это не должно быть правильным.
Может ли кто-нибудь помочь мне только с алгоритмом.
Заранее спасибо.
Комментарии:
1. Алгоритм не был дан вам на занятиях? Википедия спешит на помощь: en.wikipedia.org/wiki/Reverse_Polish_notation#Postfix_algorithm
2. Это простые алгоритмы, которые легко доступны в Интернете. Кроме того, если алгоритм не был предоставлен вам в классе, возможно, на это есть причина. Возможно, ваш учитель хочет, чтобы вы сами с этим разобрались. Честно говоря, попробуйте разобраться в этом сами, напишите код и отладьте его, прежде чем рисковать и искать его.
3. @RayToal Спасибо за помощь, но я хотел сделать это с помощью рекурсии. Реализация, приведенная в wiki, использует stack.
4. @darnir Я смог написать его префиксную версию. Но я не в состоянии думать о базовом варианте для этого алгоритма.
5. @RayToal Да, только двоичный оператор
Ответ №1:
Мне не кажется, что проблема, связанная с рекурсией. Но я уверен, что это можно было бы сделать таким образом.
Мне приходят в голову два подхода:
Вариант № 1: Сделать так, чтобы функциональные рекурсионные вызовы и возвраты соответствовали операциям stack push и pop, описанным в Wiki.
Недостатком этого подхода является то, что вы быстро обнаружите, что возвращаемые данные из функции могут быть довольно сложными. Вероятно, это будет оператор. Возможно, с необязательным операндом (т. Е. Числом). Вы будете возвращать структуры / объекты, которые, возможно, должны иметь операции (методы) над ними.
Вариант # 2: Каждый рекурсивный вызов обрабатывает следующий символ входного потока.
Я думаю, что этот подход передал бы в качестве параметров стек и, возможно, «накопитель» для текущего числа — для накопления цифр в число, прежде чем помещать его в стек. Был бы возвращен один массивный числовой результат хвостовой рекурсии.
Этот подход на самом деле просто переписывает цикл как рекурсию.
В любом случае, разобраться в этом самостоятельно должно быть непросто и познавательно!
Ответ №2:
Ниже приведен своего рода псевдокод, который будет работать для постфиксных выражений с / — . Я думаю, вы можете еще больше расширить идею. Если вы все еще сталкиваетесь с трудностями, напишите мне на 2shanks.p@gmail.com поскольку я не являюсь постоянным посетителем этого сайта.
void recursivePostfix(char* expr)
{
if(!expr) return;
bool flag=true;
static double result=0;
double v1=result, v2=0, dec=0;
char oper='0';
int i=0, state=1;
do
{
if('0' != oper)
{
switch(oper)
{
case ' ': result=v1 v2; break;
case '-': result=v1-v2; break;
case '*': result=v1*v2; break;
case '/': result=v1/v2; break;
}
oper = '0';
v1 = resu<
v2 = 0;
recursivePostfix(expr i);
}
if(SPACE_CHAR == *(expr i) amp;amp; state )
continue;
switch(state)
{
case 1:
v1 = v1*10 (expr[i]-'0'); break;
case 2:
v2 = v2*10 (expr[i]-'0'); break;
case 3:
oper = *(expr i);
}
}while(0 != *(expr i ));
cout << resu<
}
Ответ №3:
Я просто кодирую это для интервью, поэтому вот мое решение с использованием Python:
def recursive_postfix(s):
s = s.split(' ')
if len(s) == 1:
return s[0]
res = None
for i in range(len(s)):
if s[i] in [' ', '-', '*', '/']:
res = eval(f'{s[i-2]}{s[i]}{s[i-1]}')
break
s = s[0:i-2] [str(res)] s[i 1:]
return recursive_postfix(' '.join(s))
assert recursive_postfix('2 2 1 *') == '4' # (2 2) * 1
assert recursive_postfix('3 4 2 * 5 *') == '90' # 3 * (4 2) * 5
assert recursive_postfix('7 2 2 * -') == '3' # 7 - (2 * 2)