infix to postfix in java using stack class

Question

I'm trying to write infix to postfix program in java using stack. Here is my code:

import java.io.*;
import java.util.*;
public class ONP{
        public static void main(String args[]) throws java.io.IOException, NumberFormatException ,EmptyStackException{
            BufferedReader br= new BufferedReader(new InputStreamReader(System.in));

            int n=Integer.parseInt(br.readLine());
            StringBuilder out= new StringBuilder();

            Stack st=new Stack();

            for(int i=0;i<n;i++){
                String input=br.readLine();
                char in[]=input.toCharArray();
                int len=input.length();
                for (int j=0;j<len;j++){
                    if (in[j]>='a' && in[j]<='z'){
                        out.append(in[j]);
                    }

                    else if(in[j]=='('){
                        st.push(new Character(in[j]));

                    }
                    else if(in[j]=='+' || in[j]=='-' || in[j]=='*' || in[j]=='/' || in[j]=='^'){
                        st.push(new Character(in[j]));

                    }

                    else if(in[j]==')'){
                        int k=j;

                        while(in[k]!='(' && !st.empty() ){

                            char ch=st.pop().toString().charAt(0);
                            if(ch!='('&&ch!=')')
                             out.append(ch);
                            k--;
                        }
                    }


                }
                out.append("\n");

            }
            System.out.print(out);
        }
}

Input:

 ((a+t)*((b+(a+c))^(c+d)))

Output:

 at+bac++*cd+^

"*" should come after "+^" but it comes after "++". I can't find the bug.

Answer 1

Well you need to implement operator precedence, and you haven't. You need to look up the Dijkstra Shunting-yard algorithm.

Answer 2

It's just a small error. In this code you look for '(' in the "in" array which makes no sense. You only want to look for it on the stack.

else if(in[j]==')'){
    int k=j;

    while(in[k]!='(' && !st.empty() ){

        char ch=st.pop().toString().charAt(0);
        if(ch!='('&&ch!=')')
         out.append(ch);
        k--;
    }
}

Just change it to this

else if(in[j]==')'){
    while(!st.empty() ){
        char ch=st.pop().toString().charAt(0);
        if(ch == '(') break;
        out.append(ch);
    }
}

That should fix the error. But there are a lot of other details you could improve. e.g. put part of the code into another method and make use of generics and autoboxing. Use Strings instead of chars to allow operators with more then one character and also implement operator precedence so you don't need so many parentheses.

Look at this.

import java.io.*;
import java.util.*;
import java.util.regex.*;

public class ONP {
        private static int precedence(String operator) {
            switch(operator) {
                case "(": return 0;
                case "+": case "-": return 1;
                case "*": case "/": return 2;
                case "^": return 3;
                case "sin": case "cos": return 4;
                default: return -1;
            }
        }

        private static List<String> tokenize(String input) {
            ArrayList<String> tokens = new ArrayList<>();
            Pattern p = Pattern.compile("\\(|\\)|[A-Za-z]+|\\d*\\.\\d*|\\d+|\\S+?");
            Matcher m = p.matcher(input);
            while(m.find()) {
              tokens.add(m.group());
            }
            return tokens;
        }

        private static List<String> toPostfix(List<String> infix) {
            Stack<String> st = new Stack<>();
            ArrayList<String> out = new ArrayList<>();
            for(String s: infix) {
                if(s.equals("(")){
                    st.push(s);
                } else if(s.equals(")")){
                    while(!st.empty() ){
                        String s2 = st.pop();
                        if(s2.equals("(")) break;
                        out.add(s2);
                    }
                } else if(precedence(s) > 0) {
                    int p = precedence(s);
                    while(!st.isEmpty() && precedence(st.peek()) >= p) out.add(st.pop());
                    st.push(s);
                } else {
                    out.add(s);
                }
            }
            while(!st.isEmpty()) out.add(st.pop());
            return out;
        }

        public static void main(String args[]) throws java.io.IOException, NumberFormatException ,EmptyStackException{
            BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
            int n=Integer.parseInt(br.readLine());
            for(int i=0;i<n;i++){
                String input=br.readLine();
                List<String> tokens = tokenize(input);
                System.out.println("tokens: " + tokens);
                List<String> postfix = toPostfix(tokens);
                System.out.print("postfix: ");
                for(String s: postfix) System.out.print(s + " ");
                System.out.println();
            }
        }
}