C++ 中堆栈实现的质因数

Question

问候堆栈溢出，最近遇到一个问题，我的代码没有完全按照我的意图去做。我的意图是让用户输入一个数字，然后程序将检查其质因数，当它找到质因数时，我希望它将数字推入堆栈。我尝试在整个程序中放置 cout 语句，以查看是否有任何特定位置不起作用，但我还没有发现任何内容。我相信我已经非常接近弄清楚这一点，但我不确定如何从这里前进。

这是我的代码：

#include <iostream>
#include <cmath>
using namespace std;

class stack
{
    public:
        static const int MAX = 100;
        stack() { used = 0; } // constructor

        void push(int entry);
        int pop();
        int size() { return used; }
        bool empty() { return used == 0;}

    private:
        int data[MAX];
        int used; // how many elements are used in the stack, top element is used - 1
};

void stack::push(int entry)
{
    data[used] = entry;
    ++used;
}

int stack::pop()
{
    --used;
    return data[used];
}

void primeFactors(stack, int);

int main()
{
    stack primeValues;
    int entry = 0;

    cout << "Enter a positive integer (0 to stop): ";
        cin >> entry;

    if (entry != 0)
    {
        cout << "Prime factors: " << entry << " = ";
    }
    primeFactors(primeValues, entry);

    while(primeValues.pop() != 0) // hopefully continues to pop the prime factors until it reaches zero?
    {
        cout << primeValues.pop() << " ";
    }

    return 0;
}

void primeFactors(stack primeValues, int entry)
{
    if (entry == 0)
    {
        return; // terminate when zero is reached
    }
    if (entry == 1)
    {
        cout << entry; // if 1 is reached display one
    }

    while (entry % 2 == 0) // while there is no remainder do the following
    {
        primeValues.push(2); // push two into stack 
        entry = entry/2;
    }

    for (int i = 3; i <= sqrt(entry); i = i+2) // start looping through numbers to find more prime factors
    {
        while (entry % i == 0)
        {
            primeValues.push(i);
            entry = entry/i;
        }
    }

    if (entry > 2) // if the number is greater than two and doesnt have prime factors push the number
    {
        primeValues.push(entry);
    }
}

我尝试了各种不同的数字，但似乎没有任何效果。我尝试弹出几次以查看是否有任何内容被推送，但它只显示零。我在这里缺少什么？

Answer 1

你犯了一个非常简单的错误。在将堆栈按值传递给

primeFactors

时，堆栈将被复制并继续复制。当

primeFactors

完成时，该副本将被丢弃，并留下原始的空堆栈。

利用 C++ 模板：

#include <iostream>
#include <cmath>

template <typename T, unsigned int MAX>
class stack {
    private:
    T data[MAX] = { 0 };
    unsigned int used = 0;

    public:
    stack() : used(0) {}

    void push(T entry) {
        if (used <= MAX - 1) {
            data[used] = entry;
            used += 1;
        }
    }

    T pop() {
        used -= 1;
        return data[used];
    }

    unsigned int size() const {
        return used;
    }

    bool empty() const {
        return used == 0;
    }
};

template <typename T, unsigned int MAX>
void primeFactors(stack<T, MAX>&, int);

int main() {
    stack<int, 100> primeValues;
    int entry = 0;

    std::cout << "Enter a positive integer (0 to stop): ";
    std::cin >> entry;

    if (entry == 0) {
        return 0;
    }

    primeFactors(primeValues, entry);

    while (!primeValues.empty()) {
        std::cout << primeValues.pop() << " ";
    }

    std::cout << std::endl;
}

template <typename T, unsigned int MAX>
void primeFactors(stack<T, MAX>& primeValues, int entry) {
    if (entry == 0) {
        return;
    }

    if (entry == 1) {
        std::cout << entry << std::endl;
    }

    while (entry % 2 == 0) {
        primeValues.push(2);
        entry /= 2;
    }

    for (int i = 3; i <= std::sqrt(entry); i += 2) {
        while (entry % i == 0) {
            primeValues.push(i);
            entry /= i;
        }
    }
}