Add every value in stack

Question

I am trying to figure out a method that will add every value in a stack.

The goal is to use that value to determine if all the values in the stack are even. I have written to code to do this

template <class Object>
bool Stack<Object>::objectIsEven( Object value ) const {
     bool answer = false;
     if (value % 2 == 0)
          answer = true;
     return( answer );
}

However, I am stumped on how to add all of the stack's values in a separate method

Stack.cpp

#ifndef STACK_CPP
#define STACK_CPP

#include "Stack.h"

namespace cs20 {

template <class Object>
Stack<Object>::Stack() {
    topNode = NULL;
}

template <class Object>
Stack<Object>::Stack( const Stack<Object>& rhs ) {
    topNode = NULL;
    *this = rhs;
}

template <class Object>
Stack<Object>::~Stack() {
    makeEmpty();
    delete topNode;
}

template <class Object>
bool Stack<Object>::isEmpty() const {
    return( (topNode == NULL) );
}

template <class Object>
bool Stack<Object>::even() const
    {

    }
// template Object must support the % operator which ints do
template <class Object>
bool Stack<Object>::objectIsEven( Object value ) const {
    bool answer = false;
    if (value % 2 == 0)
        answer = true;
    return( answer );
}


template <class Object>
void Stack<Object>::makeEmpty() {
    while (!isEmpty()) {
        pop();
    }
}


template <class Object>
void Stack<Object>::push( const Object& data ) {
    StackNode<Object>* newNode = new StackNode<Object>( data, topNode );
    topNode = newNode;
}

template <class Object>
void Stack<Object>::pop() {
    if (isEmpty()) {
        throw EmptyStack();
    }
    StackNode<Object> *oldTop = topNode;
    topNode = topNode->getNext();
    delete oldTop;
}

template <class Object>
const Object& Stack<Object>::top( ) const {
    if (isEmpty()) {
        throw EmptyStack();
    }
    StackNode<Object> node = *topNode;
    return( node.getElement() );
}

template <class Object>
Object Stack<Object>::topAndPop( ) {
    Object o = top();
    pop();
    return( o );
}

// Deep copy of linked Stack
template <class Object>
const Stack<Object>& Stack<Object>::operator =( const Stack<Object>& rhs ) {
    if (this != &rhs) {
        makeEmpty();
        if (!(rhs.isEmpty())) {
            StackNode<Object> * rhsTopNode = rhs.topNode;
            StackNode<Object> * myTopNode = new StackNode<Object>( rhsTopNode->getElement() );
            topNode = myTopNode;

            rhsTopNode = rhsTopNode->getNext();
            while (rhsTopNode != NULL) {
                myTopNode->setNext( new StackNode<Object>( rhsTopNode->getElement() ) );
                myTopNode = myTopNode->getNext();
                rhsTopNode = rhsTopNode->getNext();
            }
        }
    }
    return( *this );
}

template <class Object> 
std::ostream& Stack<Object>::printStack( std::ostream& outs ) const {
    if (isEmpty()) {
        outs << "Empty Stack";
    }
    else {
        outs << "TOP: ";
        StackNode<Object> * node = topNode;
        while (node != NULL) {
            outs << node->getElement();
            outs << "\n     ";           /// for visual alignment
            node = node->getNext();
        }
    }
    return( outs );
}

}

#endif

Answer 1

can't you define your getSum() function in the stack implementation? Or is there any restrictions?

Sol-1:

template <class Object> 
Object Stack<Object>::getSum( ) {
    Object sum = 0;  // or memset or other stuffs
    StackNode<Object> * node = topNode;
    while (node != NULL) {
        sum += node->getElement();
        node = node->getNext();
    }
    return sum;
}

As Gary mentioned you can also improve efficiency by caching the sum value every time you push or pop (i,e stack is changed) Sol-2:

Add a member property which will denote the sum (e,g - sum)

template <class Object>
Stack<Object>::Stack() {
    topNode = NULL;
    this->sum = 0; // initialize or new object
}

update the sum whenever a object is pushed

template <class Object>
void Stack<Object>::push( const Object& data ) {
    StackNode<Object>* newNode = new StackNode<Object>( data, topNode );
    topNode = newNode;
    this->sum = this->sum + data;
}

same update goes for pop() whenever an object is removed

template <class Object>
void Stack<Object>::pop() {
    if (isEmpty()) {
        throw EmptyStack();
    }
    StackNode<Object> *oldTop = topNode;
    topNode = topNode->getNext();
    this->sum = this->sum - oldTop->getElement();
    delete oldTop;
}

now your last function getSum()

template <class Object> 
    Object Stack<Object>::getSum( ) {
        return this->sum;
    }

Sol-1 has O(N) = N cost while Sol-2 has O(N) = 1

Now you should be able to use pStack->objectIsEven(pStack->getSum());

I think you aren't required to be concerned about threading in your stack implementation otherwise you should use some kind of synchronization mechanism while insert/delete operation to make the stack consistent.

Hope this helps. regards,

Answer 2

Use this example:

Just keep the sum in a local, and pop the values off of the stack one at a time:

void MathStack::addAll()
{
    int num = 0, sum = 0;

    while(!isEmpty())
    {
        pop(num);
        sum += num;
    }

    push(sum);
}