I am having trouble with stacks and infix and post fix this is my error:
Reading from file "input16.txt":
Infix expression = (5)
Exception in thread "main" java.util.EmptyStackException
at ArrayStack.pop(ArrayStack.java:51)
at test.infixToPostfix(test.java:140)
at test.displayArray(test.java:87)
at test.main(test.java:53)
this is the txt file:
(5)
(1+1)
((9/3)-2)
(9-(3/2))
(1+(4-(9*(6/(5%7)))))
((1+4)-(((9*6)/5)%7))
(((1+(4-9))*6)/(5%7))

((1+(2-3))
(1+(2-3)))
(1+(A-3))
(1@1)

import java.util.Scanner;
   import java.io.File;
   import java.util.StringTokenizer;
   import java.util.InputMismatchException;
   import java.io.FileNotFoundException;


    public class test
   {
   /*******************************************************************************
   *  Outputs integers from user input external files.
   ********************************************************************************/
   
       public static void main( String[] commandlineArguments )throws NullPointerException  {
      //Error Checking For Command Line Arguments..
         if(commandlineArguments.length == 0){
            System.out.println("Please enter the file name as the 1st commandline argument.");
         } 
         else {
         //connect to file (does NOT create new file)
            for(int i=0; i<commandlineArguments.length; i++) {
               File file = new File(commandlineArguments[i]);
            
               Scanner inputFromFile = null;
            
               try {
                  inputFromFile = new Scanner(file);
               } 
                   catch (FileNotFoundException exception) {
                  //Print error message.
                  
                     System.out.print("ERROR: File not found for \"");
                     System.out.println(commandlineArguments[i]+"\"");
                  
                  
                     return;
                  }
            
               String [] myArray = new String[2000];// Create the array to hold all elements that are found in the file
            
               int count = 0;  // number of elements
            
               count = createOutput( inputFromFile, myArray ); // adds each element into array
            
               System.out.println( "Reading from file \"" + commandlineArguments[i] + "\":" );             
                       
               displayArray( myArray, count); // calls displayArray method
            
            }//end of "if" for connecting to file
         }//end of "else" for commandlineArguments
      }//end of main() method
   
       public static int createOutput( Scanner myScanner, String [] stringArray ) {
         int count = 0; // number of elements
      
         String element; //variable of each element
      
      
         while( myScanner.hasNext() )// Loops until end of file
         {
            
            element = myScanner.next();
             
          
            stringArray[ count ] = element; //stores the element into the array using count as the index
            count++; // increase 1
         }
         return count; //returns total number of elements found in the file
      }
   
   
   
       public static void displayArray( String [] stringArray, int count) {
      // For loop to step through each item in the array
      
         for( int i = 0; i < count; i++ ) {
            
                       // Print the index and the corresponding element value
            System.out.println( "Infix expression = " + stringArray[i] );
         	
            String postFixExpression = infixToPostfix(stringArray[i]);
         	
         	
            System.out.println("Postfix expression = " + postFixExpression);
         }
      }
    
      
       public static String infixToPostfix(String infix){
       
         String postfix = "";
      	      //here is the algorithm that is described in the slides 47-49
      //step 1: get parameter infix
         String stringArray = infix;
         StackInterface<String> stack 
            = new ArrayStack<String>();
      
      
                     //step 2: loop through String infix
         for (int i = 0; i < infix.length(); i++)
         {				           
            char oneElement = infix.charAt(i);
            if (oneElement == '(')
               stack.push(infix);
            if (oneElement == '0' || oneElement == '1' || oneElement == '2'|| oneElement == '3' || oneElement == '4'|| oneElement == '5'|| oneElement == '6'||oneElement == '7'
            ||oneElement == '8'||oneElement == '9')
               stack.push(infix);
            
            if (oneElement == '+')
               stack.push(infix);
               
            if (oneElement == '-')
               stack.push(infix);
               
            if (oneElement == '*')
               stack.push(infix);
               
            if (oneElement == '%')
               stack.push(infix);
            if (oneElement == ')')
            {
               stack.pop();
               postfix = postfix + oneElement;
            }
            else
               postfix = postfix + oneElement; 
         	String newLine = new String();
            for (int j = 0; j < postfix.length(); j++)
            {
               
               newLine  = newLine + stack.pop();
            }
            while (stack.empty()) {
               postfix = postfix + stack.pop();

              
            }
         
                     			 
         }  
      
         return postfix;
      }
   	
   }// end of class

