Java Calculator problems

Hi Everyone

My code is an implementation of the shunting yard algorithm - Shunting-yard algorithm - Wikipedia, the free encyclopedia to convert infix expressions to postfix. I then try and solve the equations and print out the answer.

I have also created my own stack class and arrayList class.

I do not see why the array I declare is not outputting correctly. I have got a file which will have equations such as:
49+62*61-36
4/64
(53+26)
0*72
21-85+75-85
90*76-50+67
46*89-15
34/83-38
20/76/14+92-15
5*10/3-1

in it. Having tried to read the file and pass it to my methods I am unable to obtain the answer just the last thing that was read in? any help will be much appreciated.

The code:
myStack class

Code :

---

 
import java.util.Iterator;
import java.util.NoSuchElementException;
 
public class myStack<Item> implements Iterable<Item> {
	private int N; // size of the stack
	private Node first; // top of stack
 
	private class Node {
		private Item item;
		private Node next;
	}
 
	/**
	 * Create an empty stack.
	 */
	public myStack() {
		first = null;
		N = 0;
		assert check();
	}
 
	public boolean isEmpty() {
		return first == null;
	}
 
	public int size() {
		return N;
	}
 
	public void push(Item item) {
		Node oldfirst = first;
		first = new Node();
		first.item = item;
		first.next = oldfirst;
		N++;
		assert check();
	}
 
	public Item pop() {
		if (isEmpty())
			throw new NoSuchElementException("Stack underflow");
		Item item = first.item; // save item to return
		first = first.next; // delete first node
		N--;
		assert check();
		return item; // return the saved item
	}
 
	public Item peek() {
		if (isEmpty())
			throw new NoSuchElementException("Stack underflow");
		return first.item;
	}
 
	public String toString() {
		StringBuilder s = new StringBuilder();
		for (Item item : this)
			s.append(item + " ");
		return s.toString();
	}
 
	// check internal invariants
	private boolean check() {
		if (N == 0) {
			if (first != null)
				return false;
		} else if (N == 1) {
			if (first == null)
				return false;
			if (first.next != null)
				return false;
		} else {
			if (first.next == null)
				return false;
		}
 
		// check internal consistency of instance variable N
		int numberOfNodes = 0;
		for (Node x = first; x != null; x = x.next) {
			numberOfNodes++;
		}
		if (numberOfNodes != N)
			return false;
 
		return true;
	}
 
	public Object[] toArray(String[] elementData) {
		return (Object[]) elementData.clone();
	}
 
	public Iterator<Item> iterator() {
		return new ListIterator();
	}
 
	// did not implement remove as it was not needed
	private class ListIterator implements Iterator<Item> {
		private Node current = first;
 
		public boolean hasNext() {
			return current != null;
		}
 
		public void remove() {
			throw new UnsupportedOperationException();
		}
 
		public Item next() {
			if (!hasNext())
				throw new NoSuchElementException();
			Item item = current.item;
			current = current.next;
			return item;
		}
	}
}

---

myArraylist

Code :

---

 
import java.util.Arrays;
 
public class myArrayList<Item> {
 
	private Object[] myStore;
	private int actSize = 0;
 
	public myArrayList() {
		myStore = new Object[100];
	}
 
	public Object get(int index) {
		if (index < actSize) {
			return myStore[index];
		} else {
			throw new ArrayIndexOutOfBoundsException();
		}
	}
 
	public void add(Object obj) {
		if (myStore.length - actSize <= 0) {
			increaseListSize();
		}
		myStore[actSize++] = obj;
	}
 
	public Object remove(int index) {
		if (index < actSize) {
			Object obj = myStore[index];
			myStore[index] = null;
			int tmp = index;
			while (tmp < actSize) {
				myStore[tmp] = myStore[tmp + 1];
				myStore[tmp + 1] = null;
				tmp++;
			}
			actSize--;
			return obj;
		} else {
			throw new ArrayIndexOutOfBoundsException();
		}
 
	}
 
	public int size() {
		return actSize;
	}
 
	private void increaseListSize() {
		myStore = Arrays.copyOf(myStore, myStore.length * 2);
	}
 
	@SuppressWarnings("unchecked")
	public <T> T[] toArray(T[] a) {
		if (a.length < size())
			// Make a new array of a's runtime type, but my contents:
			return (T[]) Arrays.copyOf(myStore, size(), a.getClass());
		System.arraycopy(myStore, 0, a, 0, size());
		if (a.length > size())
			a[size()] = null;
		return a;
	}
 
	// Positional Access Operations
 
	/*@SuppressWarnings("unchecked")
	E elementData(int index) {
		return (E) myStore[index];
	}*/
 
}

---

the test class where the shunting yard and RPN calculations should take place

Code :

---

 
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;
 
public class TestClass {
 
