У меня есть небольшая проблема. Я пытаюсь добавить математическое выражение в двоичное дерево, но я не могу понять алгоритм. Вот оно:Дерево двоичных выражений C++
If the current token is a '(':
Add a new node as the left child of the current node, and
descend to the left child.
If the current token is in the list ['+','-','/','*']:
Set the root value of the current node to the operator represented by the current token.
Add a new node as the right child of the current node and descend to the right child.
If the current token is a number:
Set the root value of the current node to the number and return to the parent.
If the current token is a ')':
go to the parent of the current node.
и код, который я сделал до сих пор:
template<class T>
void Tree<T>::Expr(Node<T> *node, char expr[], int &i)
{
i++;
T x = expr[i];
if(x == '(')
{
node = node->Left;
node = new Node<T>;
node->Left = NULL;
node->Right = NULL;
Expr(node, expr, i);
}
if(x == '+' || x == '-' || x == '*' || x == '/')
{
node->data = x;
node = node->Right;
node = new Node<T>;
node->Left = NULL;
node->Right = NULL;
Expr(node, expr, i);
}
if(x >= '0' && x <= '9')
{
node->data = x;
return;
}
if(x == ')') return;
}
Я знаю, что это большой беспорядок, но я не могу понять, как его реализовать. Может кто-нибудь объяснить алгоритм мне или дать мне источник с кодом C++ или лучше объяснил алгоритм?
P.S. Вот новый код, который я написал, но он работает только для выражений, как: (5 + 2)
template<class T>
void Tree<T>::Expr(Node<T> *&node, char expr[], int &i)
{
i++;
if(i >= strlen(expr)) return;
char x = expr[i];
node = new Node<T>;
node->Left = NULL;
node->Right = NULL;
if(x == '(')
{
Expr(node->Left, expr, i);
i++;
x = expr[i];
}
if(x >= '0' && x <= '9')
{
node->data = x;
return;
}
if(x == '+' || x == '-' || x == '*' || x == '/')
{
node->data = x;
Expr(node->Right, expr, i);
}
if(x == ')') return;
}
, что это проблема с этим кодом, что именно вы не поняли - я вас не понял. –
Очевидно, что код не следует алгоритму. Я не могу понять, как работает алгоритм. Например, если токен равен '(' Я перехожу к левому дочернему узлу текущего узла, а затем скажу, что следующий токен в выражении является числом. Я добавляю этот номер к текущему узлу, и я должен вернуться. Но как могу ли я вернуться к родителям? Я вернусь к строке 13, и программа закончится. Какая должна быть структура, которую я должен использовать? –