this is the ArrayStack and StackInterface class

import java.util.EmptyStackException;

/**
* A generic Stack class implemented with an array
* @author William McDaniel Albritton
*/			
    public class ArrayStack<T> implements StackInterface<T> {
    
   // data fields
   // size of array (size can increase if needed)
      private Integer size = new Integer(5); 
   // top of the stack is the last element in the array 
      private Integer top = new Integer(-1);
   // When using a generic container class with arrays,
   // we must cast when we instantiate an array.	
      private T array[ ] = (T[ ]) new Object[size];		
   
   /**Constructor*/
       public ArrayStack(){
       //We don't need any code in constructor,
       //as we already initialized the data fields.
      }
   
   /**Tests if the stack is empty
    * @return true/false if empty/not empty */
       public boolean empty(){
         return top == -1;
      }
   
   /**Looks at the object at the top of the stack 
   * without removing it from the stack.
   * @return an address to the top item on the stack 
   * @exception EmptyStackException if the stack is empty*/
       public T peek() throws EmptyStackException{
      //check to see if empty		 
         if(this.empty()){
            throw new EmptyStackException();
         }
      //return pointer to top element in array
      //but do NOT take it off the stack!			
         return array[top];
      }
       
   /**Removes the object at the top of stack 
   * and returns the address of this object
   * @return an addressed to the top item on the stack 
   * @exception EmptyStackException if the stack is empty*/
       public T pop() throws EmptyStackException{
      //check to see if stack is empty		 
         if(this.empty()){
            throw new EmptyStackException();
         }
      //return pointer (address) to top element in array
      //and take it off the stack				
         return array[top--];	
      	//This is the same code as:
      	//int temp = top;
      	//top = top - 1;
      	//return array[temp];
      } 
   
   /**Pushes an item onto the top of this stack 
   * @param item the item that is pushed on the stack */
       public void push(T item){
       //check to see if the stack is full
         if(top + 1 == size){
         //make the array twice as big!
            Integer size2 = size * 2;
         // When using a generic container class with arrays,
         // we must cast when we instantiate an array.				
            T array2[] = (T[]) new Object[size2];
         //copy elements into new array   
            System.arraycopy(array, 0, array2, 0, size);
         //reassign the array & size
            size = size2;
            array = array2;
         }
         array[++top] = item;	
      	//This is the same code as:
      	//top = top + 1;
      	//array[top] = item;
      } 
   
   /**Driver code to test class
   * @param arguments Commandline arguments not used */
  
   	 
   }//end class
import java.util.EmptyStackException;

/**
* A generic Stack interface roughly based on Java API's class Stack
* @author William McDaniel Albritton
*/		
    public interface StackInterface<T>{
   
   /**Tests if the stack is empty
    * @return true/false if empty/not empty */
       public boolean empty();
   
   /**Looks at the object at the top of the stack 
   * without removing it from the stack.
   * @return the address to the top item on the stack 
   * @exception EmptyStackException if the stack is empty*/
       public T peek() throws EmptyStackException;
       
   /**Removes the object at the top of stack 
   * and returns the address of this object
   * @return the address to the top item on the stack 
   * @exception EmptyStackException if the stack is empty*/
       public T pop() throws EmptyStackException;	 
   
   /**Pushes an item onto the top of this stack 
   * @param item the item that is pushed on the stack */
       public void push(T item);
       
   }//end interface

Thanks in advance for your help! :)

Recommended Answers

All 8 Replies

your code is a mess. Too many redundancies and worst of all you have a memory leak in your stack implementation.

Don't be discouraged by ejosiah - looks like he's having a bad day!
Does the problem happen on valid input data, or only on the test cases that have unmatched brackets? (Because it looks like you are popping one more item than you have pushed)

