infixpostfix.java

many simple java programs like classic algorithems to do search and few data structure implimentatio

import java.io.*;
import java.util.Scanner;

class node 
{
  public char data;
  public node link;
}
 
class stack
{
  node top;
   
  public stack()
  {
    top=null;
  }
 
  public void push(char ch)
  {
    
    
     node temp=new node();
     temp.data=ch;
     temp.link=top;
     top=temp;
  }

  public char pop()
  {
    if(top!=null)
    {
      char ch=top.data;
      top=top.link;
      return ch;
    }
    else
      return '!';
  }
}

public class infixpostfix
{

  public static int priority(char ch)
  {
    switch(ch)
    {
      case '^':
         return 5;
      case '*':
      case '/':
         return 4;
      case '+':
      case '-':
         return 3;
      case '(':
         return 2;
      case ')':
         return 1;
      default:
         return 0;
    }
  }
  
  
  public static void main(String args[])
  {
    
    String postfix=new String("");
    stack stk=new stack();
    Scanner s=new Scanner(System.in);
    System.out.print("Enter infix expression:");
    String exp=s.next();
    exp=exp+')';
    stk.push('(');
    for(int i=0;i<exp.length();i++)
    {
      System.out.println("Scan symbol : "+exp.charAt(i));  
      switch(exp.charAt(i))
      {
        case '^':
        case '*':
        case '/':
        case '+':
        case '-':
            
           char stktop=stk.pop();
           if(priority(stktop)>priority(exp.charAt(i)))
           {
             System.out.println("   priority of stack top:"+stktop+">"+exp.charAt(i)+"so adding "+stktop+" to postfix expression"); 
             postfix+=stktop;
             stk.push(exp.charAt(i));
           }
           else
           {
             System.out.println("   Priority of Stacktop, "+stktop+" & "+exp.charAt(i)+"< or =,so pushing "+exp.charAt(i)+" to stack");

             stk.push(stktop);
             stk.push(exp.charAt(i));
           }
           break;
        case '(':
           System.out.println("   '(' encountered, so pusing it to stack");   
           stk.push('(');
           break;
        case ')':
           System.out.println("   ')' encountered, so popping till '(' is reached in stack");  
           char ch=stk.pop();
           while(ch!='(')
           {
             postfix+=ch;
             ch=stk.pop();
           }
           break;
        default:
           System.out.println("   An operand, add it to postfix expression!");  
           postfix=postfix+exp.charAt(i);
      }
      System.out.println("\n");
     }
    System.out.println("Postfix expression is:"+ postfix);
  }
}