Wednesday, May 9, 2012

Infix To Post Fix using Java



import java.io.*;
public class InToPost
 {
  private Stack theStack;
  private String input;
  private String output="";
  public InToPost(String in)
  {
    input=in;
    int stackSize=input.length();
    theStack=new Stack(stackSize);
  }
  public String doTrans()
  {
    for (int i=0;i<input.length();i++)
    {
      char ch=input.charAt(i);
      switch(ch)
      {
      case '+':
      case '-':
        gotOper(ch,1);
        break; //   (precedence 1)
      case '*': // it's * or /
      case '/':
        gotOper(ch,2); // go pop operators
        break; //   (precedence 2)
      case '(': // it's a left paren
        theStack.push(ch); // push it
        break;
      case ')': // it's a right paren
        gotParen(ch); // go pop operators
        break;
      default: // must be an operand
        output=output+ch; // write it to output
        break;
      }
    }
    while(!theStack.isEmpty())
    {
      output=output+theStack.pop();
    }
    return output; // return postfix
  }
  public void gotOper(char opThis,int prec1)
  {
    while (!theStack.isEmpty())
    {
      char opTop=theStack.pop();
      if(opTop=='(')
      {
        theStack.push(opTop);
        break;
      }// it's an operator
      else
      {// precedence of new op
        int prec2;
        if(opTop=='+'||opTop=='-')
          prec2=1;
        else
          prec2=2;        if (prec2<prec1) // if prec of new op less
        { //    than prec of old
          theStack.push(opTop); // save newly-popped op
          break;
        } else
          // prec of new not less
          output=output+opTop; // than prec of old
      }
    }
    theStack.push(opThis);
  }
  public void gotParen(char ch)
  {
    while(!theStack.isEmpty())
    {
      char chx=theStack.pop();
      if(chx=='(')
        break;
      else
        output=output+chx;
    }
  }
  public static void main(String[] args) throws IOException
  {
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    System.out.print("Enter the infix expression:");
    String input=br.readLine();
    String output;
    InToPost theTrans=new InToPost(input);
    output=theTrans.doTrans();
    System.out.println("Postfix expression is:"+output);
  }
}
//-----------------------------------------------------------------------
/**
 Output:-

 Enter the infix expression:a/(b+c)+d*(e-f)
 Postfix expression is:abc+/def-*+

 Enter the infix expression:a+(b/c)*d-(e*f)
 Postfix expression is:abc/d*+ef*-

 */

0 comments:

Post a Comment