ISourceCode

Make the frequent cases fast and the rare case correct

Converting an Infix Expression to Postfix expression using a stack ADT (Linked List)

Converting and infix expression to postfix or Reverse Polish notation.

I have used a stack ADT developed using a linked list. I prefer linked lists as memory can be allocated dynamically.

One famous algorithm is the Shunting yard algorithm. The approach used in this article is the usual input and stack precedence comparison algorithm.

Precedence values of stack and input characters

Symbols Input Precedence Stack precedence

+,-          1                 2
*,/          3                 4
$,^          6                 5
operands     7                 8
(            9                 0
)            0                 -
#            -                 -1

Please make sure to give input within brackets (). Will debug this soon.

//@AUTHOR : CHINMAY LOKESH
import java.io.*;
class Node
{
	public char item;
	public Node next;
	public Node(char val)
	{
		item = val;
	}
	public void displayNode()
	{
		System.out.println(item);
	}
}
class LinkedList
{
	private Node first;
	public LinkedList()
	{
		first = null;
	}
	public boolean isEmpty()
	{
		return (first==null);
	}
	public void insert(char val)//inserts at beginning of list
	{
		Node newNode = new Node(val);
		newNode.next = first;
		first = newNode;
	}
	public Node delete()//deletes at beginning of list
	{
		Node temp = first;
		first = first.next;
		return temp;
	}
	public void display()
	{
		System.out.println("Elements from top to bottom");
		Node current = first;
		while(current != null)
		{
			current.displayNode();
			current = current.next; 
		}
		System.out.println("");
	}
	public Node displayFirst()
	{
		return first;
	}	
	
}
class Stack
{
	private LinkedList listObj;
	public Stack()	
	{	
		listObj = new LinkedList();
	}
	public void push(char ch)
	{
		listObj.insert(ch);
	}
	public Node pop()
	{
		return listObj.delete();
	}
	public boolean isEmpty()
	{
		return listObj.isEmpty();
	}
	public void displayStack()
	{
		System.out.print("Stack : ");
		listObj.display();
	}
	public Node Peek()
	{
		return listObj.displayFirst();
	}
}
class InfPos
{
	private Stack stackADT;
	private String input;
	private String output = "";
	public InfPos(String in)
	{
		input = in;
		stackADT = new Stack();
	}
	public String convert()
	{
		stackADT.push('#');
		System.out.print(stackADT.Peek().item);
		
		for(int j=0; j inpPrec(ch))
			{
				output = output + stackADT.pop().item;
				symbol = stackADT.Peek().item;
			}
			if(stackPrec(symbol) != inpPrec(ch))
				stackADT.push(ch);
			else
				stackADT.pop();
		}
				
	 
		while( !stackADT.isEmpty() )
		{
			if(stackADT.pop().item != '#')
				output = output + stackADT.pop().item; 
		}
		return output;
	}
	public int stackPrec(char ch)
	{
		switch(ch)
		{	
			case '+':
			case '-': return 2;
			case '*': 
			case '/': return 4;
			case '^': 
			case '$': return 5;
			case '(': return 0;
			case '#': return -1;
			default: return 8;
		}
	}
	public int inpPrec(char ch)
	{
		switch(ch)
		{
			case '+':
			case '-': return 1;
			case '*': 
			case '/': return 3;
			case '^': 
			case '$': return 6;
			case '(': return 9;
			case ')': return 0;
			default: return 7;
		}
	}

} 
class InfixToPostfixBlog
{
	public static void main(String[] args) throws IOException
	{
		String input, output;
		while(true)
		{
			System.out.print("Enter infix: ");
			System.out.flush();
			InputStreamReader isr = new InputStreamReader(System.in);
			BufferedReader br = new BufferedReader(isr);
			input = br.readLine();
			if( input.equals("") )
				break;
			InfPos theTrans = new InfPos(input);
			output = theTrans.convert();
			System.out.println("Postfix: " + output + '\n');
		} 
	} 

} 

OUTPUT( with trace):
labuser@ubuntu:~/intopos$ java InfixToPostfixBlog
Enter infix: (a+(b-c)*d)
#Stack : Elements from top to bottom
#

Stack : Elements from top to bottom
(
#

Stack : Elements from top to bottom
a
(
#

Stack : Elements from top to bottom
+
(
#

Stack : Elements from top to bottom
(
+
(
#

Stack : Elements from top to bottom
b
(
+
(
#

Stack : Elements from top to bottom
-
(
+
(
#

Stack : Elements from top to bottom
c
-
(
+
(
#

Stack : Elements from top to bottom
+
(
#

Stack : Elements from top to bottom
*
+
(
#

Stack : Elements from top to bottom
d
*
+
(
#

Postfix:abc-d*+

Enter infix: ((a+(b-c)*d)^e+f)
#Stack : Elements from top to bottom
#

Stack : Elements from top to bottom
(
#

Stack : Elements from top to bottom
(
(
#

Stack : Elements from top to bottom
a
(
(
#

Stack : Elements from top to bottom
+
(
(
#

Stack : Elements from top to bottom
(
+
(
(
#

Stack : Elements from top to bottom
b
(
+
(
(
#

Stack : Elements from top to bottom
-
(
+
(
(
#

Stack : Elements from top to bottom
c
-
(
+
(
(
#

Stack : Elements from top to bottom
+
(
(
#

Stack : Elements from top to bottom
*
+
(
(
#

Stack : Elements from top to bottom
d
*
+
(
(
#

Stack : Elements from top to bottom
(
#

Stack : Elements from top to bottom
^
(
#

Stack : Elements from top to bottom
e
^
(
#

Stack : Elements from top to bottom
+
(
#

Stack : Elements from top to bottom
f
+
(
#

Postfix:abc-d*+e^f+

About these ads

One response to “Converting an Infix Expression to Postfix expression using a stack ADT (Linked List)

  1. Gokul June 17, 2012 at 9:27 pm

    Hello:

    While I am reviewing the above logic, I noticed that in the following for loop some conditions are missed. Not sure if there is any issue while you upload it in this site. If possible, could you please send me the latest/updated code for the same.

    for(int j=0; j inpPrec(ch))

    Thanks in advance.

    Thanks
    Gokul

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: