java - 链表删除错误

Question

我有这个家庭作业使用堆栈制作计算器并将中缀转换为后缀。我的中缀后缀方法工作正常。但是另一种评估它的方法适用于所有情况，除非倍数或除数产生两位数。我的计算器不支持两位数输入，但支持计算两位数。尝试输入:2+2*5/2、2+5*4/2，以及其他一些类似的格式。
当它开始计算除法时，错误出现在第二次运行的第 151 行。
这是链表中发生的事情:
[2, 2, 5, *, 2,/, +]
[2, 10, 2,/, +]
[10, 2, +] -- 错误
它应该删除/、 2 和 10 ，因此 3 removes 语句。但是当它执行 eval.remove(eval.get(i-1)) 时，前面的 2 消失了，而 10 变成了前面的节点。

    import java.util.Stack;
import java.util.LinkedList;

public class Calculator
{
    Stack<Character> infix = new Stack<Character>();

    StringBuilder postfix = new StringBuilder();
    Stack<String> postfix_str = new Stack<String>();

    String operators = "+-*/^";

    String infix2postfix(String infix_str)
    {
        int i = 0;
        boolean flag = true;

        while (!infix_str.isEmpty())
        {
            if (infix_str.charAt(i) == '(')
            {
                infix.push(infix_str.charAt(i));
                infix_str = infix_str.substring(i+1, infix_str.length());
            }
            else
            {
                if (Character.getNumericValue(infix_str.charAt(i)) >= 0 && 
                    Character.getNumericValue(infix_str.charAt(i)) <= 9)
                {
                    postfix.append(infix_str.charAt(i));
                    postfix_str.push(String.valueOf(infix_str.charAt(i)));//added
                    infix_str = infix_str.substring(i+1, infix_str.length());
                }
                else //operator
                {
                    if (!(infix_str.charAt(i) == ')'))
                    {
                        if (infix.empty() || infix.peek() == '(' || !(preced(infix_str.charAt(i), infix.peek())))
                        {
                            infix.push(infix_str.charAt(i));
                            infix_str = infix_str.substring(i+1, infix_str.length());
                        }
                        else
                        {
                            postfix_str.push(String.valueOf(infix.peek()));//added
                            postfix.append(infix.pop());
                        }
                    }
                    else
                    {
                        try
                        {
                            while (infix.peek() != '(')
                            {
                                postfix_str.push(String.valueOf(infix.peek()));//added
                                postfix.append(infix.pop());
                            }
                            infix.pop();
                            infix_str = infix_str.substring(i+1, infix_str.length());
                         }
                         catch(Exception EmptyStackException)
                         {
                            System.out.println("Unbalanced Parathesis");
                            break;
                         }
                    }
                }
            }
        }
        while (!infix.empty())
        {
            postfix_str.push(String.valueOf(infix.peek()));//added
            postfix.append(infix.pop());
        }
        System.out.println(postfix);
        System.out.println(postfix_str.toString());
        return postfix.toString();
    }

    /**
     * 
     * @param statement operator, top of stack
     * @return true to pop
     */
    boolean preced(char arg1, char arg2)//when to pop (true - pop)
    { 
        String firstPreced = "^";
        String secondPreced = "*/";
        String thirdPreced = "+-";

        //EQUALS TO
        if ((thirdPreced.charAt(0) == arg1 || thirdPreced.charAt(1) == arg1)
                                          &&
            (thirdPreced.charAt(0) == arg2 || thirdPreced.charAt(1) == arg2))
        {return true;}
        if ((secondPreced.charAt(0) == arg1 || secondPreced.charAt(1) == arg1)
                                          &&
            (secondPreced.charAt(0) == arg2 || secondPreced.charAt(1) == arg2))
        {return true;}
        if (firstPreced.charAt(0) == arg1
                        &&
            firstPreced.charAt(0) == arg2) 
        {return true;}


        if ((thirdPreced.charAt(0) == arg1 || thirdPreced.charAt(1) == arg1)
                                          &&
            (secondPreced.charAt(0) == arg2 || secondPreced.charAt(1) == arg2))
        {return true;}

        if ((thirdPreced.charAt(0) == arg1 || thirdPreced.charAt(1) == arg1)
                                          &&
            (firstPreced.charAt(0) == arg2))
        {return true;}

        return false;
    }

    void evalPostfix(String postfix)//2+2*5/2
    {
        LinkedList<String> eval = new LinkedList<String>();
        //[2, 2, 5, *, 2, /, +]
        //[2, 10, 2, /, +]
        //[2, 5, +] -- should be
        //[10, 2, +] -- result
        while (!postfix_str.empty())
        {
            eval.addFirst(postfix_str.pop());
        }

        int i = 0;

        while (!(eval.size() == 1))
        {                      
            if (eval.get(i).equals("+") || eval.get(i).equals("-") || eval.get(i).equals("*") || eval.get(i).equals("/")
                    || eval.get(i).equals("^"))
            {
                double total = 0;
                if (eval.get(i).equals("+"))
                {total = Double.valueOf(eval.get(i - 1)) + Double.valueOf(eval.get(i - 2));}
                if (eval.get(i).equals("-"))
                {total = Double.valueOf(eval.get(i - 1)) - Double.valueOf(eval.get(i - 2));}
                if (eval.get(i).equals("*"))
                {total = Double.valueOf(eval.get(i - 1)) * Double.valueOf(eval.get(i - 2));}
                if (eval.get(i).equals("/"))
                {total = Double.valueOf(eval.get(i - 2)) / Double.valueOf(eval.get(i - 1));}
                if (eval.get(i).equals("^"))
                {total = Double.valueOf(eval.get(i - 1)) ^ Double.valueOf(eval.get(i - 2));}

                eval.remove(eval.get(i));
                eval.remove(eval.get(i-1));//BUG!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
                eval.remove(eval.get(i-2));

                i-=2;

                String sum_str = Double.toString(total);

                eval.add(i, sum_str);

                total = 0;
            }
            else
            {
                i++;
            }
        }
        System.out.println(eval.get(0));
    }
}



   import java.util.Scanner;

public class CalculatorTest
{
    public static void main(String[] args)
    {
        while(true)
        {
        Calculator calc = new Calculator();
        Scanner in = new Scanner(System.in);
        System.out.println("Enter Calc");
        String input = in.nextLine();
        calc.infix2postfix(input);
        calc.evalPostfix("");
        }
    }
}

Answer 1

看起来您正在使用 LinkedList#remove(Object) 从链表中删除项目。此方法通过引用删除项目，因此它搜索要删除的项目。由于一个项目可以多次出现在链表中，听起来它正在查找该项目的第一个实例( "2" )并删除该实例。 [*]

也许你可以尝试使用 LinkedList#remove(int) 按位置删除项目。所以:

eval.remove(i);
eval.remove(i-1);
eval.remove(i-2);

[*] 我在这里掩盖了一些细节，例如对两个字符串的两个引用实际上可以是同一个项目。这可能是由于字符串实习造成的，但如果没有对您的代码进行更详细的检查，我无法确定。