将中缀转换为前缀表示法

Question

我有一个任务：编写一个程序 (C++)，将 "infix" 符号转换为 "prefix" 并使用自己的 "stack and queue" 实现。

但我得到："Critical error detected c0000374" 和 "Free Heap block modified at ... after it was freed" 在 void main() { /*...*/ system("pause"); } 的最后一个字符串或 void toPrefix();

的最后一个字符串

有人可以帮我指出我的错误吗？

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

嗯...我觉得是你的问题Stack class.

您传递给 toPrefix() 的字符串是 "9-(2+2)"

所以你 Stack<char> OpStack 中定义的 toPrefix() 中的操作是（如果我理解得很好的话）

使用默认（无参数）构造函数构造
push()对应-
pop()对应od (
push()对应+
push()对应)

好吧，让我们看看里面发生了什么

1）用默认构造函数构造后

我们有

1a) size == 0

1b) first、last、first->next 和 last->next 指向相同的已分配内存区域

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

2) 在第一次调用 push() 之后（使用 -）

我们有

2a) size == 1

2b) first、last、first->next 和 last->next 指向相同的已分配内存区域

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

3) 第一次调用后pop()

我们有

3a) size == 0

3b) first、last、first->next 和 last->next 指向相同的 DELETED 内存区域

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

4) 第二次调用push() (with +)

4a) size 递增

4b) 写入(last->value = value;)在DELETED区域

4c) 在DELETED区域再次写入(last->next = first;)

我想这可以解释你的问题。

p.s.: Rambo Ramon 和 Sam Varshavchik 的 "use a debugger" 建议是个好建议（恕我直言）

p.s.2：抱歉我的英语不好

将中缀转换为前缀表示法

Convert Infix to Prefix Notation

c++

stack

queue

polish-notation