Solved

infix to postfix converter

Posted on 2000-03-20
9
452 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
 

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
Better Security Awareness With Threat Intelligence

See how one of the leading financial services organizations uses Recorded Future as part of a holistic threat intelligence program to promote security awareness and proactively and efficiently identify threats.

 
LVL 10

Expert Comment

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

Accepted Solution

by:
RONSLOW earned 100 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

Find Ransomware Secrets With All-Source Analysis

Ransomware has become a major concern for organizations; its prevalence has grown due to past successes achieved by threat actors. While each ransomware variant is different, we’ve seen some common tactics and trends used among the authors of the malware.

Join & Write a Comment

This article shows you how to optimize memory allocations in C++ using placement new. Applicable especially to usecases dealing with creation of large number of objects. A brief on problem: Lets take example problem for simplicity: - I have a G…
Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the b…
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.

708 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