Convert Infix to Prefix Notation

Question

I have a task: make a program (C++), which converts "infix" notation to "prefix" and uses own "stack and queue" realizations.

But I get: "Critical error detected c0000374" and "Free Heap block modified at ... after it was freed" at last string of void main() { /*...*/ system("pause"); } or at last string of void toPrefix();

Can somebody help me and point out my mistake(s), please?

Source.cpp:

#include "iostream"
#include "fstream"
#include "string"
#include "Stack.h"
#include "Queue.h"

void toPrefix(const std::string& first)
{
    int length = first.length();
    char test = NULL, operand = NULL;
    char *ptr = &test, *op_ptr = &operand;
    Queue<char> List;
    std::string Output;
    Stack<char> OpStack;
    for (int i = length - 1; i >= 0; i--) List.push(first[i]); //
    while (List.getsize() != 0)
    {
        List.pop(ptr);
        if (test >= 48 && test <= 57) //is it number?
        {
            Output.insert(Output.begin(), test);
        }
        if (test == '*' || test == '/' || test == '-' || test == '+')
        {
            OpStack.push(test);
        }
        if (test == ')')
        {
            OpStack.push(test);
        }
        if (test == '(')
        {
            OpStack.pop(op_ptr);
            while (operand != ')')
            {
                Output.insert(Output.begin(), operand);
                OpStack.pop(op_ptr);
            }
        }
    }
}

void main()
{
    const std::string& first = "9-(2+2)";
    toPrefix(first);
    system("pause");
}

Queue.h:

#include<iostream>

template <typename T>
class Queue
{
private:
    struct queue_element
    {
        T value;
        queue_element *next;
    };

    queue_element *first;
    queue_element *last;
    int size;

public:
    Queue()
    {
        first = new(queue_element);
        last = first;
        first->value = -1;
        first->next = 0;
        size = 0;
    }
    Queue(T x)
    {
        first = new(queue_element);
        last = first;
        first->value = x;
        first->next = 0;
        size = 1;
    }

    int getsize()
    {
        return size;
    }

    void push(T value)
    {
        if (size == 0)
        {
            size++;
            last = first;
            first->value = value;
            first->next = 0;
        }
        else
        {
            size++;
            queue_element *temp = new(queue_element);
            temp->next = 0;
            temp->value = value;
            last->next = temp;
            last = temp;
        }
    }

    void pop(T* ret)
    {
        if (size == 0)
        {
            std::cout << "Queue is empty!" << std::endl;
            return;
        }
        queue_element *temp = first;
        *ret = first->value;
        first = first->next;
        size--;
    }

    void peek(T *ret)
    {
        if (size == 0)
        {
            std::cout << "Queue is empty!" << std::endl;
            return;
        }
        *ret = first->value;
    }
};

Stack.h

#include <iostream>

template <typename T>
class Stack
{
private:
    struct stack_element
    {
        T value;
        stack_element *next;
    };
    stack_element *first;
    stack_element *last;
    int size;

public:
    Stack()
    {
        last = new(stack_element);
        first = last;
        last->value = -1;
        last->next = first;
        size = 0;
    }
    Stack(T x)
    {
        last = new(stack_element);
        first = last;
        last->value = x;
        last->next = 0;
        size = 1;
    }

    int getsize()
    {
        return size;
    }

    void push(T value)
    {
        if (size == 0)
        {
            size++;
            last->value = value;
            last->next = first;
        }
        else
        {
            size++;
            stack_element *temp = new(stack_element);
            temp->next = last;
            temp->value = value;
            last = temp;
        }
    }

    void pop(T* ret)
    {
        if (size == 0)
        {
            std::cout << "Stack is empty!" << std::endl;
            return;
        }
        stack_element *temp = last;
        *ret = last->value;
        last = last->next;
        delete temp;
        size--;
    }

    void peek(T *ret)
    {
        if (size == 0)
        {
            std::cout << "Stack is empty!" << std::endl;
            return;
        }
        *ret = first->value;
    }
};

Answer 1

Well... I think that the problem is in you Stack class.

The string that you pass to toPrefix() is "9-(2+2)"

So the operation in you Stack<char> OpStack, defined in toPrefix(), are (if I understand well)

1. construction with default (no arguments) constructor

2. push() in correspondence of -

3. pop() in correspondence od (

4. push() in correspondence of +

5. push() in correspondence of )

Well, let's see what's is happening in it

1) after the construction with default constructor

we have

1a) size == 0

1b) first, last, first->next and last->next that are pointing to the same allocated memory area

1c) first->value == last->value == (char)-1

2) after the first call to push() (with -)

we have

2a) size == 1

2b) first, last, first->next and last->next that are pointing to the same allocated memory area

2c) first->value == last->value == '-'

3) after the first call to pop()

we have

3a) size == 0

3b) first, last, first->next and last->next that are pointing to the same DELETED memory area

3c) first->value == last->value == '-'

4) calling for the second time push() (with +)

4a) size is incremented

4b) is written (last->value = value;) in a DELETED area

4c) is written again (last->next = first;) in a DELETED area

I suppose that this can explain your problem.

p.s.: the "use a debugger" suggestion from Rambo Ramon and Sam Varshavchik is a good suggestion (IMHO)

p.s.2: sorry for my bad English