Reputation: 11

Solving Postfix Notation Equations c++

For my output I am getting an invalid allocation error. Here is the edited code from the comments. The only edit I did not make is the change to the "top" function using the assertion macro, this is because it is undefined to my compiler. Thank you so very much for all the help, I see the light! I just need to clear the invalid allocation error, the compiler points to the push function when I break it during debugging.

#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;
}

Upvotes: 0

Answers (2)

R Sahu

Reputation: 206567

Problems I see:

In your default constructor, you are initializing capacity to 0. And then, you are you using the following statement to increase the size.
```
this->growStack(capacity+(capacity/2));
```
Since capacity is initialized to 0, you never really grow the size.

A simple fix to this problem is to start with an initial capacity of 1, or change the logic in the call to growStack.

That is the main problem that's causing you to access memory that you are not supposed to be able access. Undefined behavior ensues as a result.

You have couple of functions that don't have a return statement in all the paths.

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

can be fixed by using:

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

And

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

can be fixed by using:

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

You are using the wrong argument in the calls to push.

 tempStack.push(postfixStr[i]);

should be:

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

The code to read the expression in string form is not right.
```
 cin >> inputPostfixStr;
```
will stop reading input when it encounters a whitespace. When your input is "1 1 +", after that line is executed, the value of inputPostfixStr will be "1". Change that line to:
```
std::getline(cin, inputPostfixStr);
```
The implementation of OperandStack(int capacity) not right.
```
OperandStack :: OperandStack(int capacity)
{ 
    capacity = capacity;
    s = new double [capacity];
    t = -1;
}
```
You have two variables named capacity -- the argument to the function and member variable of the class. However, inside the function, the member function shadows the member variable. As a consequence, the member variable is not initialized. If you end up using this constructor, you will run into undefined behavior.

Change the line
```
    capacity = capacity;
```
to
```
    this->capacity = capacity;
```

The if-else logic in push is not correct.

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;
    }
}

Upvotes: 1

meneldal

Reputation: 1737

The error comes from the way you're putting data in your stack

        if(postfixStr[i] >= '0' && postfixStr[i] <= '9')
        {
            tempStack.push(postfixStr[i]);
        }

A compiler should have given you a warning for this. postfixStr[i] is a char and it makes no sense to convert it implicitly to double. This is why you are getting completely wrong values for x and y (and in the end bad results).

Upvotes: 0

Solving Postfix Notation Equations c++

Answers (2)

Related Questions