I searched for this topic first, because it is pretty popular, but I didn't find much to help. What I was instructed to do was convert a prefix expression to a postfix expression. I have to use a stack and a queue, which is different than many other threads about this topic. Another thing that is different is that my expressions are purely variables(ie +*A B / C D). I made a little progress on my own, and I don't want everyone to solve it for me, but help would be extremely appreciated.
I am reading the expressions from a file. I also put the postfix operands in the queue, and the operators in the stack. I get stuck when it is time to use the information. This is what I planned to do next:
if an operator is followed by 2 items that are operands, pop them and then pop the operator, else push into stack.
However, I have no clue as to do that; even if I am going in the correct direction.

If you stopped by, thanks, if you helped, thanks, if not, thanks anyway.


What I have so far:

import java.io.*;
import java.util.*;
public class lab8
{

    //Nodes
    static String strToken;
    static boolean expressionOk;

    public static void main(String[] args)
    		//throws FileNotFoundException
    {
		//declare the operators stack
		StackClass<String> postfixStack =
                            new StackClass<String>(100);
		
		//declare the expression queue
		QueueClass<String> postfixQueue =
							new QueueClass<String>(100);
		//Try for error handling
		 try
	        {
			 //File operations
	            Scanner inputStream = new
	                      Scanner(new FileReader("c:\\Prefix.txt"));
	            PrintWriter outfile = new
	                      PrintWriter("c:\\Postfix.txt");
	           
	         //While loop for file operations    	
	            while (inputStream.hasNext())
	            {
	                postfixStack.initializeStack();
	                expressionOk = true;            
	            }//end while
	            outfile.close();
	        }
		 //Catch for error handling
	        catch (FileNotFoundException fnfe)   
	        {
	            System.out.println(fnfe.toString());
	        }
    }
    public void evaluateExpression() throws FileNotFoundException
    {
    	
    	//declare the operators stack
		StackClass<String> postfixStack =
                            new StackClass<String>(100);
		
		//declare the expression queue
		QueueClass<String> postfixQueue =
							new QueueClass<String>(100);
		
		
		Scanner inFile = new Scanner(new FileReader("c:\\Prefix.txt"));
		while (inFile.hasNext())
		{
		String op;
    	op = inFile.next(); 
    	
    	//Switch to put in either stack or queue
    		//Because operator, goes in stack, else queue
    		
    		switch(op.charAt(0))
    		{
    		case '+':
    				postfixStack.push(op);
    				break;
    			
    		case '-':
    				postfixStack.push(op);
    				break;
    			
    		case '*':
    				postfixStack.push(op);	
    				break;
    			
    		case '/':
    				postfixStack.push(op);
    				break;
    	
    		default: 
    				postfixQueue.addQueue(op);		
    				
    		}//end switch
		}//end while
    }//end evaluateExpression
}//end project

See the algorithm for prefix to postfix conversion at
http://fahadshaon.files.wordpress.com/2008/01/prefix-to-postfix-stack-algo.pdf

It can be easily implemented as follows,

import java.io.*;
import java.util.*;
public class lab8 {
 
	
	public static String LEFT_DONE="LEFT_DONE";
    
	public static void main(String[] args)   {
		String strPrefix="";
		String strPostfix="";

		//declare the operators stack
		Stack<String> operatorStack = new Stack<String>();
 
		 try {
			//File operations
			BufferedReader br = new BufferedReader(new InputStreamReader(new DataInputStream(new FileInputStream("c:\\Prefix.txt"))));
	        PrintWriter pw = new PrintWriter("c:\\Postfix.txt");

			//read a line containing the prefix string from the file
			String strLine="";			
			while ((strLine = br.readLine()) != null)   {
			  if(strLine != null)
				  strPrefix = strLine;
				  System.out.println("Prefix expression = "+strPrefix);
			}


			//Loop through all the characters in the prefix string.
			char[] prefixExp = strPrefix.toCharArray();
			for(int i=0; i<prefixExp.length; i++){
				//ignore blank space
				if(prefixExp[i] == ' '){
					continue;
				}

				
				if(isOperator(prefixExp[i])){
					operatorStack.push(String.valueOf(prefixExp[i]));
				}
				else{
					strPostfix += String.valueOf(prefixExp[i]);

					while(!operatorStack.empty() && operatorStack.peek().equals(LEFT_DONE)){
						operatorStack.pop();

						strPostfix += operatorStack.pop();
					}
					operatorStack.push(LEFT_DONE);
				}
			}
 
			System.out.println("Postfix expression = "+strPostfix);
			//write to the file
			pw.write(strPostfix);

	        br.close();
	        pw.close();
	     }
	     catch (Exception e) {
			e.printStackTrace();
	     }
		 
    }


