Оцените выражение Postfix, используя дерево в переполнении стека
Я должен оценивать постфиксное выражение, используя дерево выражений. Предположим, у меня есть такое дерево
-
/ \
+ *
/ \ / \
a b c d
Сначала мне нужно оценить поддерево + b и сохранить его результат в узле +, затем c * d и так далее, пока у меня не будет результата в корневом узле.
Я попробовал рекурсивный подход с использованием стека, но это не сработало. Псевдокод выглядел так
- функция eval (узел)
- Eval (node-> слева)
- Eval (node-> справа)
- if (узел является листовым узлом)
положить его в стек - иначе если (узел является операндом)
поп а и поп б из стека
узел-> значение = a-> значение op b-> значение
удалить б;
Однако это не сработало. Я также должен показывать дерево на каждом шаге, чтобы показать уменьшающиеся узлы.
Я много раз гуглял, но не смог найти нужный ответ.
Кто-нибудь, пожалуйста, помогите мне, как это сделать.
void expression_tree::evaluate(node *temp)
{
if(!temp)
return;
/// stack_postfix obj;
stack_postfix obj2;
evaluate(temp->left);
evaluate(temp->right);
if(temp->right == NULL && temp->left == NULL)
{
obj2.push(temp);
}
else
{
node * a = obj2.pop();
node *b = obj2.pop();
temp->value = a->value + b->value;
delete a;
delete b;
}
}
Решение
у вас есть 2 варианта:
Эваль листа:
1 — просто подтолкнуть значение в стек
Eval of non_leaf:
1 — eval left, — REMEMBER: результат eval добавляется в стек.
2 — все правильно,
3 — поп 2 предмета,
4 — рассчитать,
5 — результат толчка.
в конце у вас будет 1 предмет в стеке — последний результат
РЕДАКТИРОВАТЬ:
void expression_tree::evaluate(node *temp, stack& s)
{
if(!temp)
return;
if(temp->left != NULL && temp->right != NULL){
//only 1 pointer is illegal!
evaluate(temp->left);
evaluate(temp->right);
node* n2 = s.pop();
node* n1 = s.pop();
//in the stack should be only leaves
temp->value = n1->value + n2->value;//use switch by operator
delete temp->left;
temp->left = NULL;
delete temp->right;
temp->right=NULL;
}
s.push (temp);
}
Другие решения
Ты забыл obj2.push(temp->balue); в остальной части
Однако ошибок больше, стек должен быть распределен между вызовами функций, чтобы функция могла его обработать.