Solved

infix to postfix in c++

Posted on 2001-07-15
12
3,807 Views
Last Modified: 2012-06-27
dear expert!

this is the code which i wrote to convert an infix to postfix. its compiling.. but the output is weird.
say if i gave 4+3 as my infix expression its giving 43 and not showing '+'. i dont know why? please look at my program,compile it..just copy and paste.. and debug my program..
here is my program:

#include <iostream.h>
#include <ctype.h>

const int max =50;
char postfix[50];
char exp[50];
int upper;
int lower;
static int j=0;  //j is declared as static


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

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

     }

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

     int isoperand(char symb)//checks whether the character is operator of operand
     {
     if(symb=='+' || symb=='*'||symb=='(' || symb==')')
          return 0;
     else
          return 1;
     }

     int prcd(char symb)//checks the precedence of the operators
     {
          if((st[top]=='+')&& (symb=='*'))
               return 0;
          else if(st[top]=='(')
               return 0;
          else if((st[top]!=')')&&(symb=='('))
               return 0;
          else
               return 1;
     }


};

void main()
{
   stack s1;
   int i=0;
   int k=0;
   
   char symb;
   
   char exp[50];
   cout<<"Enter an expression\n";
   cin>>exp;

   while (i < 50  &&  exp[i] != '\n')
   {
          symb=exp[i];
          if(s1.isoperand(symb))
          {
               postfix[j++]=symb;//j is declared as static
          }
          else
          {
               while(!s1.isempty() && s1.prcd(symb))
               {
                    postfix[j++]=s1.pop();

               }
               s1.push(symb);
          }
          ++i;
   }
   
//pops out all the operators and adds it to the postfix string
   while(!s1.isempty())
   {
        postfix[j++]=s1.pop();
   }

   //print out the postfix expression

   while( k<50 && postfix[k]!='\0')// i think here  something is wrong
   {
        cout<<postfix[k];
        k++;
   }


}//end of main

0
Comment
Question by:wowshekar
  • 3
  • 2
  • 2
  • +5
12 Comments
 
LVL 6

Accepted Solution

by:
kotan earned 20 total points
Comment Utility
For the line,
while (i < 50  &&  exp[i] != '\n')

you should compare the exp[i] with '\0'.

There is a one error in the pop(),
the comparison should be top <= 0.



0
 
LVL 30

Expert Comment

by:Axter
Comment Utility
>>There is a one error in the pop(),
>>the comparison should be top <= 0.

That's not an error.
The only problem is in the exp[i] comparison.
Should be the following:
while (i < 50  &&  exp[i] != 0)


Also you should have a return value in the pop() function:
Example:
int pop()
{
     if(top<0)
     {
          cout<<"stack underflow";
     }
     else
     {
     return st[--top];
     }
      return 0;  //You need to have a return here
}
0
 
LVL 1

Expert Comment

by:altaf_techie
Comment Utility
There is an error in the code in the main function in the while statement.
Instead of

while (i < 50  &&  exp[i] != '\n')

it should be

while (i < 50  &&  exp[i] != '\0')
                             -----  
i.e. the character to indicate the end of string
0
 
LVL 30

Expert Comment

by:Axter
Comment Utility
Hi (altaf_techie), welcome to EE.
All of the experts here, for the most part have learn from other experts as to the proper etiquette for posting answer.

Your answer has been proposed by both previous experts.

It's agaisnt EE policy to use previously posted comments in a proposed answer.

Before posting an answer, you should check to see if an expert has just posted the same answer as a comment.

There are many experts who never post answers as answer.  Instead, they post their answers as comments.
If you read the following link, you'll see why this is the preferred method for many of our valued experts, including myself.

http://www.experts-exchange.com/jsp/cmtyQuestAnswer.jsp


