Converting infix expressions to postfix expressions

Question

I have a problem i can't find the wrong in this function it sometimes do well with any input but it cached when there is parentheses in the input {i want to know where is the wrong in this code and how to fix it , and Is there another better way instead this way}

    public static String Converting_infix_expressions_to_postfix_expressions(String infix) throws Exception{
    StringTokenizer st = new StringTokenizer(infix);
    int numOF_tokens = st.countTokens();
    String postfix = "" ;
    for (int i = 1; i <= numOF_tokens; i++) {
        String term = st.nextToken();
        try {  // if it is an Float there is no problem will happen
            float x =  Float.parseFloat(term);
            postfix += x +" " ;
            System.out.println("term is number " + term);
        } catch (Exception e) {
            System.out.println("term is symbol " + term);
            if(stack.isEmpty())
                stack.push(term);
            else if(term == "(")
                stack.push(term);
            else if(term == ")"){
                while((String)stack.peek() != "(")
                    postfix += stack.pop() +" ";
                stack.pop();
            }

            else{
                int x = 0,y = 0;
                switch(term){
                case "+": x = 1; break;
                case "-": x = 1; break;
                case "*": x = 2; break;
                case "/": x = 2; break;
                }
                switch((String)stack.peek()){
                case "+": y = 1; break;
                case "-": y = 1; break;
                case "*": y = 2; break;
                case "/": y = 2; break;
                }
                if(x > y)
                    stack.push(term);
                else {
                    int x1 = x , y1 = y;
                    boolean puchedBefore = false;
                    while(x1 <= y1){
                        postfix += stack.pop() +" ";
                        if(stack.isEmpty() || stack.peek() == "(" ){
                            stack.push(term);
                            puchedBefore = true;
                            break;
                        }
                        else{
                            switch(term){
                            case "+": x1 = 1; break;
                            case "-": x1 = 1; break;
                            case "*": x1 = 2; break;
                            case "/": x1 = 2; break;
                            }
                            switch((String)stack.peek()){
                            case "+": y1 = 1; break;
                            case "-": y1 = 1; break;
                            case "*": y1 = 2; break;
                            case "/": y1 = 2; break;
                            }
                        }
                    }
                    if(!puchedBefore)
                        stack.push(term);
                }   
            }
        }
    }
    while(!stack.isEmpty()){
        postfix += stack.pop() +" ";
    }
    System.out.println("The postfix expression is : " + postfix);
    return postfix;
}

You should use [`equals` instead of `==` when comparing strings](http://stackoverflow.com/questions/513832/how-do-i-compare-strings-in-java). — assylias, May 03 '12 at 15:17
Have you tried debugging? Get a case that you know fails and set a breakpoint, then step through to see where it is making a decision that doesn't make sense to you. Also, examples of expressions that work (and their output) and those that don't work (and their output) would help make this a better question. — digitaljoel, May 03 '12 at 15:18
There is quite a bit of repetition in the code... Did you consider writing a descending recursive parser instead? — Thomas Mueller, May 03 '12 at 15:19
Have you considered the [Shunting Yard Algorithm](http://en.wikipedia.org/wiki/Shunting-yard_algorithm)? — Johm Don, May 03 '12 at 15:20

score 1 · Accepted Answer · answered May 03 '12 at 15:42

1

You have a couple of problems with your code.

You should make a custom string tokenizer since there may not be a space between a parenthesis and a number. Ex: (5 + 6)
The try-catch block is not being used properly. Consider, first checking if the field is symbol then moving on to parsing it as a Float. This way you can avoid having most of your code appear in the catch block.
The bug you are referring to can be fixed with the follow change to line 18.

while(!stack.isEmpty() && (String)stack.peek() != "(")

answered May 03 '12 at 15:42

user845279

2,794
1
20
38

The same answer but i want the return Sting without parentheses by a good manner without deleting the parentheses at the end of the excepression – mohsen May 03 '12 at 16:17
this is an input which the program crashed with 1 * 2 + 3 * ( 5 + 2 ) - 3 ; – mohsen May 03 '12 at 16:20
Have you tried #3 solution i mentioned above? I think you just forgot to check if stack is not empty. Btw, is this your homework? – user845279 May 03 '12 at 16:29
yes i tried #3 but it has the same output. but the problem i have that i still thought that the above code (with your instructions #3) should Handel the problem with inputs with parentheses like 1 * 2 + 3 * ( 5 + 2 ) - 3 and output the postfix excepression without parentheses but the out put is 1.0 2.0 * 3.0 * + 5.0 2.0 + ( 3.0 - ) so i wanna know why this code can't Handel this case – mohsen May 03 '12 at 17:51

Converting infix expressions to postfix expressions

1 Answers1