Solved

evaluating a postfix expression

Posted on 2001-06-28
11
601 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
  • 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
Networking for the Cloud Era

Join Microsoft and Riverbed for a discussion and demonstration of enhancements to SteelConnect:
-One-click orchestration and cloud connectivity in Azure environments
-Tight integration of SD-WAN and WAN optimization capabilities
-Scalability and resiliency equal to a data center

 

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 20 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

Free Tool: Port Scanner

Check which ports are open to the outside world. Helps make sure that your firewall rules are working as intended.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

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

Suggested Solutions

Introduction This article is the first in a series of articles about the C/C++ Visual Studio Express debugger.  It provides a quick start guide in using the debugger. Part 2 focuses on additional topics in breakpoints.  Lastly, Part 3 focuses on th…
Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…
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.

809 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