Hi (wowshekar):
Feel free to click the [Reject Answer] button near (Answer-poster's) response, even if it seems like a good answer.
Doing so will increase your chance of obtaining additional input from other experts.  Later, you can click the [Select Comment as Answer] button on any response.

Please award this answer to the appropriate expert.
0
 
LVL 1

Expert Comment

by:altaf_techie
Comment Utility
well my dear experts i m sorry for repeating the answer though i had no intention to copy anybody's answer.. i had myself found the answer by debugging the code. Yes it was my mistake that i didnt care to read other experts comments before doing so.. In future i would see that it doesnt happen again...
0
 

Author Comment

by:wowshekar
Comment Utility
dear axter!

your's code worked properly. but i am not getting the results as i desired..for ex:
if i gave: 5+6*3 as input..i should get 563*+..instead its giving as 56+6*.. i tried many examples but giving error.. so please check my program once again..if possible..please..
0
Highfive + Dolby Voice = No More Audio Complaints!

Poor audio quality is one of the top reasons people don’t use video conferencing. Get the crispest, clearest audio powered by Dolby Voice in every meeting. Highfive and Dolby Voice deliver the best video conferencing and audio experience for every meeting and every room.

 
LVL 2

Expert Comment

by:jonnin
Comment Utility
this is the correct answer, to be parsed by the easy rule
"if operand, push, if operator, pop twice, do the operation, push result" ...


5 push
6 push
3 push

* ->
pop 6, pop 3, multiply, push the 18

+ ->
pop the 18, pop the 5, add, push
end of input, pop once for result...


from a long time hp calculator user =)

0
 
LVL 2

Expert Comment

by:jonnin
Comment Utility
arrg, read that backwards, that post was not too helpful.
I read the good and bad results and mentally reversed them, sorry...
0
 
LVL 30

Expert Comment

by:Axter
Comment Utility
>>but i am not getting the results as i desired..for ex:
I'm sorry but I have a full schedule this week.
Perhaps one of the other experts can help you out.  Feel free to give them the points.
0
 
LVL 5

Expert Comment

by:BlackDiamond
Comment Utility
wowshekar,

There are 2 more errors in this code that I found.  The first is an off by one error in your prcd method:

   int prcd(char symb)//checks the precedence of the operators
   {
      //top was off by one
      if((st[top-1]=='+') && (symb=='*'))
         return 0;
      else if(st[top-1]=='(')
         return 0;
      else if((st[top-1]!=')')&&(symb=='('))
         return 0;
      else
         return 1;
   }




And the second is that you need to delete the parens when you pop:


---------------------

   while(!s1.isempty() && s1.prcd(symb)) {
      postfix[j++]=s1.pop();
      // need to delete ()'s
      if (postfix[j-1] == '(' || postfix[j-1] == ')'){
         postfix[--j] = 0;
      }
   }

--------------------
   while(!s1.isempty()) {
      postfix[j++]=s1.pop();
      // need to delete ()'s
      if (postfix[j-1] == '(' || postfix[j-1] == ')'){
         postfix[--j] = 0;
      }
   }
---------------------

Hope this helps...

BD
0
 
LVL 11

Expert Comment

by:griessh
Comment Utility
I think you forgot this question. I will ask Community Support to close it unless you finalize it within 7 days. Unless there is objection or further activity,  I will suggest to accept "kotan,Axter,BlackDiamond" comment(s) as an answer.

If you think your question was not answered at all, you can post a request in Community support (please include this link) to refund your points.
The link to the Community Support area is: http://www.experts-exchange.com/jsp/qList.jsp?ta=commspt

PLEASE DO NOT ACCEPT THIS COMMENT AS AN ANSWER!
======
Werner
0
 
LVL 1

Expert Comment

by:Computer101
Comment Utility
Comment from kotan accepted as answer.
Axter and BlackDiamond, look for your questions in this topic area.

Thank you
Computer101
Community Support Moderator
0

Featured Post

Highfive Gives IT Their Time Back

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

Join & Write a Comment

Often, when implementing a feature, you won't know how certain events should be handled at the point where they occur and you'd rather defer to the user of your function or class. For example, a XML parser will extract a tag from the source code, wh…
Templates For Beginners Or How To Encourage The Compiler To Work For You Introduction This tutorial is targeted at the reader who is, perhaps, familiar with the basics of C++ but would prefer a little slower introduction to the more ad…
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 learn how to clear a vector as well as how to detect empty vectors in C++.

762 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

Need Help in Real-Time?

Connect with top rated Experts

15 Experts available now in Live!

Get 1:1 Help Now