我有一个小问题。我正在尝试向二叉树添加数学表达式,但我无法理解该算法。这里是:
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++ 代码或更好解释算法的源代码吗?
PS 这是我编写的新代码,但它仅适用于以下表达式:(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;
}