?
Solved

evaluating a postfix expression

Posted on 2001-06-28
11
Medium Priority
?
606 Views
Last Modified: 2012-05-04
dear expert!

please find why the below given program is saying "stack overflow", when i gave some postfix expression (say 65+)?

my program:

#include <iostream.h>

const int max = 50;
char exp[50];
int upper;
int lower;

class stack
{
public:
     char st[max];
     int top;
public:
     stack()
     {
          top=0;
     }
     void push(int var)
     {
          if(top>=max)
          {
               cout<<"stack overflow";
          }
          else
          {
          st[++top]=var;
         
          }

     }
     int pop()
     {
          if(top<0)
          {
               cout<<"stack underflow";
          }
          else
          {
          return st[top--];
          }

     }

     int isempty()
     {
          if(top==0)
          {
               return 1;
          }
          else
          {
               return 0;
          }
     }
};

void main()
{
     stack s1;
     
     cout<<"Enter a postfix expression\n";
     cin>>exp;

     
     for (int i=0;i<50;++i)
     {
          while(!(exp[i]=='\0'))
          {
                         
          if((exp[i]=='+')|(exp[i]=='-')|(exp[i]=='*')|(exp[i]=='/'))
          {
               switch(exp[i])
               {
               case '+':
                    upper=s1.pop();
                    lower=s1.pop();
                    s1.push(int(upper+lower));
               case '-':
                    upper=s1.pop();
                    lower=s1.pop();
                    s1.push(int(upper-lower));
               case '*':
                    upper=s1.pop();
                    lower=s1.pop();
                    s1.push(int(upper*lower));
               case '/':
                    upper=s1.pop();
                    lower=s1.pop();
                    s1.push(int(upper/lower));
               }//end of switch
          }//end of if

          else
          {
               s1.push(int(exp[i]));

          }//end of else

          }//end of while
     }//end of for

     cout<<s1.pop();

     
}//end of main
0
Comment
Question by:wowshekar
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 5
  • 4
  • 2
11 Comments
 
LVL 30

Expert Comment

by:Axter
ID: 6236139
What compiler are you using?
What OS?
What posix expersion?

Please provide a lot more details.
0
 

Author Comment

by:wowshekar
ID: 6236444
iam using windows os. but its not that important here.just some where iam doing some mistake in my code. please find that.
0
 
LVL 30

Expert Comment

by:Axter
ID: 6236506
All the information is important if you want help.
What compiler, and what posix expresion?

If you want help, you really need to provide as much information as possible.  Especially considering you only assigned 20 points for this question.
50-Easy
100-regular
200-hard

With out getting additional information from you, this question is hard.
0
Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

 

Author Comment

by:wowshekar
ID: 6236543
dear axter!
it is postfix and not posix. iam using microsoft visual studio and i dont know what compiler iam using but the os is windows 200
0
 

Author Comment

by:wowshekar
ID: 6236721
dear axter!
it is postfix and not posix. iam using microsoft visual studio and i dont know what compiler iam using but the os is windows 200
0
 

Expert Comment

by:wkmatt42
ID: 6236951
You're filling your stack with the first character you type. Check your looks:

for (int i = 0; i < 50; ++i)
{
    while (!(exp[i]=='\0')) // change this to exp[i] != '\0' or simply exp[i]
    {
        ....
    }
}

The inner loop will never end if the first character input is not '\0'. Fixing that probem (by eliminating either the for or the while loop and fixing the one that remains) will lead to a different bug - this time probably a stack underflow because you are missing the "break;" statements in your switch.

