Solved

evaluating a postfix expression

Posted on 2001-06-28
11
602 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
Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 

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

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
C++ standard library based binary archive format 6 108
c++ syntax question 9 57
Path to  STL Map header file 1 74
max float value 3 59
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…
Container Orchestration platforms empower organizations to scale their apps at an exceptional rate. This is the reason numerous innovation-driven companies are moving apps to an appropriated datacenter wide platform that empowers them to scale at a …
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.

685 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