2

我正在尝试编写一个程序来计算后缀表达式，它包括驱动程序和实现文件。这两个如下图所示：

#include <cstdlib>
#include <iostream>
#include <string>
#include "Stack.h"

using namespace std;

void printStack(Stack<float>);

int main()
{
 Stack<float> postFix;
 float userIn, operand1, operand2;
 // while the end of the postfix hasn't been reached
 do
 { 
   // prompt user for next number or modulus command
   cout << "ENTER: ";
   if (!postFix.isEmpty()) printStack(postFix);
   string userInput;
   cin >> userInput;

   // If user input is q or Q then terminate program
   if (userInput == "q" || userInput == "Q") return 0;
   else
   {
     // read next token by parsing userInput
     // if token is a number push it onto stack
  if (userInput != "+" && userInput != "/" && userInput != "*" && userInput != "-")
  {
    userIn = atof(userInput.c_str());
    postFix.push(userIn);
  }
  else if (!(postFix.size() < 2))
  {
    // if it's not a number then pop element from the stack and call it
    // operand2
    operand2 = postFix.lastElem();
    postFix.pop();

    // pop another element from the stack; call it operand1
    operand1 = postFix.lastElem();
    postFix.pop();

    // Perform the operation: operand1 token operand2 and
    // push the result of the operation onto the stack
    if (userInput == "/")
      postFix.push((operand1 / operand2));
    else if (userInput == "*")
      postFix.push((operand1 * operand2));
    else if (userInput == "+")
      postFix.push((operand1 + operand2));
    else if (userInput == "-")
      postFix.push((operand1 - operand2));
  }
  else if (postFix.size() < 2)
    cout << "Stack is too small, request ignored\n";
} // end else

} while (!postFix.isEmpty()); // end while

// empty the stack
postFix.makeEmpty();

return 0;
}

// The problem is in the print function!

void printStack(Stack<float> postFix)
{
  do
  {
    cout << postFix.lastElem() << " ";
    postFix.pop();
  } while (!postFix.isEmpty());
}

我的实现文件显示在这里：

#include <iostream>
using namespace std;

template <class DataType>
class Stack
{
  public:
  Stack() // constructor
  {
    capacity = 2;
    //Stack(capacity);
    elements = new DataType[capacity];
    top = -1;
  }

  Stack(int s) // constructor with one parameter
  {
    capacity = s;
    elements = new DataType[capacity];
    top = -1;
  }

~Stack()
{
  delete [] elements;
}

bool isEmpty() const {return -1 == top;}

void pop() // pop function
{
  //if (-1 == top) return; // failed
  top--;
  if (top > 2 && top < (capacity / 4))
  {
    capacity /= 2;
    changeSize(capacity);
  }
}

DataType & lastElem()
{
  return elements[top];
}

int size() {return top;}

void push(float parameter) // push function
{
  if (++top == capacity)
  {
    capacity *= 2;
    changeSize(capacity);
  }
  elements[top] = parameter;
}

bool peek(DataType& parameter) const
{
  if (-1 == top) return false; // failed
  parameter = elements[top];
  return true; // success
}

inline DataType & operator=(const Stack<DataType>& a)
{
  if (this != &a)
  {
    delete [] elements;
    elements = 0;
    capacity = a.capacity;
    if (capacity > 0)
      elements = new DataType[capacity];
    for (int i = 0; i < capacity; i++)
      elements[i] = a.elements[i];
    top = a.top;
  }
  return *this;
}

void changeSize(float newSize) // function for changing the array size if it's too small
{
  DataType *newArray = new DataType[(int)newSize];
  int limit = (newSize > capacity)? capacity : newSize;

  for (int i = 0; i < limit; i++)
  {
    newArray[i] = elements[i];
  }
  delete [] elements;
  elements = newArray;
  capacity = newSize;
}

void makeEmpty() {top = -1;}

private:
  DataType* elements;
  int capacity;
  int top; // track newest value 
};

使用 g++ 编译此程序后，我最多可以输入两个值，直到出现如下所示的奇怪内存错误：

