Go Premium for a chance to win a PS4. Enter to Win

x
?
Solved

infix to postfix converter

Posted on 2000-03-20
9
Medium Priority
?
468 Views
Last Modified: 2010-04-10
I've created a class to push pop test empty or full to a stack. How do I create a main to convert infix to postfix notation. I'm not sure how to implement the stack in doing this. When I use a cin.get(ch) to input, the prog loops with c's filling screen.(I entered c+d as a test. While(ch !='\n')
0
Comment
Question by:dolphin203
9 Comments
 
LVL 7

Expert Comment

by:KangaRoo
ID: 2639221
Can you paste (some of) the code?
iostreams can act 'weird' if formatted (like istream::get) is mixed with formatted (operator>>) I/O.
0
 
LVL 3

Expert Comment

by:MDarling
ID: 2639610
sounds like you need a

cin.get(ch);

inside your loop.

but like KangaRoo says, we need to see a little code.

regards,
Mike.
0
 
LVL 10

Expert Comment

by:RONSLOW
ID: 2639972
infix to postifx is probably best done without an explicit stack .. use function return stack instead
eg. somehting like this...

static char ch;
void NextChar() {
  cin.get(ch);
}
void DoAddSub();
void DoMulDiv();
void DoSimple();
void DoExpr();
void DoAddSub() {
  DoMulDiv();
  for(;;) {
    char op = ch;
    if (ch != '+' && ch != '-') break;
    NextChar();
    DoMulDiv();
    cout << op;
  }
}
void DoMulDiv() {
  DoSimple();
  for(;;) {
    char op = ch;
    if (ch != '*' && ch != '/') break;
    NextChar();
    DoSimple();
    cout << op;
  }
}
void DoSimple() {
  if (ch == '(') {
    NextChar();
    DoAddSub();
    if (ch != ')') {
      // error
       return;
    }
    NextChar();
  } else { // assume it is a letter
    cout<<ch;
    NextChar();
  }
}
void DoExpre() {
  NextChar();
  DoAddSub();
}


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:dolphin203
ID: 2642912
Ron, Here's class and main() I'm working on. I'll try to adapt your answer to it. I didn't want to reject your answer, but that was the only way I know to respond back to you.//Dave McNeil
//Stack.h  Stack class to facilitate infix to postfix thru entering expression. Push, Pop, Empty, Full, Top Methods employed
//**********************************************************************

#include <iostream.h>
#include <ctype.h>                 // isalpha
const int MAX_STKSIZE = 10;        // set maximum stack size
int priority(char e);              // function to determine operator priority
class stack
{
       protected:
              int size;                    // current size(TOP)tack
              char datum[MAX_STKSIZE];     // initialize stack array to 10

       public:
              stack();               // constructor
              ~stack();              // destructor
              void push(char i);     // push data on to stack prototype
              int pop();             // pop data off the stack prototype
              int top();             // return data item at top of stack prototype
              bool empty();          // test empty stack prototype
              bool full();           // test full stack prototype
              void print();                   // print contents of stack
              int getsize();
};

stack::stack()
{
       size =0;                    // initialize stack data to zero
}

stack::~stack()
{
       if(size >0)
              cout<<"The stack was not empty during this destruction.\n";
       size = 0;                // size set to zero clearing stack memory
}

int stack::getsize()
{
      return size;
}

void stack::push(char i)
{
       if(full() ==true)
       {
              cout<<"Stack is full\n";  // test for a full stack before inserting data
       }
    else
       {
              datum[size] =i;           // put data on to the stack and incremeny size    
              size++;
       }
}

int stack::pop()
{
       if(empty() ==true)
       {
              cout<<"Stack is empty\n";
              return true;
       }
       else
       {
              size--;                  // remove top data by setting size of stack -1
              return datum[size];      // return next value
       }
}

int stack::top()
{
       if(empty() ==true)
       {
              cout<<"Stack is Empty\n";
              return 0;
       }
       else
       {
              return datum[size-1];   // return value at top of stack
       }
}

void stack::print()
{
       int i;              // local var to set for loop
       if(empty() ==true)
               cout<<"Stack is Empty\n";
       else
       {
              for(i = size-1; i >=0; i--)    // count down from top
                        cout<<"\t|  " <<datum[i] <<"\t|" <<endl;
              cout<<"\t|_______|" <<endl;    // Separate stack elements
       }
}

bool stack::empty()
{
       if(size==0)
              return true;
       else
              return false;
}

bool stack::full()
{
       if(size ==MAX_STKSIZE)
              return true;
       else
              return false;
}