	private static boolean isOperator(char c){
		char[] operators = {'+','-','/','*'};
		boolean isOp = false;
		for(int i=0; i<operators.length; i++){
			if(c == operators[i]){
				isOp = true;
				break;
			}
		}
		return isOp;
	}
	
}//end project

Hi,
You may find this link helpfull

http://fahadshaon.wordpress.com/2008/01/18/prefix-to-postfix-stack-emplementation/

It is written in C but the basic algorithm for converting Prefix to Postfix is quite clear. I remember doing a very similar project at uni and i don't quite see the reason you would need a queue as well as a stack. Not unless you output after processing everything into the queue then dump the queue to screen.

basically parse the prefix input string -

WHILE !end of string

Do

IF 'char = operator'
then push onto top of stack
IF 'char && char+1 = operand'
then output both then pop stack to output
Else output char

END WHILE

If you still have no luck i will dig out my old project and check over it.

Thank you both for your help! It was very helpful, and I tried not to use the code you gave me as it was a homework assignment. I modeled my version on yours though, so it is somewhat the same. However, I have to use both stacks and queues. Incidentally, I really don't care for the problem statement anymore. In the workplace, all it would need to be workable, which it is. Flagging this thread as solved.

O.K. I have stumbled upon another problem. I couldn't use the buffer reader to iterate. I have to read from a file that has a series of the expressions.
+ * A B / C D
* A + B / C D
- * A + B / C D E
* + A B - C D
Since the buffer reader doesn't have an iterator, it can only do the first expression. I tried converting to buffer reader into a file reader, but it prints out the third in the series.
Updated Code:

import java.io.*;
      import java.util.*;
  
      public class lab8 
      {
      public static String LEFT_DONE="LEFT_DONE";
      public static void main(String[] args) 
      {
  
      String strPrefix="";
      String strPostfix="";
 
      //declare the operators stack
      Stack<String> operatorStack = new Stack<String>();
 
      //error handling try
      try 
      {
  
      //File operations
        
      Scanner inFile = new Scanner(new FileReader("c:\\Prefix.txt"));
      PrintWriter pw = new PrintWriter("c:\\Postfix.txt");
 
      //read a line containing the prefix string from the file
      String strLine="";
      
      //Set up console for prefix expressions
      System.out.println("Set of Prefix expressions: ");
      //Set up file for prefix expressions
      pw.write("Set of Prefix expressions: " + System.getProperty("line.separator"));
      
      //While loop to build the prefix expressions and print to console
      while (inFile.hasNext())
      {
      if(strLine != null)
      strPrefix = strLine;
      strLine = inFile.nextLine();
      System.out.println("Prefix expression : " + strLine);
      pw.write("Prefix expression: " + strPrefix + System.getProperty("line.separator"));
      
      }
      
      //Set up organization of the console
      System.out.println();
      System.out.println("The Converted set of Postfix expressions: ");
      //Setup the organization of output file
      pw.write("" + System.getProperty("line.separator"));
      pw.write("The Converted set of Postfix expressions: " + System.getProperty("line.separator"));
      
      
      //Loop through all the characters in the prefix string.
      char[] prefixExp = strPrefix.toCharArray();
  
      for(int i=0; i<prefixExp.length; i++)
      {
  
    	  //ignore blank space
    	  if(prefixExp[i] == ' ')
    	  {
    		  continue;
    	  }
    
    	  if(isOperator(prefixExp[i]))
    	  {
    		  operatorStack.push(String.valueOf(prefixExp[i]));
    	  }
 
    	  else
      		{
    		  strPostfix += String.valueOf(prefixExp[i]);
    		  //build the expression
    		  while(!operatorStack.empty() && operatorStack.peek().equals(LEFT_DONE))
    		  {
    			  operatorStack.pop();
    			  strPostfix += operatorStack.pop();
    		  }
    		  operatorStack.push(LEFT_DONE);
      		}//end else
 
      }//end for 
      
      //Moved these out 
      //Write the postfix expression out to screen
      System.out.println("Postfix expression : " + strPostfix);
      //write to the file
      pw.write("Postfix expression: " + strPostfix);
      //Close all
      inFile.close();
      pw.close();
		
      }
      
      catch (Exception e) 
      {
      e.printStackTrace();
      }
 
      }//end try
      
      //Boolean class to decide what to do per each operator
      private static boolean isOperator(char c)
      {
    	  char[] operators = {'+','-','/','*'};
    	  boolean isOp = false;
     
    	  for(int i=0; i<operators.length; i++)
    	  	{
    		  if(c == operators[i])
    		  {
    		  isOp = true;
    		  break;
    		  }
     	  	}
      	  return isOp;
      }//end isOperator
}//end project
      
      
      //convert buffered reader into scanner and infile

Edited 7 Years Ago by Hanyouslayer: n/a

This article has been dead for over six months. Start a new discussion instead.