This code will work (I'm not reprinting the stack class since it works):

void main()
{
    stack s1;
   
    char exp[50];
    cout<<"Enter a postfix expression\n";
    cin>>exp;

    int i = 0;
    while (i < 50  &&  exp[i] != '\n')
    {
        if (isdigit(exp[i]))
        {
             s1.push(exp[i] - '0');
        }
        else if((exp[i]=='+') || (exp[i]=='-') || (exp[i]=='*') || (exp[i]=='/'))
        {
             switch(exp[i])
             {
             case '+':
                 s1.push(s1.pop() + s1.pop());
                 break;
             case '-':
                 s1.push(s1.pop() - s1.pop());
                 break;
             case '*':
                 s1.push(s1.pop() * s1.pop());
                 break;
             case '/':
                 s1.push(s1.pop() / s1.pop());
                 break;
             }
        }
        else
        {
            cout << "ignoring input character " << i << endl;
        }

        ++i;

    }   // end of for

    cout << s1.pop();

}//end of main

There are some semantic issues I'm tempted to address, but I'll restrain myself. Here are the bugs in your original post:

1. The loop thing I already mentioned above - I replaced the for and while with a single while loop.
2. The code in a case statement should almost always include a break; statement before the next case. If it's not there, the next line of code will be executed. So, in the original code, if you typed '+', two items would be popped off the stack, added together, and the sum would be push back on the stack. Since there is no break statement after that, the next line of code would execute (i.e. the code in case '-'. For what it's worth, I almost never use switch statements. I use if (..) {} else if (..) {} else {} instead - it can be easier to read and compilers typically optimize it better. But I left it in the code above so you could understand the whole break thing.
3. You need to use || rather than | in your if ... + .. - .. * .... statement. The double || is the logical OR operator and is used as you would normally use the word OR in the english language (if this or this or this). The single | is a bit-wise operator that is used to do binary arithmetic operations. I'll let you look that one up.
4. int('6') does not convert the character '6' to the number 6. The computer already thinks of the character '6' as a number - 54 (that's the ascii number used to represent '6'). You need to subtract 48 from the 54 to give you the number you likely want to perform arithmetic with. 48 just happens to be the ascii number used to represent '0', so it's looks nicer to code '6' - '0' rather that '6' - 48. So I replaced int(exp[i]) with exp([i] - '0').

I also added a little error-checking code using the isdigit macro, which takes a character as an argument and returns non-zero if the character is numeric or zero if it is not. That way if you make a typo (6t+ instead of 65+), you won't get wacky results. Actually, you'll still get unexpected results, but you'll get a warning to let you know why. (You'll need to add #include <ctype.h> to the top of your file, since that's where isdigit is defined.)

I think that's it.

0
 

Accepted Solution

by:
wkmatt42 earned 80 total points
ID: 6236953
And I meant "check your loops" on that first line - I don't think your looks are that important.
0
 

Expert Comment

by:wkmatt42
ID: 6236957
I also moved the declaration of char exp[50] into the main function, since no other function uses it. As a general rule, global variables are bad. Repeat after me: "Bad global. Bad global."
0
 

Expert Comment

by:wkmatt42
ID: 6236961
Oops - one more thing. (Is everyone tired of those notification emails yet?)

I changed the code in the case switches from:

upper = s1.pop();
lower = s1.pop();
s1.push(upper <some op> lower);

to:

s1.push(s1.pop() <some op> s1.pop());

just because I'm a lazy typist and I like to keep things short and sweet.
0
 

Author Comment

by:wowshekar
ID: 6236974
dear wkmatt42!
that was incredible..awsome..two thumbs up!!! i asked so many people about my code but none could find bugs.. i think you are real expert..
thanks a lot..
0
 

Expert Comment

by:wkmatt42
ID: 6238309
Thanks. Me too.
0

Featured Post

On Demand Webinar - Networking for the Cloud Era

This webinar discusses:
-Common barriers companies experience when moving to the cloud
-How SD-WAN changes the way we look at networks
-Best practices customers should employ moving forward with cloud migration
-What happens behind the scenes of SteelConnect’s one-click button

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

In days of old, returning something by value from a function in C++ was necessarily avoided because it would, invariably, involve one or even two copies of the object being created and potentially costly calls to a copy-constructor and destructor. A…
This article will show you some of the more useful Standard Template Library (STL) algorithms through the use of working examples.  You will learn about how these algorithms fit into the STL architecture, how they work with STL containers, and why t…
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.

719 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question