linkedlist remove bug

[zetologos]

I have this homework assignment to make a calculator using a stack and converting infix to postfix. My infix to postfix method works fine. But the other method to evaluate it works for all cases except when multiples or divisors result in double digits. My calculator does not support double digit entries but supports evaluating double digits. Try inputing: 2+2*5/2, 2+5*4/2, and some others in similar format.
The error is at line 151 on the second run when it goes to calculate the divide.
This is what happens in the linkedlist:
[2, 2, 5, *, 2, /, +]
[2, 10, 2, /, +]
[10, 2, +] -- error
It should delete the / , 2 , and 10 hence the 3 removes statement. But when it does eval.remove(eval.get(i-1)) the 2 in front disappears and the 10 become the front node.

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

[ztini]

A couple of things:

1) You are iterating / indexing on a stack. This is against the premise of a stack. Think in terms of a stack of plates at a dinner buffet. You can see the top plate, you can put a plate on top, you can take the top plate, or you can see if all the plates are gone. That's it. You can't look at the plates in the middle, you can't take a plate from the bottom, etc.

2) When you do arg0 ^ arg1, this is a bitwise operation not an arithmetic operation. You should use something like this instead: Math.pow(arg0, arg1)

3) When testing console based applications, such as this, you should always use JUnit testing.

Here is the infix to postfix using Stack that I came up with:

import java.util.Stack;


public class Calculator {
			
	private static char 
		ADD = '+', SUB = '-', DIV = '/', MUL = '*', POW = '^', MOD = '%';
	private static Stack<Character> queue = new Stack<Character>();
	private static String postFix;
	
	public static String convertToPostFix(String inFix) {
		postFix = "";

		for (char token : inFix.toCharArray()) {
			if (token == ADD || token == SUB || token == DIV || 
					token == MUL || token == POW || token == MOD)
				pushStack(token);
			else
				postFix += token;	
		}

		while (!queue.isEmpty())
			postFix += queue.pop();
		
		return postFix;
	}
	
	private static void pushStack(char value) {
		
		if (value == POW) {
			while (!queue.isEmpty() && 
					queue.peek() == POW)
				postFix += queue.pop();
		}
		
		else if (value == MUL || value == DIV || value == MOD) {
			while(!queue.isEmpty() && 
					(queue.peek() == MUL || queue.peek() == DIV ||
					queue.peek() == MOD || queue.peek() == POW))
				postFix += queue.pop();
		}
		
		else if (value == SUB || value == ADD) {
			while (!queue.isEmpty() && 
					(queue.peek() == SUB || queue.peek() == ADD ||
					queue.peek() == MUL || queue.peek() == DIV ||
					queue.peek() == MOD || queue.peek() == POW))
				postFix += queue.pop();
		}
		
		queue.push(value);		
	}

}

And the corresponding JUnit testing:

import static org.junit.Assert.assertTrue;
import org.junit.Test;


public class CalculatorTest {
	
	@Test
	public void testConvertToPostfix() {
		assertTrue(Calculator.convertToPostFix("3+5").equals("35+"));
		assertTrue(Calculator.convertToPostFix("3*5").equals("35*"));
		assertTrue(Calculator.convertToPostFix("3-5").equals("35-"));
		assertTrue(Calculator.convertToPostFix("3/5").equals("35/"));
		assertTrue(Calculator.convertToPostFix("3%5").equals("35%"));
		assertTrue(Calculator.convertToPostFix("3^5").equals("35^"));
		
		assertTrue(Calculator.convertToPostFix("1+2-3*4/5^6%7").equals("12+34*56^/7%-"));
		assertTrue(Calculator.convertToPostFix("7%1+2-3*4/5^6").equals("71%2+34*56^/-"));
		assertTrue(Calculator.convertToPostFix("6^7%1+2-3*4/5").equals("67^1%2+34*5/-"));
		assertTrue(Calculator.convertToPostFix("5/6^7%1+2-3*4").equals("567^/1%2+34*-"));
		assertTrue(Calculator.convertToPostFix("4*5/6^7%1+2-3").equals("45*67^/1%2+3-"));
		assertTrue(Calculator.convertToPostFix("3-4*5/6^7%1+2").equals("345*67^/1%-2+"));
		assertTrue(Calculator.convertToPostFix("2+3-4*5/6^7%1").equals("23+45*67^/1%-"));
		assertTrue(Calculator.convertToPostFix("1%2+3-4*5/6^7").equals("12%3+45*67^/-"));

		// etc.
	}
}

[zetologos]

I turn it into an linkedlist so that i can edit in the middle.

[tunlinaung]

Hi,
Have you already got answer for your problem? To produce the correct answer from your program, just need to change some of your coding like that:
- eval.remove(i);
- eval.remove(i-1);
- eval.remove(i-2);

instead of this coding:

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

Explanation:
Let => the values in Linkedlist be : [9, 10, 9, /, +]
=> the values of the variable 'i' be : 3
- eval.get(i-1) // will return 9
- eval.remove(eval.get(i-1)) // remove method will search the element 9 to remove
here, the error you said emerge. You see that there are two duplicate 9 in linkedlist. So, Remove method will only remove the first element 9 in index 0.
Remove method will not remove the second element 9 in index 2 which is you want to delete. Remove method starts searching at index 0. As soon as the element to remove found, this method stop searching and delete this element from linkedlist.That is why your program finally produce the incorrect answer.

I hope to be okay and your bright future ............