void main()
{
       char ex;               // expression
       char tos;              // top of stack
       int tosp;              // top of stack priority
       stack action;
       cout<<"Enter infix expression\n";
       cin.get(ex);
       while(ex != '\n')
       {
            if(isalpha(ex))      // print alpha A-Z, a-z
                  cout<<ex;
       else
            switch(ex)
            {
            case '/':
                  action.push(ex);        // push div to stack
                  break;
            case '*':
                  if(action.top() =='$')  // char on top is exponential higher precedence
                  {
                        cout<<action.top(); // print $ exponential
                        action.pop();       // pop $ off the stack
                  }
                  else
                        action.push(ex);    // push * to stack
                  break;
            case '+':
                  if(action.top() =='$' || action.top() =='/' || action.top() =='*')
                  {
                        cout<<action.top();  // print higher precedence operator
                        action.pop();        // pop higher precedence operator off stack
                        action.push(ex);       // push + to stack
                  }
                  else
                        action.push(ex);     // put + on the stack
                  break;
          case '-':
                  if(action.top() =='$' || action.top() =='/' || action.top() =='*')
                  {
                        cout<<action.top();  // print operator at top
                        action.pop();        // pop operator
                        action.push(ex);     // push - to stack
                  }
                  else
                        action.push(ex);     // put - on the stack
                  break;
            case '(':
                  action.push(ex);         // put ( on the stack
                  break;
            case ')':
                  while(action.top() !='(')
                  {
                        cout<< action.top();  // pop & print till =(
                        action.pop();
                  }
                  action.pop();             // pop the (b
                  break;

            default:
                  if(action.getsize() ==1)
                  {
                  cout<<action.top() <<endl;
                  action.pop();
                  break;
                  }
                  else
                        break;
             }
             cin.get(ex);
       }
}
//***************************************************
// priority function
//***************************************************
int priority(char e)
{
      if(e =='-' || e =='+')
            return 1;
      else if(e =='*' || e =='/')
            return 2;
      else if(e =='$')
            return 3;
      else if(e =='(')
            return 4;
      return 0;
}





0
 
LVL 10

Expert Comment

by:RONSLOW
ID: 2642967
You can respond by just adding a comment.
0
 
LVL 10

Accepted Solution

by:
RONSLOW earned 400 total points
ID: 2643019
First a little note: the usual convention for member function names is that they are either verb (ie do something) or nouns (get a property).  You havea method called 'empty' in your stack class.  Anyone reading code using your class will think that stack.empty() means "empty the stack".  I suggest you change the name to isempty (and isfull) to make code more readable and understandable to others.

ignoring parentheses, the code is fairly simple ... just do this for each character you read.

if (priority(ch) == 0) {
  // not an operator so just output
  cout << ch;
} else {
  // pop and output any lower priority
  // items from the stack
  while (! stack.empty() && priority(stack.top()) < priority(ch)) {
    cout << stack.pop();
  }
  // then push the new one
  stack.push(ch);
}

parentheses make it trickier

if (priority(ch) == 0) {
  // not an operator so just output
  cout << ch;
} else if (ch == ')') {
  // pop and output down to the
  // matching open parenthese
  while (! stack.empty() && stack.top() != '(') {
    cout << stack.pop();
  }
  // and not pop the open parenthese
  stack.pop();
} else {
  // pop and output any lower priority
  // items from the stack but don't
  // go past the latest open
  // parenthese
  while (! stack.empty() && stack.top() != '(' && priority(stack.top()) < priority(ch)) {
    cout << stack.pop();
  }
  // then push the new one
  stack.push(ch);
}

This is the sort of thing you need .. and this way the only special characters that need to be coded for in this loop are the parentheses .. the rest are determined by the priority function.

PLEASE NOTE: I've just typed this in directly here .. probably full of bugs !!


0
 

Author Comment

by:dolphin203
ID: 2643123
Thanks for the advice Roger. I'm sure I can get the class working with what you have provided. Therefore, I've given you an "A" and my thanks. A last couple questions! How do you handle the last poping the last value/operators in the following expression;
(A+B)*(C+D)+E$ I believe the translation is:
AB+CD+E+*$ How is +*$ handled?
Dave
0
 
LVL 10

Expert Comment

by:RONSLOW
ID: 2643141
becaues $ is higher priorty than anything on the stack (assuming all your parentheses are matchend), then it will pop off everything else.

At end of loop, you'll probably need to pop and print anything left on the stack .. all things being ok, it should only be the $ symbol.  If there is more than that on the stack, then there was probably a syntax error in the input expression.
0
 

Author Comment

by:dolphin203
ID: 2643192
Thanks a lot Roger, I'll give it a try. I'm trying to learn advanced C++ on my own and find very few real life examples to point me in the right direction. The next project I plan to tackle is a "linked list." Can you suggest any reading material? Pointers have always been difficult for me.
0

Featured Post

Keep up with what's happening at Experts Exchange!

Sign up to receive Decoded, a new monthly digest with product updates, feature release info, continuing education opportunities, and more.

Question has a verified solution.

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

When writing generic code, using template meta-programming techniques, it is sometimes useful to know if a type is convertible to another type. A good example of when this might be is if you are writing diagnostic instrumentation for code to generat…
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 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 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.
Suggested Courses

916 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