1

我创建了一个指向树的指针的下推堆栈。当用户在后缀中键入方程式时，程序将方程式存储为树（即如下所示）

34*7+ 58+ 12* 等于

   ----+----        ---+---      ---*---
   |        |       |     |      |     |
---*---     7       5     8      1     2
|     |
3     4

然而，目前任何存储多于一个节点的树的尝试（当遇到 + 或 * 时）都会覆盖先前的树，即上述等式导致以下堆栈：

 ---+---      ---+---       ---*---
 |     |      |     |       |     |
 1     2      1     2       1     2

我的代码如下：

#include <iostream>
using namespace std;

struct node
{
    char info; struct node *r, *l;
};


class Stack
{
    private:
        node *stack;
        int p;
    public:
        Stack (int max = 100)
            { stack = new node[max]; p=0; }
       ~Stack ()
            { delete stack;}
        inline void push(node item)
            { 
                stack[p] = item;
                p++;
            }
        inline node pop()
            { 
                p--;                
                return stack[p];
            }
        inline int empty ()
            { return !p; }
};

void tree(const char *ltr)
{
    struct node *z;
    Stack stack(50);
    z = new node;
    z->l =z; z->r =z;z->info='a';
    while(*ltr)
    {
        while (*ltr == ' ')
        {
            ltr ++;
        }
        struct node *x;
        x = new node;
        x ->info = *ltr; 
        if ( (*ltr == '+' || *ltr == '*') && !stack.empty())
        {
            x->r=&stack.pop();
            x->l=&stack.pop();          
        }else{
            x->l = z; x->r = z;
        }
        stack.push(*x);
        ltr++;
    }
}

int main()
{
    char word[100];
    cin.get(word, 100);
    cin.ignore(100, '\n');
    tree(word);
    cin.get();
}

似乎是当 x->r = &stack.pop(); 执行它会覆盖所有先前的节点-> r。但是 node->info 没有改变，z 节点也不影响树。

有人知道发生了什么吗？几个小时以来，我一直在努力弄清楚发生了什么以及我做错了什么。

亲切的问候山姆

修正案

为了测试我一直在使用非递归遍历类型函数的代码（由于问题导致堆栈溢出的递归），这个代码有点乱，但我已经将它包含在下面，如果你运行它并输入：

12+ 34* 56+

你会看到我遇到的问题，它应该说：

aa5+ aa3* aa1+

而是产生：

aa5+ aa5* aa5+

#include <iostream>
using namespace std;

struct node
{
    char info; struct node *r, *l;
};

void traverse3(struct node *tree)
{
    {
        cout << tree->info;
    }
}
void traverse2(struct node *tree)
{
    {
        traverse3(tree->r);
        cout << tree->info;
    }
}
void traverse1(struct node *tree)
{
    {
        traverse2(tree->r);
        cout << tree->info;
    }
}

void traverse(struct node *tree)
{
    {
        traverse1(tree->r);
        cout << tree->info;
    }
}

class Stack
{
    private:
        node *stack;
        int p;
    public:
        Stack (int max = 100)
            { stack = new node[max]; p=0; }
       ~Stack ()
            { delete stack;}
        inline void push(node item)
            { 
                stack[p] = item;
                p++;
            }
        inline node pop()
            { 
                p--;                
                return stack[p];
            }
        inline int empty ()
            { return !p; }
};

void tree(const char *ltr)
{
    struct node *z,*c;
    Stack stack(50);
    z = new node;
    z->l =z; z->r =z;z->info='a';
    while(*ltr)
    {
        while (*ltr == ' ')
        {
            ltr ++;
        }
        struct node *x;
        x = new node;
        x ->info = *ltr; 
        if ( (*ltr == '+' || *ltr == '*') && !stack.empty())
        {
            x->l = &stack.pop();
            x->r = &stack.pop();
        }else{
            x->l = z; x->r = z;
        }
        stack.push(*x);
        ltr++;
    }
    c = new node;
    int q;
    for(q=0; q<3; q++)
    {
    *c = stack.pop();
    traverse(c);
    }
}

int main()
{
    char word[100];
    cin.get(word, 100);
    cin.ignore(100, '\n');
    tree(word);
    cin.get();
}
4

0 回答 0