you got the having a bad day part right anyways about your memory leak. Garbage collection does not work for you here becase you manage your own memory internally. everytime you pop from your stack and reduce your size by one your internal array still has a reference to the Object which was poped so its not avaliable for garbage collection. to fix this in your pop method do this

public T pop() throws EmptyStackException{
    if(this.empty()){
         throw new EmptyStackException();
     }

     T value =  array[top--]

     // remove reference to poped it
     array[top] = null

    // your leak is gone now you can return
    return value;
}

one more thing do not use (this) reference to call your methods or refere to your variables onless there is an ambiguity.

for your problem your stack is empty which must mean that your conditional statements are not working correctly.
Hope this helps

This is your problem. look in your test code

while (stack.empty()) {
   postfix = postfix + stack.pop();
}

look at your condition its runs when your stack is empty resulting in your empty stack exception. you do still have other errors in your code but lets take it one step at a time fix this first.

thank you for your suggestions :)

I revised my code and this is what i have thus far...still the output is wrong. I am just learning stacks and I am not sure what to do.

import java.util.Scanner;
   import java.io.File;
   import java.util.StringTokenizer;
   import java.util.InputMismatchException;
   import java.io.FileNotFoundException;


    public class KashiwabaraNicole16
   {
   /*******************************************************************************
   *  Outputs integers from user input external files.
   ********************************************************************************/
   
       public static void main( String[] commandlineArguments )throws NullPointerException  {
      //Error Checking For Command Line Arguments..
         if(commandlineArguments.length == 0){
            System.out.println("Please enter the file name as the 1st commandline argument.");
         } 
         else {
         //connect to file (does NOT create new file)
            for(int i=0; i<commandlineArguments.length; i++) {
               File file = new File(commandlineArguments[i]);
            
               Scanner inputFromFile = null;
            
               try {
                  inputFromFile = new Scanner(file);
               } 
                   catch (FileNotFoundException exception) {
                  //Print error message.
                  
                     System.out.print("ERROR: File not found for \"");
                     System.out.println(commandlineArguments[i]+"\"");
                  
                  
                     return;
                  }
            
               String [] myArray = new String[2000];// Create the array to hold all elements that are found in the file
            
               int count = 0;  // number of elements
            
               count = createOutput( inputFromFile, myArray ); // adds each element into array
            
               System.out.println( "Reading from file \"" + commandlineArguments[i] + "\":" );             
                       
               displayArray( myArray, count); // calls displayArray method
            
            }//end of "if" for connecting to file
         }//end of "else" for commandlineArguments
      }//end of main() method
   
       public static int createOutput( Scanner myScanner, String [] stringArray ) {
         int count = 0; // number of elements
      
         String element; //variable of each element
      
      
         while( myScanner.hasNext() )// Loops until end of file
         {
            
            element = myScanner.next();
             
          
            stringArray[ count ] = element; //stores the element into the array using count as the index
            count++; // increase 1
         }
         return count; //returns total number of elements found in the file
      }
   
   
   
       public static void displayArray( String [] stringArray, int count) {
      // For loop to step through each item in the array
      
         for( int i = 0; i < count; i++ ) {
            
                       // Print the index and the corresponding element value
            System.out.println( "Infix expression = " + stringArray[i] );
         	
            String postFixExpression = infixToPostfix(stringArray[i]);
         	
         	
            System.out.println("Postfix expression = " + postFixExpression);
         }
      }
    
      
       public static String infixToPostfix(String infix){
       
         String postfix = "";
      	   
      //step 1: get parameter infix
         String stringArray = infix;
         StackInterface<String> stack 
            = new ArrayStack<String>();
      
      
                     
         for (int i = 0; i < infix.length(); i++)
         {
            String oneElement = infix.substring(i);
         
            if (oneElement == "(")
            
               stack.push(oneElement);
            
            
            if (oneElement == "+")
            
               stack.push(oneElement);           
            if (oneElement == "-")
               stack.push(oneElement);
                    
            if (oneElement == "*")
               stack.push(oneElement);
               
            if (oneElement == "%")
            
               stack.push(oneElement);
            
            else             	//you need a while loop to do this part
            //{pop operators off stack, add each operator to end of output string,until pop a left parenthesis }	
            
            
               while (oneElement == ")")
               {
                                   
                     stack.pop();
                     stack.push(oneElement);
                  	   
                    
                }
            postfix = postfix + oneElement;
         }
      	
      	
         
         return postfix;
      }
   	
   }// end of class

