Читать инфиксное выражение в стек
Я написал код для преобразования дерева выражений в preorder и postorder, но я изо всех сил пытаюсь построить дерево выражений из выражения infix. У меня есть файл .cc, который будет вызывать функцию build_expression_tree, вызывать функции преобразования и распечатывать преобразованные выражения.
Это моя текущая нерабочая функция:
void Expression_Tree::build_expression_tree(char input[], int size)
{
for (int i = 0; i < size; i++)
{
if (input[i] == ' ')
{
i++;
}
if(input[i] >= '0' && input[i] <= 9)
{
ETNode *temp = new ETNode;
temp->left = temp->right = NULL;
temp->input = input[i];
tree_stack.push(temp);
}
else if (input[i] == '(')
{
ETNode *temp = new ETNode;
temp->left = temp->right = NULL;
temp->input = input[i];
tree_stack.push(temp);
}
else if (input[i] == ')')
{
while (tree_stack.top() != '(')
{
temp->right = tree_stack.top();
tree_stack.pop();
temp->left = tree_stack.top();
tree_stack.pop();
tree_stack.pop();
tree_stack.push(temp);
}
}
else if (input[i] == '+' || input[i] == '-' || input[i] == '*' || input[i] == '/')
{
while (!tree_stack.empty())
{
ETNode *temp = new ETNode;
temp->left = temp->right = NULL;
temp->input = input[i];
tree_stack.push(temp);
temp->right = tree_stack.top();
tree_stack.pop();
temp->left = tree_stack.top();
tree_stack.pop();
tree_stack.push(temp);
}
}
}
}
Ошибки, которые я получаю в этот момент:
Expression_Tree.h: 61: 40: ошибка: ISO C ++ запрещает сравнение между указателем и целым числом
while(tree_stack.top() != '(')
Expression_Tree.h: 62: 13: ошибка: ‘temp’ не был объявлен в этой области
temp->right = tree_stack.top();
Expression_Tree.h: 62: 13: ошибка: ‘temp’ не был объявлен в этой области
temp->left = tree_stack.top();
Я знаю, почему происходят последние две ошибки (не объявленные в области видимости), но я просто не знаю, что делать, чтобы исправить это, в то же время заставляя мой код работать должным образом.
Я даже не знаю, является ли мой код полностью неправильным, но любые советы были бы невероятно оценены!
Благодарю.
РЕДАКТИРОВАТЬ:
Это классы, которые влияют на функцию Build_Expression_Tree.
class ETNode {
public:
char input;
ETNode *left, *right;
};
class Expression_Tree {
public:
Expression_Tree() { root = 0; };
~Expression_Tree() { clear(root); }
void build_expression_tree(char[], int);
void inorder() { inorder(root); }
void preorder() { preorder(root); }
void postorder() {postorder(root); }
private:
ETNode* root;
std::stack<ETNode*> tree_stack;
void visit(ETNode* p) { std::cout << p->input << " "; }
void inorder(ETNode*);
void preorder(ETNode*);
void postorder(ETNode*);
void clear(ETNode*);
};
Решение
Здесь я разделил ваш пример входных данных на представление о том, как использовать стек и какие решения принимаются на каждом входе.
// _ = nullptr or empty
// # = pointer to subtree (not just a number)
// | ___ | | | begin (empty element on stack)
// | 2__ | | | 2 make number node and set to top->left if empty, else top->right
// | 2+_ | | | + set top->input if not set, else pop parent into left of new node
// | 2+_ | ___ | | ( make new node on stack
// | 2+_ | 3__ | | 3 make number node and set to top->left if empty, else top->right
// | 2+_ | 3*_ | | * set top->input if not set, else pop parent into left of new node
// | 2+_ | 3*_ | ___ | ( make new node on stack
// | 2+_ | 3*_ | 2__ | 2 make number node and set to top->left if empty, else top->right
// | 2+_ | 3*_ | 2+_ | + set top->input if not set, else pop parent into left of new node
// | 2+_ | 3*_ | 2+2 | 2 make number node and set to top->left if empty, else top->right
// | 2+_ | 3*# | | ) pop it off into its parent
// | 2+# | | | ) pop it off into its parent
// | #+_ | | | + set top->input if not set, else pop parent into left of new node
// | #+5 | | | 5 make number node and set to top->left if empty, else top->right
Обратите внимание, что у меня есть много повторяющихся утверждений, один тип для ( один для ) один на номер 0-9 и по одному на каждую операцию +-*/, У вас уже есть эти подразделения в вашем коде, так что вы на правильном пути.
(Единственной задачей должно быть создание нового узла на вершине стека. В вашем коде нет смысла устанавливать input = '(' потому что он будет перезаписан фактическим вводом позже, и его позиция в стеке — все, что нужно для отслеживания этого. Вы должны инициализировать input в '\0' или что-то еще, означающее пустое.
)Работа должна состоять в том, чтобы вытолкнуть вершину из стека и поместить ее туда, куда она должна идти. Это будет либо левый узел следующей вершины, если он нулевой, в противном случае это будет правый узел вершины. Вам не нужно зацикливаться на стеке, как вы делаете, потому что он всегда будет просто вершиной, в которой мы заинтересованы.
Работа числа должна состоять в том, чтобы создать себя как новый узел и поместить себя туда, куда он должен идти. Как ) это будет либо левый верхний узел, если он нулевой, иначе это будет правый верхний узел. В своем коде вы создаете узел, но не помещаете его где-либо кроме стека. Там нет никакой пользы, потому что числовой узел всегда будет листовым узлом (без правого или левого).
Наконец, работа операции должна состоять в том, чтобы просто установить себя на вершину input, Тем не менее, есть особый случай, когда вершина уже заполнена (когда вы делаете 1+2+3 1+2 это узел сверху). Таким образом, в этом случае вы можете просто вытолкнуть верхнюю часть, вставить новый узел сверху, добавить старую верхнюю часть в качестве левого, и ТОГДА просто установить себя в верхнюю часть. input, Вам не нужна петля.
После того, как все сделано, вы можете просто установить root = tree_stack.top(),
Если вам нужен код, я могу его предоставить, но я надеюсь, что моего объяснения достаточно.
Код: Кажется, это работает для меня
void Expression_Tree::build_expression_tree(char input[], int size)
{
// assuming empty tree_stack, it shouldn't really be a member
// variable since its only used for building
//std::stack<ETNode*> tree_stack;
// make empty node, should really make a default constructor set all this up
tree_stack.push(new ETNode);
tree_stack.top()->left = nullptr;
tree_stack.top()->right = nullptr;
tree_stack.top()->input = '\0';
for (int i = 0; i < size; i++)
{
if (input[i] == ' ')
{
i++;
}
if (input[i] >= '0' && input[i] <= '9') // this 9 had a typo before
{
// create number leaf
ETNode *temp = new ETNode;
temp->left = nullptr;
temp->right = nullptr;
temp->input = input[i];
// put where it needs to go
if (tree_stack.top()->left == nullptr)
tree_stack.top()->left = temp;
else
tree_stack.top()->right = temp;
}
else if (input[i] == '(')
{
// make empty node
ETNode *temp = new ETNode;
temp->left = nullptr;
temp->right = nullptr;
temp->input = '\0';
tree_stack.push(temp);
}
else if (input[i] == ')')
{
// pop top from the stack
ETNode *temp = tree_stack.top();
tree_stack.pop();
// put where it needs to go
if (tree_stack.top()->left == nullptr)
tree_stack.top()->left = temp;
else
tree_stack.top()->right = temp;
}
else if (input[i] == '+' || input[i] == '-' || input[i] == '*' || input[i] == '/')
{
// shuffle node if already filled
if (tree_stack.top()->input != '\0')
{
ETNode *old = tree_stack.top();
tree_stack.pop();
ETNode *temp = new ETNode;
temp->left = old;
temp->right = nullptr;
tree_stack.push(temp);
}
tree_stack.top()->input = input[i];
}
}
// set root node
root = tree_stack.top();
}
Другие решения
Беглый взгляд показывает, что вам нужно ETNode *temp = new ETNode; сразу после while(tree_stack.top() != '('), Я не проверял логику, хотя.