	private static final int LEFT_ASSOC = 0;
	private static final int RIGHT_ASSOC = 1;
	static String OPERATORS1 = "+-*/()";
 
	// Operators
	private static final Map<String, int[]> OPERATORS = new HashMap<String, int[]>();
	static {
		// Map<"token", []{precedence, associativity}>
		OPERATORS.put("+", new int[] { 0, LEFT_ASSOC });
		OPERATORS.put("-", new int[] { 0, LEFT_ASSOC });
		OPERATORS.put("*", new int[] { 5, LEFT_ASSOC });
		OPERATORS.put("/", new int[] { 5, LEFT_ASSOC });
		OPERATORS.put("(", new int[] {1, RIGHT_ASSOC});
		OPERATORS.put(")", new int[] {1, LEFT_ASSOC});
	}
 
	private static boolean isOperator(String token) {
		return OPERATORS.containsKey(token);
	}
 
	// Test associativity of operator token
	private static boolean isAssociative(String token, int type) {
		if (!isOperator(token)) {
			throw new IllegalArgumentException("Invalid token: " + token);
		}
 
		if (OPERATORS.get(token)[1] == type) {
			return true;
		}
		return false;
	}
 
	// Compare precedence of operators.
	private static final int cmpPrecedence(String token1, String token2) {
		if (!isOperator(token1) || !isOperator(token2)) {
			throw new IllegalArgumentException("Invalid tokens: " + token1
					+ " " + token2);
		}
		return OPERATORS.get(token1)[0] - OPERATORS.get(token2)[0];
	}
 
	public static String[] infixToRPN(String[] inputTokens) {
		myArrayList<String> out = new myArrayList<String>();
		myStack<String> stack = new myStack<String>();
		// For each token
		for (String token : inputTokens) {
			StringTokenizer tokens = new StringTokenizer(token,OPERATORS1,true);
			while (tokens.hasMoreTokens()) {
				token = tokens.nextToken();
 
			}
			// If token is an operator
			if (isOperator(token)) {
				// While stack not empty AND stack top element
				// is an operator
				while (!stack.isEmpty() && isOperator(stack.peek())) {
					if ((isAssociative(token, LEFT_ASSOC) && cmpPrecedence(
							token, stack.peek()) <= 0)
							|| (isAssociative(token, RIGHT_ASSOC) && cmpPrecedence(
									token, stack.peek()) < 0)) {
						out.add(stack.pop());
						continue;
					}
					break;
				}
				// Push the new operator on the stack
				stack.push(token);
			}
			// If token is a left bracket '('
			else if (token.equals("(")) {
				stack.push(token); 
			}
			// If token is a right bracket ')'
			else if (token.equals(")")) {
				while (!stack.isEmpty() && !stack.peek().equals("(")) {
					out.add(stack.pop());
				}
				stack.pop();
			}
			// If token is a number
			else {
				out.add(token);
			}
		}
		while (!stack.isEmpty()) {
			out.add(stack.pop());
		}
		String[] output = new String[out.size()];
		return out.toArray(output);
	}
 
	public static double RPNtoDouble(String[] tokens) {
		myStack<String> stack = new myStack<String>();
 
		// For each token
 
		for (String token : tokens) {
			System.out.println( "Working this token: " + token );
			// If the token is a value push it onto the stack
			if (!isOperator(token)) {
				stack.push(token);
			} else {
				// Token is an operator: pop top two entries
				Double d2 = Double.valueOf(stack.pop());
				Double d1 = Double.valueOf(stack.pop());
 
				// Get the result
				Double result = token.compareTo("+") == 0 ? d1 + d2 : token
						.compareTo("-") == 0 ? d1 - d2
								: token.compareTo("*") == 0 ? d1 * d2 : d1 / d2;
 
				// Push result onto stack
				stack.push(String.valueOf(result));
			}
		}
 
		return Double.valueOf(stack.pop());
	}
 
	static public void main(String[] args) throws IOException {
		File file = new File("testEquations.txt");
		String[] lines = new String[1];
 
		try {
			FileReader reader = new FileReader(file);
			@SuppressWarnings("resource")
			BufferedReader buffReader = new BufferedReader(reader);
			int x = 0;
			String s;
			while ((s = buffReader.readLine()) != null) {
				lines[x] = s;
				x++;
			}
		} catch (IOException e) {
			System.exit(0);
		}
		// test printing string array
		for (String s : lines) {
			System.out.println("" + s);
			String[] output =infixToRPN(lines);
			System.out.println(Arrays.toString(output));
		}
 
 
	}
 
}

---

Quote:

---

why the array I declare is not outputting correctly

---

Can you post what the program is outputting and also post what the output should be and explain what is wrong with the output?

Quote:

---

Originally Posted by Norm

Can you post what the program is outputting and also post what the output should be and explain what is wrong with the output?

---

Hi the program currently outputs:

