使用堆栈类在java中中缀到后缀 [英] infix to postfix in java using stack class

问题描述

我正在尝试使用堆栈将中缀写入 java 中的 postfix 程序.这是我的代码:

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

输入:

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

输出:

 at+bac++*cd+^

*"应该在+^"之后，但在++"之后.我找不到错误.

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

推荐答案

这只是一个小错误.在这段代码中，您在in"数组中查找 '(' ，这是没有意义的.您只想在堆栈中查找它.

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

改成这个就行了

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.

看看这个.

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

这篇关于使用堆栈类在java中中缀到后缀的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！