Friday, 12 August 2016

Infix to Postfix conversion



/*
Write  a Program to convert infix to postfix string

Input String can have operators -> '+','-','%','/','*'
Precedence for + and - operator is same
Precedence for %,/,* is same but higher than + and - opertor

Example

Input string                 Postfix String

a+b                               ab+
a+b+c+(d*e+f)             ab+c+de*f++

 */
package postfix_conversion;

import java.util.Scanner;

/**
 *
 * @author shashank
 */

class stack
{
 char arr[];
 int top =-1;

 public stack(String s)
 {
     arr = new char[s.length()];
 }

public void push(char c)
{
    arr[++top] = c;
}

public char pop()
{
    return arr[top--];
}

public boolean isempty()
{
    return (top==-1)?true:false;
}

public char peek()
{
    return arr[top];
}
}

public class Postfix_conversion {

 
    public static int check_prec(char c)
    {
        if(c=='+'|| c=='-')
            return 1;
        else if(c=='*'||c=='/'||c=='%')
            return 2;
        return 0;
    }

    public static void main(String[] args) {
        // TODO code application logic here
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter the infix string");
        String s = sc.next();
        StringBuilder sb = new StringBuilder();
        stack st = new stack(s);
        char symbol;
        for(int i=0;i<s.length();i++)
        {
            symbol = s.charAt(i);
         
            if(Character.isLetter(symbol))
            sb.append(symbol);
            else if(symbol=='(')
             st.push(symbol);
            else if(symbol==')')
            {
                while(st.peek()!='(')
                {
                    sb.append(st.pop());
                }
            st.pop(); // to remove '('
            }
            else
            {
                while(!st.isempty() && !(st.peek()=='(') && check_prec(symbol) <= check_prec(st.peek()))
                {
                    sb.append(st.pop());
                }
             
                st.push(symbol);
            }
        }
        while(!st.isempty())
        {
            sb.append(st.pop());
        }
     
        System.out.println("Postfix String is :->" + sb.toString());
    }
 
}

No comments:

Post a Comment