49+62*61-36
[36]
36.0

whereas the program should be giving me

equation read in
49+62*61-36
array of equation in RPN format
[49+62*61-36]
answer to equation
3795

What's in the input file you are reading for testing the code?

Where does this part of the program's output come from: "equation read in"?
I don't see that String in the program. How can the program generate the output you posted if there isn't the String in the program?

Can you post EXACTLY what the output should be?

sorry I added the description so it was clear what they should be.

at the minute the input file contains only:
49+62*61-36

and the output should be
49+62*61-36
[49+62*61-36]
3795

Thanks

Looks like you need to do some debugging to see why the code is not doing what you want.
One way to debug code is to add lots of println statements that print out the values of variables that control the logic and hold values used in the program. If you can see what the computer sees when it executes the program you should see where the program is going wrong and where it needs to be changed. When you wrote the code, you had expectations for how the code should work. The print out will show you if the code is doing what you expected.

Quote:

---

Originally Posted by Norm

Looks like you need to do some debugging to see why the code is not doing what you want.
One way to debug code is to add lots of println statements that print out the values of variables that control the logic and hold values used in the program. If you can see what the computer sees when it executes the program you should see where the program is going wrong and where it needs to be changed. When you wrote the code, you had expectations for how the code should work. The print out will show you if the code is doing what you expected.

---

Hi

I have tried that and I am unable to find the reason for it just using the last token.

Basically what happens is when I call the RPNtoDouble function I was printing the token that was being "worked" and it was always the same.

Would I be better off changing the function to handle just a string and then find a way to do it line by line?

I am totally lost as to why it does not work

Quote:

---

unable to find the reason for it just using the last token.

---

Continue adding println statements that print out the values of the variables. For example print out the value of the variable: token in the infixToRPN() method. Print it out when it is first assigned a value and then again when it is used later in the method and again when it is added to the stack and arraylist.

Quote:

---

Originally Posted by Norm

Continue adding println statements that print out the values of the variables. For example print out the value of the variable: token in the infixToRPN() method. Print it out when it is first assigned a value and then again when it is used later in the method and again when it is added to the stack and arraylist.

---

Hi I managed to get it working for one equation by moving the end bracket of the while statement to line 101.

I am now getting the following error:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 1
at uk.ac.shef.dcs.com262.coa10pjh.TestClass.main(Test Class.java:146)

when trying to read in a file with multiple equations. How would I make this work for that file?

Code :

---

package uk.ac.shef.dcs.com262.coa10pjh;
 
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;
 
public class TestClass {
 
	private static final int LEFT_ASSOC = 0;
	private static final int RIGHT_ASSOC = 1;
	static String OPERATORS1 = "+-*/()";
 
	// Operators
	private static final Map<String, int[]> OPERATORS = new HashMap<String, int[]>();
	static {
		// Map<"token", []{precedence, associativity}>
		OPERATORS.put("+", new int[] { 0, LEFT_ASSOC });
		OPERATORS.put("-", new int[] { 0, LEFT_ASSOC });
		OPERATORS.put("*", new int[] { 5, LEFT_ASSOC });
		OPERATORS.put("/", new int[] { 5, LEFT_ASSOC });
		OPERATORS.put("(", new int[] {1, RIGHT_ASSOC});
		OPERATORS.put(")", new int[] {1, LEFT_ASSOC});
	}
 
	private static boolean isOperator(String token) {
		return OPERATORS.containsKey(token);
	}
 
	// Test associativity of operator token
	private static boolean isAssociative(String token, int type) {
		if (!isOperator(token)) {
			throw new IllegalArgumentException("Invalid token: " + token);
		}
 
		if (OPERATORS.get(token)[1] == type) {
			return true;
		}
		return false;
	}
 
	// Compare precedence of operators.
	private static final int cmpPrecedence(String token1, String token2) {
		if (!isOperator(token1) || !isOperator(token2)) {
			throw new IllegalArgumentException("Invalid tokens: " + token1
					+ " " + token2);
		}
		return OPERATORS.get(token1)[0] - OPERATORS.get(token2)[0];
	}
 
