postfix expression with stacks

[react05]

I need some help with postfix expression please. I've only been able to find examples about changing from infix to postfix. With the code provided below, I want it to the following:

1. if the token is an operator (it is a +, -, *, or /)
a. two items are popped off the stack
b. the operator is applied to them
c. the result is pushed back onto the stack
2. if the token is an integer (not a +, -, *, or /)
a. it is pushed onto a stack

any help will be appreciated. thanks.

#include <iostream>
#include <sstream>
using namespace std;

int main()
{
string line;
getline(cin, line);
// Create a string stream that will read from "line"
stringstream ss(line,stringstream::in);

// While there are more tokens...
while (!ss.eof())
{
string token;
ss >> token;

//display token for testing
cout << token << endl;

}; //end while

// The should be one and only one item left on the stack
// print the item at the top of the stack
return 0;
}

[Salem]

So you want to be able to type in say

2 3 +

and then get the answer 5
?

Start with std::stack<int> See a number, push it
See an operator - well you've already described everything.

[react05]

So you want to be able to type in say

2 3 +

and then get the answer 5
?

Start with std::stack<int> See a number, push it
See an operator - well you've already described everything.

Yeah that's exactly what I need it to do.

[WaltP]

Your code is:

#include <iostream>
#include <sstream>
using namespace std;

int main()
{
string line;
getline(cin, line);
// Create a string stream that will read from "line"
stringstream ss(line,stringstream::in);

// While there are more tokens...
while (!ss.eof())
{
string token;
ss >> token;

//display token for testing
cout << token << endl;

Now that you have a token, what do you need to do with it?

}; //end while

// The should be one and only one item left on the stack
// print the item at the top of the stack
return 0;
}

[react05]

Okay this is what I have so far. let me know if i am doing it right please.

#include <iostream>
#include <sstream>
using namespace std;
#include "Stack.h"

int main() 
{
    int i,value1, value2, q, z;
    string line;
    getline(cin, line);
    // Create a string stream that will read from "line"
    stringstream ss(line,stringstream::in);
    
    // While there are more tokens...
    while (!ss.eof()) 
    {
          string token;
          ss >> token;
          
         //display token for testing
         cout << token << endl;
        
         // Put your code for evaluating the expression here!
         for(i=0;i<token;i++)
          {
              if (token[i] != '*' && token[i] != '+' &&token[i] != '/' && token[i] != '-' )
              {
                             push(token[i]);
              }
              else if ( token[i] == '*' || token[i] == '+' || token[i] == '/' || token[i] == '-' )
              {
                   value1 = pop( );
                   value2 = pop( );
                   switch( token[i] )
                   {
                           case '+' : q=value2+value1; break;
                           case '-' : q=value2-value1; break;
                           case '*' : q=value2*value1; break;
                           case '/' : q=value2/value1; break;
                   }
               push (q);
              }
                  z = pop ( );
                  return z; 
           }
																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																																									
    }; //end while

    // The should be one and only one item left on the stack
    // print the item at the top of the stack
    return 0;
}

here's my stack.cpp file to understand it better.

/*-- STACK.cpp-----------------------------------------------------------
 
   This file implements List member functions.
-------------------------------------------------------------------------*/

using namespace std;
#include "Stack.h"

//--- Definition of class constructor
Stack::Stack(int maxSize)
: mySize(0), myCapacity(maxSize)
{
   myArray = new ElementType[maxSize];
 }

//--- Definition of class destructor
Stack::~Stack()
{
   delete [] myArray;
}


//--- Definition of empty()
bool Stack::empty() const
{
   return mySize == 0;
}

//--- Definition of display()
void Stack::display(ostream & out) const
{
   for (int i = 0; i < mySize; i++)
     out << myArray[i] << "  ";
}

//--- Definition of output operator
ostream & operator<< (ostream & out, const Stack & aStack)
{
   aStack.display(out);
   return out;
}

//--- Definition of insert()
void Stack::insert(ElementType item, int pos)
{
   if (mySize == myCapacity)
   {
      cerr << "*** No space for list element -- terminating "
              "execution ***\n";
      exit(1);
   }
   if (pos < 0 || pos > mySize)
   {
      cerr << "*** Illegal location to insert -- " << pos 
           << ".  List unchanged. ***\n";
      return;
   }

   // First shift array elements right to make room for item

   for(int i = mySize; i > pos; i--)
      myArray[i] = myArray[i - 1];

   // Now insert item at position pos and increase list size  
   myArray[pos] = item;
   mySize++;
}