ENTER: 23
ENTER: 23 43
*** glibc detected *** ./calc: double free or corruption (fasttop): 0x0000000000c86010 ***
======= Backtrace: =========
/lib/libc.so.6(+0x78b06)[0x7fbd11e4ab06]
/lib/libc.so.6(cfree+0x73)[0x7fbd11e513d3]
./calc[0x401197]
./calc[0x400d9b]
/lib/libc.so.6(__libc_start_main+0xfd)[0x7fbd11df0c4d]
./calc[0x400c09]
======= Memory map: ========
00400000-00402000 r-xp 00000000 08:06 788295                             /home/badr/Documents/My programs/COMSC-210/calc
00601000-00602000 r--p 00001000 08:06 788295                             /home/badr/Documents/My programs/COMSC-210/calc
00602000-00603000 rw-p 00002000 08:06 788295                             /home/badr/Documents/My programs/COMSC-210/calc
00c86000-00ca7000 rw-p 00000000 00:00 0                                  [heap]
7fbd0c000000-7fbd0c021000 rw-p 00000000 00:00 0 
7fbd0c021000-7fbd10000000 ---p 00000000 00:00 0 
7fbd11dd2000-7fbd11f4f000 r-xp 00000000 08:06 5813                       /lib/libc-2.11.1.so
7fbd11f4f000-7fbd1214e000 ---p 0017d000 08:06 5813                       /lib/libc-2.11.1.so
7fbd1214e000-7fbd12152000 r--p 0017c000 08:06 5813                       /lib/libc-2.11.1.so
7fbd12152000-7fbd12153000 rw-p 00180000 08:06 5813                       /lib/libc-2.11.1.so
7fbd12153000-7fbd12158000 rw-p 00000000 00:00 0 
7fbd12158000-7fbd1216e000 r-xp 00000000 08:06 1268                       /lib/libgcc_s.so.1
7fbd1216e000-7fbd1236d000 ---p 00016000 08:06 1268                       /lib/libgcc_s.so.1
7fbd1236d000-7fbd1236e000 r--p 00015000 08:06 1268                       /lib/libgcc_s.so.1
7fbd1236e000-7fbd1236f000 rw-p 00016000 08:06 1268                       /lib/libgcc_s.so.1
7fbd1236f000-7fbd123f1000 r-xp 00000000 08:06 5814                       /lib/libm-2.11.1.so
7fbd123f1000-7fbd125f0000 ---p 00082000 08:06 5814                       /lib/libm-2.11.1.so
7fbd125f0000-7fbd125f1000 r--p 00081000 08:06 5814                       /lib/libm-2.11.1.so
7fbd125f1000-7fbd125f2000 rw-p 00082000 08:06 5814                       /lib/libm-2.11.1.so
7fbd125f2000-7fbd126e8000 r-xp 00000000 08:06 322753                     /usr/lib/libstdc++.so.6.0.13
7fbd126e8000-7fbd128e8000 ---p 000f6000 08:06 322753                     /usr/lib/libstdc++.so.6.0.13
7fbd128e8000-7fbd128ef000 r--p 000f6000 08:06 322753                     /usr/lib/libstdc++.so.6.0.13
7fbd128ef000-7fbd128f1000 rw-p 000fd000 08:06 322753                     /usr/lib/libstdc++.so.6.0.13
7fbd128f1000-7fbd12906000 rw-p 00000000 00:00 0 
7fbd12906000-7fbd12926000 r-xp 00000000 08:06 5815                       /lib/ld-2.11.1.so
7fbd12afa000-7fbd12afe000 rw-p 00000000 00:00 0 
7fbd12b21000-7fbd12b25000 rw-p 00000000 00:00 0 
7fbd12b25000-7fbd12b26000 r--p 0001f000 08:06 5815                       /lib/ld-2.11.1.so
7fbd12b26000-7fbd12b27000 rw-p 00020000 08:06 5815                       /lib/ld-2.11.1.so
7fbd12b27000-7fbd12b28000 rw-p 00000000 00:00 0 
7fff78cf3000-7fff78d08000 rw-p 00000000 00:00 0                          [stack]
7fff78dff000-7fff78e00000 r-xp 00000000 00:00 0                          [vdso]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0                  [vsyscall]
ENTER: 43 0 Aborted

经过多次调试，我确定问题一定出在 .cpp 文件中的打印函数中：

// The problem is in the print function!

void printStack(Stack<float> postFix)
{
  do
  {
    cout << postFix.lastElem() << " ";
    postFix.pop();
  } while (!postFix.isEmpty());
}

我只是无法弄清楚它为什么会发生或如何克服它。

4

1 回答 1

3

void printStack(Stack<float> postFix)通过 value获取参数，因此制作了一个副本。使用编译器生成的复制构造函数。哪个是浅拷贝。你需要实现你自己的，做一个深拷贝。

您已经有一个复制赋值运算符 ( operator =) 和一个析构函数。这是正确的，但还不够。这 2 加上复制构造函数Stack(const Stack<DataType>& other)构成了三的规则。如果您需要其中之一，则需要全部。通常，当你在课堂上管理记忆时，你需要它们，你就是这样。

实现类似于operator =：

DataType(const Stack<DataType>& a)
{
    elements = 0;
    capacity = a.capacity;
    if (capacity > 0)
      elements = new DataType[capacity];
    for (int i = 0; i < capacity; i++)
      elements[i] = a.elements[i];
    top = a.top;
}

此外，以防万一这不是出于教育目的，您可以使用std::stack标题中的预实现。<stack>

于 2012-10-21T00:04:18.003 回答