c++ - 求解后缀表示法方程 c++

Question

对于我的输出，我收到无效分配错误。这是评论中的编辑代码。我唯一没有做的编辑是使用断言宏对“top”函数的更改，这是因为它对我的编译器是未定义的。非常感谢您提供的所有帮助，我看到了曙光!我只需要清除无效分配错误，编译器在调试时打破它时指向 push 函数。

#include "stdafx.h"
#include <iostream>
#include <string>
using namespace std;


void solvePostfix(string postfixStr);

class OperandStack
{
private:
    double * s;  //pointer to 1D dynamic array for storing stack elements
    int capacity,  //stack capacity
        t;  //index of the top element on stack
    void growStack(int newCapacity);  //increases the stack if it is full
                        //must be called from the push function if the stack is full

 public:
    OperandStack(){ capacity = 1; s = NULL; t = -1; };
     OperandStack(int capacity);
     ~OperandStack();
     int size() const;  //return the number of elements in the stack
     bool isFull() const; 
     bool isEmpty() const;
     double top() const;  //returns the element at the top of the stack
                 //without removing it from the stack
     void push(double x);
     void pop();

};

OperandStack :: OperandStack(int capacity)
{ 
    capacity = capacity;
    s = new double [capacity];
    t = -1;
}

OperandStack :: ~OperandStack()
{
    while(this->isEmpty() == false)
    {
        for(int i = 0; i < this->size(); i++)
        {
            this->pop();     
        }
    }
    delete []s;
}

int OperandStack :: size () const
{

    return t+1;
}

bool OperandStack :: isFull() const
{
    return this->size() == capacity;

}

bool OperandStack :: isEmpty() const
{
    if(t == -1) return true;
    else return false;
}

double OperandStack :: top() const
{
    if(this->isEmpty() == false) return s[t];

}


void OperandStack :: push( double x) 
{
    if(this->isFull())
    {
        this->growStack(capacity+(capacity/2));
    }

    else if(this->isEmpty())
    { 
        t = 0; 
        s[t] = x;
    }
    else
    {
        ++t;
        s[t] = x;
    }
}

void OperandStack :: pop()
{
    s[t] = NULL;
    t--;
}

void OperandStack :: growStack(int newCapacity)
{
    double *copyStack = new double[newCapacity];
    for(int i = 0; i < capacity; i++) //Deep copy 
    {
        copyStack[i] = s[i];
    }

    if(s != NULL) delete[] s;
    s = copyStack;
    capacity = newCapacity;
}


void solvePostfix(string postfixStr)
{   
    int i = 0; //The index of a number in the string
    double x, y; //Represent the numbers from the string
    char symbol; //The operator from the string
    OperandStack tempStack;

    while(i < postfixStr.length())
    {
        if(postfixStr[i] >= '0' && postfixStr[i] <= '9')
        {
            tempStack.push(postfixStr[i]-'0');
        }
        else if(postfixStr[i] == '+' || postfixStr[i] == '-'  
            || postfixStr[i] == '*' || postfixStr[i] == '/')
        {
            y = tempStack.top();
            tempStack.pop();
            x = tempStack.top();
            tempStack.pop();
            switch(postfixStr[i])
            {
                case '+': tempStack.push(x + y); break;
                case '-': tempStack.push(x - y); break;
                case '/': tempStack.push(x / y); break;
                case '*': tempStack.push(x * y); break;
            }
        }
        else
        {
            cout << "error- malformed expression.";
        }
        i++;
    }
    cout << "Result: " << tempStack.top() << endl;

}




int main()
{
    OperandStack myStack(8);
    string inputPostfixStr;

    cout << "Enter a postfix expression: ";
    std::getline(cin, inputPostfixStr);

    solvePostfix(inputPostfixStr);

    system("pause");
    return 0;
}

Answer 1

我看到的问题:

1. 在您的默认构造函数中，您将capacity 初始化为0。然后，您正在使用以下语句来增加大小。

   this->growStack(capacity+(capacity/2));
   

   由于 capacity 被初始化为 0，您永远不会真正增加大小。

   解决此问题的一个简单方法是从初始容量 1 开始，或者更改对 growStack 的调用逻辑。

   这是导致您访问您不应该访问的内存的主要问题。结果导致未定义的行为。

2. 您有几个函数在所有路径中都没有 return 语句。

   bool OperandStack :: isFull() const
   {
      if(this->size() == capacity) return true;
      else if(this->size() != capacity) return false;
   }
   

   可以通过以下方式修复:

   bool OperandStack :: isFull() const
   {
      return (this->size() == capacity);
   }
   

   和

   double OperandStack :: top() const
   {
      if(this->isEmpty() == false) return s[t];
   }
   

   可以通过以下方式修复:

   double OperandStack :: top() const
   {
      assert(this->isEmpty() == false);
      return s[t];
   }
   

3. 您在调用 push 时使用了错误的参数。

    tempStack.push(postfixStr[i]);
   

   应该是:

    tempStack.push(postfixStr[i]-'0');
   

4. 读取字符串形式的表达式的代码不对。

    cin >> inputPostfixStr;
   

   遇到空格时将停止读取输入。当您输入“1 1 +”时，执行该行后，inputPostfixStr 的值将为“1”。将该行更改为:

   std::getline(cin, inputPostfixStr);
   

5. OperandStack(int capacity) 的实现不正确。

   OperandStack :: OperandStack(int capacity)
   { 
       capacity = capacity;
       s = new double [capacity];
       t = -1;
   }
   

   您有两个名为capacity 的变量——函数的参数和类的成员变量。但是，在函数内部，成员函数隐藏了成员变量。结果，成员变量没有被初始化。如果您最终使用此构造函数，您将遇到未定义的行为。

   换行

       capacity = capacity;
   

   到

       this->capacity = capacity;
   

6. push 中的if-else 逻辑不正确。

   void OperandStack :: push( double x) 
   {
       if(this->isFull())
       {
           // this->growStack(capacity+(capacity/2));
           // This will be a problem if the initial size is zero or 1
           // 1/2 == 0. Change it appropriately.
       }
   
       // Using the `else` here is a problem.
       // If you do, when the stack is full, the stack is grown but 
       // nothing is added to the stack.
       // else if(this->isEmpty())
   
       if(this->isEmpty())
       { 
           t = 0; 
           s[t] = x;
       }
       else
       {
           ++t;
           s[t] = x;
       }
   }