class Node  {
	public Object data;
	public Node next;
	public Node () {
	   data =' ';  next = null; }
	public Node (Object val) {
	   data = val;  next = null; }
}

public class LinkStack {
	private Node top;
	/*  Creates a new instance of LinkStack */
	public LinkStack() {
		top = null; }
	public boolean empty(){
		return top == null; }
   
	
	public boolean full(){
		return false;
	}
public void push(Object e){
		Node tmp = new Node(e);
		tmp.next = top;
		top = tmp;
	}
public Object pop(){

	Object e =  top.data;
	top = top.next;
	return e;
}
public Object peek(){

	Object e =  top.data;
   
	return e;
}


public void matching(String x)
{	
	LinkStack S=new LinkStack();

	for(int i=0;i<x.length();i++)
	{
		char c=x.charAt(i);
		if(c=='(')
			S.push(c);
		else
		{
			if(c==')')
			if(S.empty())
				System.out.println("NOT MATCHING !!!");
			else
				S.pop();
		}
	}
	if(!S.empty())
		System.out.println("NOT MATCHING !!!");
	else
		System.out.println("MATCHING !!!");
}
public void Evaluation(String x)
{
	
	LinkStack S=new LinkStack();
	for(int i=0;i<x.length();i++)
	{
		char c=x.charAt(i);
		String s="0"+c;
		
		if(c=='+')
		{
			int z=Integer.parseInt((String)S.pop())+Integer.parseInt((String)S.pop());
			S.push(Integer.toString(z));
		}
		else if(c=='*')
		{
			int z=Integer.parseInt((String)S.pop())*Integer.parseInt((String)S.pop());
			S.push(Integer.toString(z));
			
		}
		else if(c=='/')
		{	int u=Integer.parseInt((String)S.pop());
			
			int z=Integer.parseInt((String)S.pop())/u;
			S.push(Integer.toString(z));
			
		}
		else if(c=='-')
		{	int u=Integer.parseInt((String)S.pop());
			int z=Integer.parseInt((String)S.pop())-u;
			S.push(Integer.toString(z));
		}
		else
		S.push(s);
	}
	System.out.println("THE POSTFIX = "+x);
	System.out.println("THE RESULT = "+S.pop());
}
public void postfix(String x)
{
	String output="";
	LinkStack S=new LinkStack();
	for(int i=0;i<x.length();i++)
	{
		char c=x.charAt(i);
		
		if(c==('+')||c==('*')||c==('-')||c==('/'))
			{while(!S.empty() && priority(S.peek())>= priority(c))
				output+=S.pop();
			S.push(c);
			}
		else if(c=='(')
		{
			S.push(c);
		}
		else if(c==')')
		{
			while(!S.peek().equals('('))
					output+=S.pop();
			S.pop();
		}
		else
			output+=c;
	}
	while(!S.empty())
		output+=S.pop();
	System.out.println("THE INFIX = "+x);
	System.out.println("THE POSTFIX = "+output);
}
public int priority(Object x)
{
	if(x.equals('+')||x.equals('-'))
		return 1;
	else if(x.equals('*')||x.equals('/'))
		return 2;
	else
		return 0;
}

public static void main(String args[])
{
	
	
	LinkStack s=new LinkStack();
	s.postfix("A*B+((C+D)*(F-G))");
	System.out.println("------------------------------------------");
	s.matching("A*B+((C+D)*(F-G))");
	System.out.println("------------------------------------------");
	s.Evaluation("23*23+32-*+");
	System.out.println("------------------------------------------");
}
}

skyhawk133, on 2 Dec, 2007 - 11:31 AM, said:

	public static boolean matching=true;
	public static void main(String[] args)//method that tests matching  
	{
		LinkStack s=new LinkStack();
			   s.matching("A*B+C+(D*F-G)");
		if(matching==true)
			System.out.println("MATCHING!");
		else
			System.out.println("NOT MATCHING!");
	   
	}//end main method

public void matching(String x)
	{	
		Stack S=new Stack();

		for(int i=0;i<x.length();i++)
		{
			char c=x.charAt(i);
			if(c=='(')
				S.push(c);
			else
			{
				if(c==')')
				if(S.isempty())
					matching=false;
				else
					S.pop();
			}
		}
		if(!S.isempty())
			matching=false;
	}