//--- Definition of erase()
void Stack::erase(int pos)
{
   if (mySize == 0)
   {
      cerr << "*** List is empty ***\n";
      return;
   }
  if (pos < 0 || pos >= mySize)
   {
      cerr << "Illegal location to delete -- " << pos
           << ".  List unchanged. ***\n";
      return;
   }

   // Shift array elements left to close the gap
   for(int i = pos; i < mySize; i++)
       myArray[i] = myArray[i + 1];

   // Decrease list size
    mySize--;
}
void Stack::push(ElementType e)
{
   if (mySize < myCapacity - 1)     
   { 
      ++mySize;
      myArray[mySize] = e;
   }
   else
   {
      cerr << "Stack full -- can't add new value\n"
              "Must increase Stack's capacity\n";
      exit(1);
   }
}

ElementType Stack::top() const
{
   if ( !empty() ) 
      return (myArray[mySize]);
   else
   {
      cerr << "Stack is empty -- returning garbage value\n";
      return (myArray[	myCapacity - 1]);
   }
}
void Stack::pop()
{
  if ( !empty() )    // Preserve stack invariant
    mySize--;
  else
    cerr << "Stack is empty -- can't remove a value\n";
}

[Salem]

> let me know if i am doing it right please.
Well it looks OK.
But the real test is for you to run it, and type in some expressions to see what happens.

You might consider actually printing the final result at some point though, just as your comment says you should.

[react05]

> let me know if i am doing it right please.
Well it looks OK.
But the real test is for you to run it, and type in some expressions to see what happens.

You might consider actually printing the final result at some point though, just as your comment says you should.

I tried compiling it but I got quite a few errors.
One of them said "no match for operator<' in' i<token'
and the other 2 said that my pop and my push is undeclared even though I am include the stack.h file

[WaltP]

Start eliminating the errors.

[react05]

I don't understand the errors though.
The first one i have no clue about but the other 2 saying my push and pop are undeclared even though i am including the header file.

[WaltP]

So post the errors. Don't just describe the errors. You are missing most of the relevant information when you just tell us kinda what the error is.

And code goes with the errors.

[react05]

So post the errors. Don't just describe the errors. You are missing most of the relevant information when you just tell us kinda what the error is.

And code goes with the errors.

"no match for operator<' in' i<token' "

for(i=0;i < token; i++)

'push' undeclared

push(token[i]);

'pop' undeclared

value1 = pop( );

[WaltP]

Stop editing the errors. Post the entire error message, from beginning of the line to the end of the line. And although it is good to post the line itself, context is important. Post the entire code.

The last two errors just mean that you have not written the code for the function.

[mitrmkar]

"no match for operator<' in' i<token' "

for(i=0;i < token; i++)

'push' undeclared

push(token[i]);

'pop' undeclared

value1 = pop( );

I think you meant to say ..

for(i=0;i < token.length(); i++)

And for the other two errors, both pop() and push() are methods of the Stack class hence you need an instance of the Stack class in main() . So it would be ..

Stack stk;
stk.push();
stk.pop();

[Salem]

> 'push' undeclared
You need an instance of your stack, and do something like
myStack.push()

> for(i=0;i<token;i++)
token is a string, so what's comparing int with string mean?
Did you mean to examine each token character?

Before you try pushing and popping, try

while (!ss.eof()) 
    {
          string token;
          ss >> token;
          
         //display token for testing
         cout << token << endl;
    }

Until that produces good results, don't waste effort on trying to fix the rest of it.

[react05]

Thanks for the last two replies. It helped.
Now I'm getting an error
in the code marked below.

else if ( token[i] == '*' || token[i] == '+' || token[i] == '/' || token[i] == '-' )
              {
                   value1 = stk.pop( ); ///// void value not ignored as it ought to be
                   value2 = stk.pop( ); ///// void value not ignored as it ought to be
                   switch( token[i] )
                   {
                           case '+' : q=value2+value1; break;
                           case '-' : q=value2-value1; break;
                           case '*' : q=value2*value1; break;
                           case '/' : q=value2/value1; break;
                   }
               stk.push (q);
              }
                  z = stk.pop ( );  ///// void value not ignored as it ought to be
                  return z; 
           }

[jonsca]

value1 = stk.pop( ); doesn't work because pop is void.
Use your top method[/URL] to access the value of the next item on the stack and then pop it off after that with the pop() method.

[react05]

ok i got that part now. I got

value1 = stk.top();
stk.pop( );
value2 =  stk.top();
 stk.pop( );

Where would I enter the output that tells them to enter a postfix expression. Should It be in here?

int main() 
{
    Stack stk;
    int i,value1, value2, value, z;
    string line;
    getline(cin, line);
    // Create a string stream that will read from "line"
    stringstream ss(line,stringstream::in);
    
    // While there are more tokens...
    while (!ss.eof()) 
    {
          string token;
          cout << "Enter postfix expression: " << endl; ////// I entered it right here. Is it right?
          ss >> token;
          
         //display token for testing
         cout << token << endl;

[Salem]

No,
> getline(cin, line);
This reads your entire expression
2 3 +

> ss >> token;
This splits it into tokens
2
3
+

Did you try this bit on it's own like I suggested?

[react05]

Oh ok. So it doesn't ask anything, you just type in 2 3 + as an example.

When it says, There should be one and only one item left on the stack. print the item at the top of the stack. did i do it right in the portion marked below?

while (!ss.eof()) 
    {
          string token;
          ss >> token;
          
         //display token for testing
         cout << token << endl;
        
         // Put your code for evaluating the expression here!
         for(i=0; i < token.length(); i++)
          {
              if (token[i] != '+' && token[i] != ')' &&token[i] != '*' && token[i] != '/' )
              {
                             stk.push(token[i]);
              }
              else if ( token[i] == '+' || token[i] == '-' || token[i] == '*' || token[i] == '/' )
              {
                   value1 = stk.top();
                   stk.pop( );
                   value2 =  stk.top();
                   stk.pop( );
                   switch( token[i] )
                   {
                           case '+' : value = value2+value1; break;
                           case '-' : value = value2-value1; break;
                           case '*' : value = value2*value1; break;
                           case '/' : value = value2/value1; break;
                   }
               stk.push (value);
              }
                 value = stk.top();        /////
                 stk.pop();                   ///// Right Here
                 return value;              ////

           }
														
    }; //end while

[react05]

One last question about this then im done.
it wants me to use

atoi(token.c_str());

to turn the string representation of numbers into int type so you can push them onto the stack for some reason but i dont know what and where to put it. any help please?

[react05]

Nevermind I got it now. however, I keep getting an error saying
"error: switch quantity not an integer"
how would I change that to make it an integer? thanks.

#include <iostream>
#include <sstream>
using namespace std;
#include "Stack.h"

int main() 
{
    Stack stk;
    int i,value1, value2, value, z;
    string line;
    getline(cin, line);
    // Create a string stream that will read from "line"
    stringstream ss(line,stringstream::in);
    
    // While there are more tokens...
    while (!ss.eof()) 
    {
          string token;
          ss >> token;
          
         //display token for testing
         cout << token << endl;
        
         // Put your code for evaluating the expression here!
              if (token != "+" && token != "-" && token != "*" && token != "/" )
              {
                             int num1 = atoi(token.c_str());
                             stk.push(num1);
              }
              else if ( token == "+" || token == "-" || token == "*" || token == "/" )
              {
                   value1 = stk.top();
                   stk.pop( );
                   value2 =  stk.top();
                   stk.pop( );
                   switch( token )
                   {
                           case '+' : value = value2+value1; break;
                           case '-' : value = value2-value1; break;
                           case '*' : value = value2*value1; break;
                           case '/' : value = value2/value1; break;
                   }
               stk.push (value);
              }
                 value = stk.top();
                 stk.pop();
                 cout << "  " << value << endl;

    }; //end while

    // The should be one and only one item left on the stack
    // print the item at the top of the stack
    return 0;
}

[mitrmkar]

"error: switch quantity not an integer"

The token is a std::string , so it cannot be used as such in a switch()/case . But by looking at your current code, you want to do ..

switch( token [ 0 ] )
{
case '+' : value = value2+value1; break;
...

About atoi() , you might be better off using a stringstream for converting the input to a number.
Daniweb surely has many examples of doing that.

[react05]

Oh thankyou! It said that I had to use atoi() even though it's not the best way so that's why i used it.