data structre stack

[samytaqq]

Write a C++ program that asks the user to enter an integer n followed by n numbers. The program will use 2 stacks to enter the numbers entered by the user. In every iteration the program will balance the total of the numbers stored in every stack. For example, if the user already entered 10 (the program stores this value in stack 1) and 23.5 (the program stores this value in stack 2) and then enters the value 4.7 then the program will store this value in stack 1 since 10<23.5. If the user enters 12.3, then the program will store it in stack 1 since the total in stack 1 is 14.7 (10+4.7) and 14.7<23.5. If the user enter 7, then the program will store this value in stack 2 since the total in stack 1 is 27 (14.7+12.3) and 27>23.5.
At the end, the program will display on the screen the content of every stack.

[zeroliken]

What have you coded so far? is there a specific problem you need help with?

[TrustyTony]

Are you sure you are not going against MEMBER RULES ?

[m4ster_r0shi]

Oh, come on, guys, don't be so harsh. Let's help him get started...

You could use two big sized arrays to represent your stacks. You'll have to also use two integers (initialized to zero) to keep track of each stack's current size. When you want to add a number to a stack, put it to stack[cur_size] and then increment cur_size by one. Don't forget to make sure that your arrays (stacks) are of the appropriate data type (look at the numbers the user is allowed to enter). You can easily get the sum of each stack at any time using a loop. The main part of your program would also be one big loop whose body is repeated n times.

Show us what you can make out of that, and we'll gladly help you more.

Now, this looked like a good metaprogramming exercise and I was bored, so I gave it a shot...

main.cpp

#include <boost/preprocessor/seq/for_each.hpp>
#include <boost/preprocessor/seq/seq.hpp>

#include <boost/mpl/push_back.hpp>
#include <boost/mpl/pop_front.hpp>
#include <boost/mpl/for_each.hpp>
#include <boost/mpl/front.hpp>
#include <boost/mpl/deque.hpp>
#include <boost/mpl/fold.hpp>
#include <boost/mpl/plus.hpp>
#include <boost/mpl/if.hpp>

#include <iostream>

#define MAKE_MPL_INTS(r, data, elem) ,int_< elem >
#define MAKE_MPL_INT(elem) int_< elem >

#define APPLY_OP_STEPS(r, data, elem) ::apply::result
#define APPLY_OP_STEP apply::result

#define input_seq (0)(8)(7)(2)(4)(1)(3)(5)(6)(9)

using namespace boost::mpl;

template <class container> struct sum { typedef typename fold<container, int_<0>, plus<_1, _2> >::type type; };

template <class input_, class stack1_, class stack2_>
struct state { typedef input_ input; typedef stack1_ stack1; typedef stack2_ stack2; };

template <class state_>
struct op_step
{
    typedef state_ cur_state;

    struct apply
    {
        typedef typename cur_state::stack1 stack1;
        typedef typename cur_state::stack2 stack2;
        typedef typename cur_state::input input;

        typedef typename sum<stack1>::type sum1;
        typedef typename sum<stack2>::type sum2;

        static const bool condition = sum1::value <= sum2::value;

        typedef typename if_c< condition, stack1, stack2>::type stack_to_extend;
        typedef typename if_c<!condition, stack1, stack2>::type unchanged_stack;

        typedef typename push_back<stack_to_extend, typename front<input>::type >::type extended_stack;

        typedef typename pop_front<input>::type new_input;

        typedef typename if_c< condition, extended_stack, unchanged_stack>::type new_stack1;
        typedef typename if_c<!condition, extended_stack, unchanged_stack>::type new_stack2;

        typedef op_step<state<new_input, new_stack1, new_stack2> > result;
    };
};

struct printer { template<class T> void operator()(T val) { std::cout << val << ' '; } };

int main()
{
    typedef deque<
        MAKE_MPL_INT(BOOST_PP_SEQ_HEAD(input_seq))
        BOOST_PP_SEQ_FOR_EACH(MAKE_MPL_INTS, ~, BOOST_PP_SEQ_TAIL(input_seq))
    > input;

    typedef deque<> stack1;
    typedef deque<> stack2;

    typedef op_step<state<input, stack1, stack2> >::
        APPLY_OP_STEP BOOST_PP_SEQ_FOR_EACH(APPLY_OP_STEPS, ~, BOOST_PP_SEQ_TAIL(input_seq))
    ::cur_state result;

    std::cout << "stack1 elements: "; for_each<result::stack1>(printer()); std::cout << std::endl;
    std::cout << "stack2 elements: "; for_each<result::stack2>(printer()); std::cout << std::endl;

    return 0;
}

stdout

stack1 elements: 0 8 4 5 9
stack2 elements: 7 2 1 3 6

I tried to write a metafunction and use it with mpl::fold but it didn't work out well (I didn't bother too much either...), so I ended up using preprocessor stuff for the main loop. If anyone can do it using a custom metafunction and mpl::fold (or, at least, in a pure mpl way, not involving the preprocessor), I'd like to see it.

(I know APPLY_OP_STEP isn't really necessary, but I really wanted the scope resolution operator to appear twice around that part in main...)

[TrustyTony]

I am sure this guy can pass also his next course if he gets 50 % of your post oh Mysterious master!

For me the loop is against the general idea of the stack so I would add one variable for total of stack for each stack. What this assignement is benefitting from using stack I have no idea. It only reverses the order of inputs.

I must say that my understanding of required logic from description is less than perfect, here my pseudocode (OK it is runnable Python code, but I am who am I), the last bit in docstring use example with Master's input gives different stacks than he gives.

def stacker(input_seq):
    """ 
    >>> stacker([10,23.5, 12.3])
    22.3 [10, 12.3] 23.5 [23.5]
    >>> stacker([10,23.5, 7])
    17 [10, 7] 23.5 [23.5]
    >>> stacker([10,23.5, 12.3, 7])
    22.3 [10, 12.3] 30.5 [23.5, 7]
    >>> stacker([10,23.5, 4.7, 12.3, 7])
    21.7 [10, 4.7, 7] 35.8 [23.5, 12.3]
    >>> stacker([10,23.5,12.3,7])
    22.3 [10, 12.3] 30.5 [23.5, 7]
    >>> stacker([0, 8, 7, 2, 4, 1, 3, 5, 6, 9])
    17 [0, 7, 1, 3, 6] 28 [8, 2, 4, 5, 9]
    >>>
    """
    stack1, stack2 = [], []
    for item in input_seq:
        if not stack1 or sum(stack1) + item <= sum(stack2):
            stack1.append(item)
        else:
            stack2.append(item)
    print sum(stack1), stack1, sum(stack2), stack2

[m4ster_r0shi]

I am sure this guy can pass also his next course if he gets 50 % of your post oh Mysterious master!

:) :) :) I'm sure he'll eventually be able to get 100 % of it.

For me the loop is against the general idea of the stack so I would add one variable for total of stack for each stack.

Ah, right. After all, a stack is supposed to only allow access on the topmost element (I forgot that restriction in the code above too...).

EDIT:

the last bit in docstring use example with Master's input gives different stacks than he gives

Yes, that's because, in python terms, my code looks like...

if sum(stack1) <= sum(stack2):

instead of...

if not stack1 or sum(stack1) + item <= sum(stack2):