java - 使用堆栈类在 Java 中对后缀进行中缀

Question

我正在尝试使用堆栈在 Java 中将中缀写入后缀程序。这是我的代码:

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

输入:

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

输出:

 at+bac++*cd+^

“*”应该在“+^”之后，但它在“++”之后。我找不到错误。

Answer 1

这只是一个小错误。在此代码中，您在“in”数组中查找“(”，这是没有意义的。您只想在堆栈中查找它。

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--;
    }
}

改成这样就可以了

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

这应该可以修复错误。但是还有很多其他细节你可以改进。例如将部分代码放入另一种方法中，并利用泛型和自动装箱。使用字符串而不是字符来允许运算符包含一个以上的字符，并实现运算符优先级，因此您不需要那么多括号。

看看这个。

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();
            }
        }
}