Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 9 of 9

Thread: Infix to Prefix

  1. #1
    Junior Member
    Join Date
    Oct 2011
    Posts
    3
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Infix to Prefix

    Hi i keep receiving the error:

    Exception in thread "main" java.util.EmptyStackException
    at java.util.Stack.peek(Stack.java:85)
    at java.util.Stack.pop(Stack.java:67)
    at calc.Main.calculate(Main.java:147)
    at calc.Main.main(Main.java:251)
    Java Result: 1

    I keep trying to google and read on how to fix it, but i deadlocked. Help pls?

    Heres my code:

     
    /*
     * To change this template, choose Tools | Templates
     * and open the template in the editor.
     */
     
    package calc;
     
    import java.util.*;
    import jpb.*;
     
    public class Main {
     
        private integerStack myStack;
        private String infix;
        private String postfix = "";
     
        //creates an empty stack used for declaring methods
        public Main(String in) {
            infix = in;
    	int size = in.length();
    	myStack = new integerStack(size);
        }
     
        //method to convert infix expression to postfix expression
        public String convert() {
            for (int j = 0; j < infix.length(); j++) {
                char ch = infix.charAt(j);
                switch (ch) {
                    case '+':
                    case '-':
                        checkPrecedence(ch, 1);
                        break;
                    case '*':
                    case '/':
                        checkPrecedence(ch, 2);     // pop operators
                        break;
                    case '%':
                        checkPrecedence(ch,3);
                        break;
                    case '(':
                        myStack.push(ch);           // push it
                        break;
                    case ')':
                        parentheses(ch);            // pop operators
                        break;
                    default:                        // must be an operand
                        postfix = postfix + ch;     // append to output
                        break;
                }
            }
            while (!myStack.isEmpty()) {
                postfix = postfix + myStack.pop();
    	}
            System.out.println(postfix);
    	return postfix;                             // return postfix
        }
     
        //method to order each operator encountered by the correct precedence
        public void checkPrecedence(char opThis, int p1) {
            while (!myStack.isEmpty()) {
                char opTop = myStack.pop();
                if (opTop == '(') {
                    myStack.push(opTop);
                    break;
                 }                                           // it's an operator
                 else {                                      // precedence of new op
                    int p2;
                    if (opTop == '+' || opTop == '-')
                        p2 = 1;
                    else if (opTop=='*' || opTop=='/')
                        p2=2;
                    else
                        p2=3;
                    // if precendence of new op less than precendence of old save newly-popped op
                    if (p2 < p1){
                        myStack.push(opTop);
                        break;
                    }
                    //else append to postfix
                    else
                        postfix = postfix + opTop;
                }
            }
    	myStack.push(opThis);
        }
     
        //method to grant expressions inside parentheses top precedence
        public void parentheses(char ch){
            while (!myStack.isEmpty()) {
                char paren = myStack.pop();
                if (paren == '(')
                    break;
                else
                    postfix = postfix + paren;
    	}
        }
     
        //method to calculate postfix expression
        public static int calculate(String input) throws Exception {
            int finalResult;
            Stack <Integer> solution = new Stack<Integer>();
            int op1,op2,result;
     
            for(int i=0;i<input.length();i++){
                char c=input.charAt(i);
                try {
                    switch (c){
                        case '+':
                            op1=solution.pop();
                            op2=solution.pop();
                            result=op1 + op2;
                            solution.push(result);
                            break;
                        case '-':
                            op1=solution.pop();
                            op2=solution.pop();
                            result=op1 - op2;
                            solution.push(result);
                            break;
                        case '*':
                            op1=solution.pop();
                            op2=solution.pop();
                            result=op1 * op2;
                            solution.push(result);
                            break;
                        case '/':
                            op1=solution.pop();
                            op2=solution.pop();
                            result=op1 / op2;
                            solution.push(result);
                            break;
                        case '%':
                            op1=solution.pop();
                            op2=solution.pop();
                            result=op1 % op2;
                            solution.push(result);
                            break;
                        default:
                            solution.push(Integer.parseInt(Character.toString(c)));
                            break;
                    }
                }
     
                catch(EmptyStackException e){
                    System.exit(-1);
                }
     
            }        
            finalResult = solution.pop();
            return finalResult;
     
     
        }
     
        //method to check if number of operators is more than number of operands
        public static boolean checkOps(String input){
            int countNumbers=0;
            int countOperators=0;
     
            for(int i=0;i<input.length();i++){
                char ops=input.charAt(i);
                switch(ops){
                    case '+':case '-':case '*':case '/': case '%':
                        countOperators++;break;
                    default: countNumbers++;
                }
            }
            if(countNumbers<=countOperators)
                return false;
            else
                return true;
        }
     
        //method to check if infix contains floating point numbers.
        public static boolean checkFloat(String input){
            char [] c=input.toCharArray();
     
            for (int i=0;i<c.length;i++){
                if (c[i]=='.'){
                return false;}
            }
            return true;
        }
     
        //method to check if infix expression is in correct form
        public static boolean checkInfix(String input){
            char[] c=input.toCharArray();
     
            for(int i=0;i<c.length;i++){
                if(Character.isDigit(c[i]) && Character.isDigit(c[i+1])){
                    return false;
                }
                else if (c[i]=='(' && !Character.isDigit(c[i+1]))
                    return false;
                else
                    return true;
            }
            return true;
        }
     
        public static void main(String[] args) throws Exception {
            while(true){
                SimpleIO.prompt("Enter an infix expression to evaluate: \n");
                String input = SimpleIO.readLine();
     
                //if user enters float show error message and prompt for another expression
                while(!checkFloat(input)){
                    System.out.println("Error in Expression! Cannot accept "
                            + "floating numbers \n");
                    SimpleIO.prompt("Enter an infix expression to evaluate: \n");
                    input = SimpleIO.readLine();
                }
     
                //if user enters incorrect formatted infix show error message and prompt for another expression
                while(!checkInfix(input)){
                    System.out.println("Error in Expression! No operator between "
                            + "operands. Also last token must be an operand \n");
                    SimpleIO.prompt("Enter an infix expression to evaluate: \n");
                    input = SimpleIO.readLine();
                }
     
                //if user enters too many operators show error message and prompt for another expression
                while(!checkOps(input)){
                    System.out.println("Error in Expression! Operator cannot "
                            + "be preceded by an operator \n");
                    SimpleIO.prompt("Enter an infix expression to evaluate: \n");
                    input = SimpleIO.readLine();
                }
     
                //takes a value for x and creates new infix with entered value
                char[] c=input.toCharArray();
                String input2="";
     
                for(int i=0;i<c.length;i++){
                    if(c[i]=='x'){
                        SimpleIO.prompt("Enter a value for x: ");
                        c[i]=SimpleIO.readLine().charAt(0);
     
                        for(int j=0;j<c.length;j++){
                            input2+=c[j];
                        }
     
                        if(!Character.isDigit(c[i])){
                            System.out.println("You did not enter an integer "
                                    + "value for x ");
                            System.exit(-1);
                        }
                    }
                }
     
                String output;
                Main theTrans = new Main(input2);
                output = theTrans.convert();
                int result= calculate(output);
     
                System.out.println("Postfix is: " + output );
                System.out.println("Postfix evaluated is: " + result +'\n');
                SimpleIO.prompt("Evaluate another expression? (y/n)");
     
                if (SimpleIO.readLine().equals("n")){
                    System.exit(0);
                }
            }
        }
     
        //class to build stack which host integers and char
        class integerStack {
            private char[] stackArray;
    	private int top;
    	public integerStack(int size) {
                stackArray = new char[size];
    	    top = -1;
    	}
     
            public void push(char j) {
                stackArray[++top] = j;
    	}
     
    	public char pop() {
                return stackArray[top--];
    	}
     
    	public char peek() {
                return stackArray[top];
            }
     
    	public boolean isEmpty() {
                return (top == -1);
            }
        }
    }


  2. #2
    Junior Member
    Join Date
    Oct 2011
    Posts
    3
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Infix to Prefix

    sorry the error occurs at:

    finalResult = solution.pop(); //line 147
     
    //........
     
    int result= calculate(output); //line 251

  3. #3
    Think of me.... Mr.777's Avatar
    Join Date
    Mar 2011
    Location
    Pakistan
    Posts
    1,136
    My Mood
    Grumpy
    Thanks
    20
    Thanked 82 Times in 78 Posts
    Blog Entries
    1

    Default Re: Infix to Prefix

    Yeah and the problem is, your stack is empty and you want to pop it.
    You must implement, isEmpty() and isFull() for stack class.
    And call isFull() before pushing data and isEmpty() before poping.

    Also, do you have clear understanding of stack concept?

  4. #4
    Grand Poobah
    Join Date
    Mar 2011
    Posts
    1,545
    My Mood
    Grumpy
    Thanks
    0
    Thanked 167 Times in 158 Posts

    Default Re: Infix to Prefix

    Quote Originally Posted by Mr.777 View Post
    You must implement isFull() for stack class.
    ???

    Since when have Stacks had an isFull method?
    Improving the world one idiot at a time!

  5. #5
    Think of me.... Mr.777's Avatar
    Join Date
    Mar 2011
    Location
    Pakistan
    Posts
    1,136
    My Mood
    Grumpy
    Thanks
    20
    Thanked 82 Times in 78 Posts
    Blog Entries
    1

    Default Re: Infix to Prefix

    Quote Originally Posted by Junky View Post
    ???

    Since when have Stacks had an isFull method?
    What if OP had not implemented the circular stack?
    And what if his stack is, let's say of size 10 and there are already 10 values in it????

  6. #6
    Administrator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,318
    Thanks
    181
    Thanked 833 Times in 772 Posts
    Blog Entries
    5

    Default Re: Infix to Prefix

    The exception provides a lot of information - you are trying to pop a stack that is empty.

    The Stack class does not contain an isFull method, and implementing one would not solve your problem. A circular stack is beside the point - you are accessing the J2SE class Stack which is the problem (at least the problem as it manifests itself)

    Your code is not an SSCCE, so I cannot run it. That being said, inspect the calculate method and make sure your code adds to the stack as appropriate. Add some println's in there, or use a debugger, to step through the code and make sure it behaves properly.

  7. #7
    Think of me.... Mr.777's Avatar
    Join Date
    Mar 2011
    Location
    Pakistan
    Posts
    1,136
    My Mood
    Grumpy
    Thanks
    20
    Thanked 82 Times in 78 Posts
    Blog Entries
    1

    Default Re: Infix to Prefix

    Quote Originally Posted by copeg View Post
    The Stack class does not contain an isFull method, and implementing one would not solve your problem.
    Why stack class can not have a isFull() method? Kindly give me some reasons. As far as i know, if you are playing with a fixed size stack, you must check it somehow, whether stack is full or not, so that you could push() data into it.

  8. #8
    Administrator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,318
    Thanks
    181
    Thanked 833 Times in 772 Posts
    Blog Entries
    5

    Default Re: Infix to Prefix

    Quote Originally Posted by Mr.777 View Post
    Why stack class can not have a isFull() method? Kindly give me some reasons. As far as i know, if you are playing with a fixed size stack, you must check it somehow, whether stack is full or not, so that you could push() data into it.
    It can, but like Junky and I said the java.util.Stack class does not contain this method ( Stack (Java Platform SE 6) ), and this is where the exception is being thrown - from a call to pop on a java.util.Stack instance.

  9. #9
    Think of me.... Mr.777's Avatar
    Join Date
    Mar 2011
    Location
    Pakistan
    Posts
    1,136
    My Mood
    Grumpy
    Thanks
    20
    Thanked 82 Times in 78 Posts
    Blog Entries
    1

    Default Re: Infix to Prefix

    Well copeg, i was not talking about java.util.Stack, i know it doesn't implement isFUll(), infact if i ever implement a stack, i always use isFull() method.
    Anyways, thanks Copeg and Junky

Similar Threads

  1. [SOLVED] Using Stack Data Type to Solve an Infix Expression
    By patriots1049 in forum What's Wrong With My Code?
    Replies: 9
    Last Post: October 9th, 2011, 01:39 PM
  2. [SOLVED] Help with prefix and postfix(increment&decrement)
    By Lokesh in forum Object Oriented Programming
    Replies: 1
    Last Post: February 12th, 2011, 10:20 AM
  3. convert infix to postfix
    By tina G in forum Algorithms & Recursion
    Replies: 2
    Last Post: March 11th, 2010, 01:46 AM
  4. Infix to Prefix parser
    By r2ro_serolf in forum Java Theory & Questions
    Replies: 1
    Last Post: November 8th, 2009, 01:11 AM
  5. Infix to Prefix
    By Sasarai in forum Algorithms & Recursion
    Replies: 2
    Last Post: November 7th, 2009, 10:03 PM

Tags for this Thread