Thread: 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);
        }
    }
}

sorry the error occurs at:

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

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?

Originally Posted by Junky

???

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????

Originally Posted by copeg

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.

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