	public static String[] infixToRPN(String[] inputTokens) {
		myArrayList<String> out = new myArrayList<String>();
		myStack<String> stack = new myStack<String>();
		// For each token
		for (String token : inputTokens) {
			StringTokenizer tokens = new StringTokenizer(token,OPERATORS1,true);
			while (tokens.hasMoreTokens()) {
				token = tokens.nextToken();
 
 
				// If token is an operator
				if (isOperator(token)) {
					// While stack not empty AND stack top element
					// is an operator
					while (!stack.isEmpty() && isOperator(stack.peek())) {
						if ((isAssociative(token, LEFT_ASSOC) && cmpPrecedence(
								token, stack.peek()) <= 0)
								|| (isAssociative(token, RIGHT_ASSOC) && cmpPrecedence(
										token, stack.peek()) < 0)) {
							out.add(stack.pop());
							continue;
						}
						break;
					}
					// Push the new operator on the stack
					stack.push(token);
				}
				// If token is a left bracket '('
				else if (token.equals("(")) {
					stack.push(token); 
				}
				// If token is a right bracket ')'
				else if (token.equals(")")) {
					while (!stack.isEmpty() && !stack.peek().equals("(")) {
						out.add(stack.pop());
					}
					stack.pop();
				}
				// If token is a number
				else {
					out.add(token);
				}
 
				while (!stack.isEmpty()) {
					out.add(stack.pop());
				}
			}
		}
		String[] output = new String[out.size()];
		return out.toArray(output);
	}
 
	public static double RPNtoDouble(String[] tokens) {
		myStack<String> stack = new myStack<String>();
 
		// For each token
 
		for (String token : tokens) {
			//System.out.println( "Working this token: " + token );
			// If the token is a value push it onto the stack
			if (!isOperator(token)) {
				stack.push(token);
			} else {
				// Token is an operator: pop top two entries
				Double d2 = Double.valueOf(stack.pop());
				Double d1 = Double.valueOf(stack.pop());
 
				// Get the result
				Double result = token.compareTo("+") == 0 ? d1 + d2 : token
						.compareTo("-") == 0 ? d1 - d2
								: token.compareTo("*") == 0 ? d1 * d2 : d1 / d2;
 
				// Push result onto stack
				stack.push(String.valueOf(result));
			}
		}
 
		return Double.valueOf(stack.pop());
	}
 
	static public void main(String[] args) throws IOException {
		File file = new File("testEquations.txt");
		String[] lines = new String[1];
 
		try {
			FileReader reader = new FileReader(file);
			@SuppressWarnings("resource")
			BufferedReader buffReader = new BufferedReader(reader);
			int x = 0;
			String s;
			while ((s = buffReader.readLine()) != null) {
				lines[x] = s;
				x++;
			}
		} catch (IOException e) {
			System.exit(0);
		}
		// test printing string array
		for (String s : lines) {
			System.out.println("" + s);
			String[] output =infixToRPN(lines);
			System.out.println(RPNtoDouble(output));
 
		}
 
 
	}
 
}

---

Any help will be appreciated :)

Quote:

---

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 1
at uk.ac.shef.dcs.com262.coa10pjh.TestClass.main(Test Class.java:146)

---

At line 146 the code uses an index of 1 in an array with less than 2 elements.
Its probably the following array:

Code :

---

		String[] lines = new String[1];

---

Why is that array only given 1 element?

Quote:

---

Originally Posted by Norm

At line 146 the code uses an index of 1 in an array with less than 2 elements.
Its probably the following array:

Code :

---

		String[] lines = new String[1];

---

Why is that array only given 1 element?

---

Hi yeah I forgot to change it to 10.

I am now having the code give me the same answer for each equation the out put is:

Code :

---

49+62*61-36
 15.666666666666668 
4/64 
15.666666666666668 
(53+26) 
15.666666666666668 
0*72 
15.666666666666668 
21-85+75-85 
15.666666666666668 
90*76-50+67 
15.666666666666668 
46*89-15 
15.666666666666668 
34/83-38 
15.666666666666668 
20/76/14+92-15 
15.666666666666668 
5*10/3-1 
15.666666666666668

---

instead of:

Code :

---

49+62*61-36 
3795 
4/64 
0.0625 
(53+26) 
79 
0*72 
0 
21-85+75-85 
-74 
90*76-50+67 
6857 
46*89-15 
4079 
34/83-38 
-37.5903614458 
20/76/14+92-15 
77.0187969925 
5*10/3-1 
15.666666666666668

---

Is there a way for me to solve this?

thanks

--- Update ---

Also when I try and run it with the file given with a million expressions I get the following error:

Code :

---

2012-11-26 23:58:49.887 java[3570:9807] Unable to obtain JNIEnv for context: 0x0
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
	at java.lang.String.substring(String.java:1939)
	at java.util.StringTokenizer.nextToken(StringTokenizer.java:335)
	at uk.ac.shef.dcs.com262.coa10pjh.TestClass.infixToRPN(TestClass.java:59)
	at uk.ac.shef.dcs.com262.coa10pjh.TestClass.main(TestClass.java:152)

---

Is there any reason for this?

thanks

--- Update ---

Now resolved thanks to everyone for their help

Quote:

---

Is there a way for me to solve this?

---

The normal way to find problems in code is to debug it. Add lots of printlns to show what the code is doing and examine what is printed out. If you understand what the code is supposed to do, the print outs will show you what the code is doing so you can see where the program is going wrong.

Quote:

---

Now resolved thanks to everyone for their help

---

Please mark this thread as solved.