if you read the info in the link I sent you Then the code I'm about to give you should not be hard to understand.

public class InfixToPostfix {
	
	/**
	 * Converts an infix string to its postfix version.
	 * 
	 * @param infix infix string to convert
	 * @return postfix version of input string;
	 */
	public String toPostFix(String infix){
		String postfix = "";
		Stack<Character> operators = new Stack<Character>();
		
		for(int i = 0, length =  infix.length(); i < length; i++){
			Character element = infix.charAt(i);
			
			if(isOperator(element)){
				if(operators.isEmpty()){
					operators.push(element);
				}else if(hasHigherPrecedence(operators.peek(),element)){
					postfix += addOperatorsToPostfix(operators);
					operators.push(element);
				}else{
					operators.push(element);
				}
			}else{
				postfix += element;
			}
		}
		
		postfix += addOperatorsToPostfix(operators);
		
		
		return postfix;
	}
	
	/*
	 * creates a string of operaters in the stack starting
	 * with the element at the top of the stack
	 */
	private String addOperatorsToPostfix(Stack<Character> operators) {
		String str = "";
		while(!operators.isEmpty()){
			if(operators.peek().equals('(') || operators.peek().equals(')')){
				operators.pop();
				continue;
			}
			str += operators.pop();
		}
		return str;
	}
	
	/*
	 * checks if operatorA has a higher precedence than operatorB
	 */
	private boolean hasHigherPrecedence(Character operatorA, Character operatorB){
		switch(operatorA){
		case '(' : return false;
		case ')' : return true;
		case '*' : return false;
		case '/':
			switch(operatorB){
			case '*' : return false;
			case '/' : return false;
			case '+' : return true;
			case '-' : return true;
			}
		case '%':
			switch(operatorB){
			case '*' : return false;
			case '/' : return false;
			case '+' : return true;
			case '-' : return true;
			}
		case '+':
			switch(operatorB){
			case '*' : return false;
			case '/' : return false;
			case '+' : return false;
			case '-' : return true;
			}
		case '-':
			switch(operatorB){
			case '*' : return false;
			case '/' : return false;
			case '+' : return false;
			case '-' : return false;
			}
		default: return false;
		}
		
	}
	
	/*
	 * checks if a character is an arithmetic operator
	 */
	private boolean isOperator(Character what){
		switch(what){
		case '(':;
		case ')':;
		case '*':;
		case '/':;
		case '+':;
		case '-': return true;
		default : return false;
		}
	}
}

.
Note that the sixed entry in your input file is not correct.

i'm calling back my statement on your sixted entry not being correct. my code does not account for % operators so you are going to have to figure that out for your self. you need to also replace the hasHigerPrecedence method with this

private boolean hasHigherPrecedence(Character operatorA, Character operatorB){
		switch(operatorA){
		case '(' : return false;
		case ')' : return true;
		case '*' :
			switch(operatorB){
			case '*' : return false;
			case '/' : return true;
			case '+' : return true;
			case '-' : return true;
			}
		case '/':
			switch(operatorB){
			case '*' : return false;
			case '/' : return false;
			case '+' : return true;
			case '-' : return true;
			}
		case '%':
			switch(operatorB){
			case '*' : return false;
			case '/' : return false;
			case '+' : return true;
			case '-' : return true;
			}
		case '+':
			switch(operatorB){
			case '*' : return false;
			case '/' : return false;
			case '+' : return false;
			case '-' : return true;
			}
		case '-':
			switch(operatorB){
			case '*' : return false;
			case '/' : return false;
			case '+' : return false;
			case '-' : return false;
			}
		default: return false;
		}
		
	}
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.