Stack basierter Rechner

[christopher_gies]

Hallo,
habe ein Problem bei der realisierung eines Stack basierten Rechners.
Allerdings ist mein Projekt mittlerweile schon ein bissl komplexe.
Und zwar funktioniert die interne Abarbeitung einer bestimmten Funktion noch nicht!
Diese ist in der Klasse StackCalculator und zwar die Methode public double calculate (String formula).
Hat jemand Erfahrung mit sowas und kann mir eventuell weiterhelfen?
Mir geht es nur um die Implementierung dieser Methode.
Andere Aspekte, z.B. wie der String übergeben wird, sind fest vorgeschrieben.
Es handelt sich hierbei um eine Programmieraufgabe im Studium.
Manche Formeln funktionieren auch schon bzw. können berechnet werden.
Nun hänge ich aber bei dieser Formel, die einfach nicht korrekt von meinem Programm durchlaufen wird: 8+12-14*1+103

Ich poste mal die 3 Klassen und hoffe das mir jemand weiterhelfen kann!
Wie gesagt der Fehler muss im der dritten gepostet Klasse zwischen Zeile 62 und 97 liegen! Es liegt kein syntaktisches sondern ein logisches Problem vor!

Danke schon mal im Voraus
Mit freundlichen Grüßen
Christopher Gies

package de.hsfulda.dua.stackcalculator;

import java.util.ArrayList;
import java.util.EmptyStackException;

public abstract class AbstractArrayListStack<E> {
	/**
	 * ArrayList used to implement the stack.
	 */
	protected ArrayList<E> arrayList;

	/**
	 * Index of the top element of the stack in the ArrayList.
	 */
	protected int top = -1;

	/**
	 * Initializes the stack to use an ArrayList of default capacity.
	 */
	public AbstractArrayListStack() {
		arrayList = new ArrayList<E>(1000);
	}

	/**
	 * Returns the number of elements in the stack. This method runs in O(1)
	 * time.
	 * 
	 * @return number of elements in the stack.
	 */
	public abstract int size();

	/**
	 * Tests whether the stack is empty. This method runs in O(1) time.
	 * 
	 * @return true if the stack is empty, false otherwise.
	 */
	public abstract boolean isEmpty();

	/**
	 * Inserts an element at the top of the stack. This method runs in O(1)
	 * time.
	 * 
	 * @param element
	 *            to be inserted.
	 */
	public abstract void push(E element);

	/**
	 * Inspects the element at the top of the stack. This method runs in O(1)
	 * time.
	 * 
	 * @return top element in the stack.
	 * @exception EmptyStackException
	 *                if the stack is empty.
	 */
	public abstract E top() throws EmptyStackException;

	/**
	 * Removes the top element from the stack. This method runs in O(1) time.
	 * 
	 * @return element removed.
	 * @exception EmptyStackException
	 *                if the stack is empty.
	 */
	public abstract E pop() throws EmptyStackException;

}

package de.hsfulda.dua.stackcalculator;

import java.util.EmptyStackException;

/**
 * Implementation of the stack ADT using an ArrayList.
 */

/* 
 * Add your personal information here.
 * Missing or incorrect information will lead to the ignoring of this solution. 
 */
@Author(name = "Gies", 
		vorname = "Christopher",
        matrikelNr = "529685", 
        mailAddress = "christopher.gies@googlemail.com")

public class ArrayListStack<E> extends AbstractArrayListStack<E>
{

	@Override
	public int size()
	{
		return arrayList.size();
	}

	@Override
	public boolean isEmpty()
	{
		if(arrayList.size()==0)
			return true;
		else
			return false;
	}

	@Override
	public void push(E element)
	{
		arrayList.add(element);	
		top++;
	}

	@Override
	public E top() throws EmptyStackException
	{
		if(arrayList.size() == 0)
			throw new EmptyStackException();
		else
			return arrayList.get(arrayList.size() - 1);
	}

	@Override
	public E pop() throws EmptyStackException
	{
		if(arrayList.size() == 0)
			throw new EmptyStackException();
		else{
			E temp = arrayList.get(arrayList.size() - 1);
			arrayList.remove(arrayList.size() - 1);
			top--;
			return temp;	
		}
	}

}

package de.hsfulda.dua.stackcalculator;

import java.util.ArrayList;
import java.util.HashMap;

/**
 * Umsetzung eines Taschenrechners mit zwei Stacks.
 * Es werden die vier Grundrechenarten unterstützt.
 */

/*
 * Add your personal information here. Missing or incorrect information
 * will lead to the ignoring of this solution.
 */
@Author(name = "Gies", 
		vorname = "Christopher",
        matrikelNr = "529685", 
        mailAddress = "christopher.gies@googlemail.com")

public class StackCalculator
{
	HashMap<String,Integer> priority;
	private ArrayListStack<Double> operanden;
	private ArrayListStack<String> operatoren;
	ArrayList<String> strFormula;
	int index;

	public StackCalculator()
	{
		priority = new HashMap<String,Integer>();
		priority.put("+", 0);
		priority.put("-", 0);
		priority.put("*", 1);
		priority.put("/", 1);
		operanden = new ArrayListStack<Double>();
		operatoren = new ArrayListStack<String>();
	}

	/**
	 * Berechnung der übergebenen Formel
	 * 
	 * @param formula	Formel als String
	 * @return Ergebnis der Formel
	 */
	public double calculate (String formula)
	{
//		System.out.println(operanden.size());
//		System.out.println(operatoren.size());
		System.out.println("Zu Berechnende Formel: " + formula);
		strFormula = stringFormat(formula);
//		System.out.println(strFormula.size());

		operanden.push(Double.parseDouble(strFormula.get(0)));
		operatoren.push(strFormula.get(1));
		operanden.push(Double.parseDouble(strFormula.get(2)));
		index = 2;

		do
		{
			System.out.println("Oberstes Element im OperandenStack: " + operanden.top());
			System.out.println("Elemente im OperandenStack: " + operanden.size());
			System.out.println("Oberstes Element im OperatorenStack: " + operatoren.top());
			System.out.println("Elemente im OperatorenStack: " + operatoren.size());

			if(hasNext())
			{
				if(checkPriority(nextOperator()))
				{
					while(operatoren.size() > 0)
					{
						operanden.push(calculateOneOperation(operanden.pop(), operatoren.pop(), operanden.pop()));
					}
					pushNext();
				}
				else
					pushNext();
			}else
			{
				//operanden.push(calculateOneOperation(operanden.pop(), operatoren.pop(), operanden.pop()));
			}
			if(!hasNext())
				while(operatoren.size() > 0)
				{
					operanden.push(calculateOneOperation(operanden.pop(), operatoren.pop(), operanden.pop()));
					System.out.println(operatoren.size());
				}
		}while(hasNext());

//		System.out.println("Elemente im OperandenStack: " + operanden.size());
//		System.out.println("Elemente im OperatorenStack: " + operatoren.size());
		System.out.println("Ergebnis: " + operanden.top());
		return operanden.pop();
	}

	public boolean checkPriority(String operator)
	{
		System.out.println(operator);
		System.out.println(operatoren.top());

		if(priority.get(operator) <= priority.get(operatoren.top()))
			return true;
		else
			return false;
	}

	public String nextOperator()
	{
//		System.out.println(strFormula.get(index + 1));
		return strFormula.get(index + 1);
	}

	public void pushNext()
	{
		index++;
		operatoren.push(strFormula.get(index));
		index++;
		operanden.push(Double.parseDouble(strFormula.get(index)));
	}

	public boolean hasNext()
	{
//		System.out.println(strFormula.size());
//		System.out.println(index);

		if(strFormula.size() > index + 1)
			return true;
		else
			return false;
	}

	public double calculateOneOperation(double operand1, String operator, double operand2) throws IllegalArgumentException
	{
		if(operator.equals("+"))
		{
			double result = operand2 + operand1;
//			System.out.println(result);
			return result;
		}
		else if(operator.equals("-"))
		{
			double result = operand2 - operand1;
//			System.out.println(result);
			return result;
		}
		else if(operator.equals("*"))
		{
			double result = operand2 * operand1;
//			System.out.println(result);
			return result;
		}
		else if(operator.equals("/"))
		{
			double result = operand2 / operand1;
//			System.out.println(result);
			return result;
		}
		else
			throw new IllegalArgumentException("Es wurde bei der Berechnung einer Operation ein nicht erlaubter Operator gefunden!");
	}

	public ArrayList<String> stringFormat(String formula)
	{
		ArrayList<String> liste = new ArrayList<String>();
		ArrayList<Character> buffer = new ArrayList<Character>(); 
		String[] stringBuffer;

		/* bereitet String vor indem alle Leerzeichen entfernt werden wenn welche vorhanden sind */
		formula = formula.replaceAll(" ", "");

		/* Schreibt jeden Buchstaben des Strings an eine Positions der ArrayList */
		for(int i = 0; i < (formula.length()); i++)
		{
			buffer.add(formula.charAt(i));
		}

		/* fügt Leerzeichen vor und nach allen Operatoren ein */
		for(int i = 0; i < (buffer.size()); i++)
		{
			if(buffer.get(i) == '+' || buffer.get(i) == '-' || buffer.get(i) == '*' || buffer.get(i) == '/')
			{
                buffer.add(i, ' ');
                buffer.add(i + 2, ' ');
                i++;
			}
		}

		formula = "";

		/* konvertiert ArrayList wieder in einen String */
		for(char letter : buffer)
		{
			formula += letter;
		}

		stringBuffer = formula.split(" ");

		for(String str : stringBuffer)
		{
			liste.add(str);
//			System.out.println(str);
		}
		return liste;
	}

	public static void main (String[] args)
	{
		StackCalculator test1 = new StackCalculator();
//		test1.calculateOneOperation(1,"+",2);
		String helfer= "8+12-14*1+103";
//		String helfer= "12+4";
//		String helfer1= "12-4";
//		test1.stringFormat(helfer);
		test1.calculate(helfer);
//		test1.calculate(helfer1);
	}

}

[CStoll]

Das nenne ich aber eine sehr genaue Fehlerbeschreibung. Der genannte Bereich ist die Hauptschleife des gesamten Programms - und dein Problem liegt vermutlich schon vor der Stelle beim Füllen des Stack.

[christopher_gies]

Entschuldigung habe eine falsche Formel gepostet die eben genannte funktioniert noch!
Diese hier schlägt fehl: 8+12+14*1*103 also schlägt fehl im Sinne von falsches Ergebniss.
Wie gesagt syntaktisch ist alle i.O.

Das Problem liegt darin das er wenn er in den Teil (ab Zeile 74):

while(operatoren.size() > 0)
                    {
                        operanden.push(calculateOneOperation(operanden.pop(), operatoren.pop(), operanden.pop()));
                    }
                    pushNext();

springt bei dieser Formel nicht prüft ob im Rest der noch abzuarbeiten Formel ein von der Präzedenz her noch höherer Operator vorkommt.
Und er einfach den restlichen Stack abarbeitet!
Das Problem tritt erst nach der ersten Multiplikation in der Formel auf, er müsste dann eigentlich erst noch die zweite Multiplikation ausführen, führt aber stattdessen die restlichen untergeordneten additionen aus.
Ich weiß allerdings nicht wie ich das realisieren soll!
K.A. vlt. liegt es auch einfach daran weil ich schon zu lange dran sitze!
Aber ein Tipp währe schon echt hilfreich. Sehe die Lösung des Problems nicht wirklich!

Danke schon mal im Voraus!

[christopher_gies]

So konnte das Problem lösen. Hier der komplette richtig funktionierende Code:

package de.hsfulda.dua.stackcalculator;

import java.util.ArrayList;
import java.util.HashMap;

/**
 * Umsetzung eines Taschenrechners mit zwei Stacks.
 * Es werden die vier Grundrechenarten unterstützt.
 */

/*
 * Add your personal information here. Missing or incorrect information
 * will lead to the ignoring of this solution.
 */
@Author(name = "Gies", 
		vorname = "Christopher",
        matrikelNr = "529685", 
        mailAddress = "christopher.gies@googlemail.com")

public class StackCalculator
{
	HashMap<String,Integer> priority;
	private ArrayListStack<Double> operanden;
	private ArrayListStack<String> operatoren;
	ArrayList<String> strFormula;
	int index;

	/**
	 * versetzt den StackCalculator in einen gültigen Ausgangszustand
	 */
	public StackCalculator()
	{
		priority = new HashMap<String,Integer>();
		priority.put("+", 0);
		priority.put("-", 0);
		priority.put("*", 1);
		priority.put("/", 1);
		operanden = new ArrayListStack<Double>();
		operatoren = new ArrayListStack<String>();
	}

	/**
	 * Berechnung der übergebenen Formel
	 * 
	 * @param formula	Formel als String
	 * @return double 	Ergebnis der Formel
	 */
	public double calculate (String formula)
	{
//		System.out.println(operanden.size());
//		System.out.println(operatoren.size());
		System.out.println("Zu Berechnende Formel: " + formula);
		strFormula = formatString(formula);
//		System.out.println(strFormula.size());
//		System.out.println("---" + strFormula.get(0) + "---");
//		System.out.println("---" + strFormula.get(1) + "---");

		/*  fängt den Fehler ab, der entsteht wenn die Methode stringFormat mit nur einem Operator aufgerufen wird:
		 *  Die Methode liefert dann eine ArrayList mit size=2, an index 0 hält die ArrayList einen leeren String
		 *  und erst an index 1 steht der String der den Operator enthält. Der Fehler liegt denke ich an der internen
		 *  Verarbeitung der split Methode in formatString.
		 *  Außerdem werden die ungewollten Eingaben abgefangen, wenn dem Programm z.B. ein String mit nur einem Operator, 
		 *  einem Operanden, einem Leerzeichen oder ein komplett leerer String übergeben wird.*/
		if(strFormula.size() == 2 )
		{
			strFormula.remove(0);
			if(priority.containsKey(strFormula.get(0)))
				System.out.println("Ergebnis: 0");
				return 0;		
		}else if(strFormula.size() == 1)
		{
			if(strFormula.get(0) == "" || strFormula.get(0) == " ")
			{
				System.out.println("Ergebnis: 0");
				return 0;
			}
			else{
				System.out.println("Ergebnis: " + Double.parseDouble(strFormula.get(0)));
				return Double.parseDouble(strFormula.get(0));
			}
		}

		/* pushed die ersten 3 Elemente der Gleichung in die entsprechenden Stacks */
		operanden.push(Double.parseDouble(strFormula.get(0)));
		operatoren.push(strFormula.get(1));
		operanden.push(Double.parseDouble(strFormula.get(2)));
		index = 2;

		/* Schleifen- bzw. Abfragenkonstrukt, dass über die interne Stackabarbeitung und die Entscheidung,
		 * sind noch Elemente zu berechnen und in welcher Reihenfolge verfügt.*/
		do
		{
//			System.out.println("Oberstes Element im OperandenStack: " + operanden.top());
//			System.out.println("Elemente im OperandenStack: " + operanden.size());
//			System.out.println("Oberstes Element im OperatorenStack: " + operatoren.top());
//			System.out.println("Elemente im OperatorenStack: " + operatoren.size());

			while(operatoren.size() > 0 && hasNext() && checkPriority(nextOperator()))
			{
				operanden.push(calculateOneOperation(operanden.pop(), operatoren.pop(), operanden.pop()));
			}
			if(hasNext())
				pushNext();

		}while(hasNext());

		while(operatoren.size() > 0)
		{
			operanden.push(calculateOneOperation(operanden.pop(), operatoren.pop(), operanden.pop()));
//			System.out.println(operatoren.size());
		}

//		System.out.println("Elemente im OperandenStack: " + operanden.size());
//		System.out.println("Elemente im OperatorenStack: " + operatoren.size());
		System.out.println("Ergebnis: " + operanden.top());
		return operanden.pop();
	}

	/**
	 * prüft die Präzedenz zweier Operatoren 
	 * @param String operator nächster zu prüfender Operator
	 * @return boolean true wenn die Präzedenz des Operators im Stack höher ist als die des Vergleichsoperators
	 * */
	public boolean checkPriority(String operator)
	{
//		System.out.println(operator);
//		System.out.println(operatoren.top());

		if(priority.get(operator) <= priority.get(operatoren.top()))
			return true;
		else
			return false;
	}

	/**
	 * Gibt den nächsten Operatoren im String zurück
	 * @return String nächster Operator im String
	 */
	public String nextOperator()
	{
//		System.out.println(strFormula.get(index + 1));
		return strFormula.get(index + 1);
	}

	/**
	 * pushed den nächsten Operator und den nächsten Operanden in die entsprechenden Stacks
	 */
	public void pushNext()
	{
		index++;
		operatoren.push(strFormula.get(index));
		index++;
		operanden.push(Double.parseDouble(strFormula.get(index)));
	}

	/**
	 * prüft ob noch weiter Elemente im String abzuarbeiten sind
	 * @return boolean true wenn noch ein Element abzuarbeiten
	 */
	public boolean hasNext()
	{
//		System.out.println(strFormula.size());
//		System.out.println(index);

		if(strFormula.size() > index + 1)
			return true;
		else
			return false;
	}

	/**
	 * Führt die Berechnung einer Operation bestehend aus 2 Operanden und einem Operator durch
	 * @param operand1
	 * @param operator
	 * @param operand2
	 * @return double Ergebnis der Berechnung
	 * @throws IllegalArgumentException
	 */
	public double calculateOneOperation(double operand1, String operator, double operand2) throws IllegalArgumentException
	{
		if(operator.equals("+"))
		{
			double result = operand2 + operand1;
//			System.out.println(result);
			return result;
		}
		else if(operator.equals("-"))
		{
			double result = operand2 - operand1;
//			System.out.println(result);
			return result;
		}
		else if(operator.equals("*"))
		{
			double result = operand2 * operand1;
//			System.out.println(result);
			return result;
		}
		else if(operator.equals("/"))
		{
			double result = operand2 / operand1;
//			System.out.println(result);
			return result;
		}
		else
			throw new IllegalArgumentException("Es wurde bei der Berechnung einer Operation ein nicht erlaubter Operator gefunden!");
	}

	/**
	 * Formatiert den übergebenen String und bereitet ihn damit für die Abarbeitung in der Methode calculate vor.
	 * @param String formula zu formatierender String
	 * @return ArrayList<String> die die Operatoren und Operanden der Gleichung in entsprechender Reihenfolge hält.
	 */
	public ArrayList<String> formatString(String formula)
	{
		ArrayList<String> liste = new ArrayList<String>();
		ArrayList<Character> buffer = new ArrayList<Character>(); 
		String[] stringBuffer;

		/* bereitet String vor indem alle Leerzeichen entfernt werden wenn welche vorhanden sind */
		formula = formula.replaceAll(" ", "");

		/* Schreibt jeden Buchstaben des Strings an eine Positions der ArrayList */
		for(int i = 0; i < (formula.length()); i++)
		{
			buffer.add(formula.charAt(i));
		}

		/* fügt Leerzeichen vor und nach allen Operatoren ein */
		for(int i = 0; i < (buffer.size()); i++)
		{
			if(buffer.get(i) == '+' || buffer.get(i) == '-' || buffer.get(i) == '*' || buffer.get(i) == '/')
			{
                buffer.add(i, ' ');
                buffer.add(i + 2, ' ');
                i++;
			}
		}

		formula = "";

		/* konvertiert ArrayList wieder in einen String */
		for(char letter : buffer)
		{
			formula += letter;
		}

		stringBuffer = formula.split(" ");

		for(String str : stringBuffer)
		{
			liste.add(str);
//			System.out.println(str);
		}
		return liste;
	}

	public static void main (String[] args)
	{
		StackCalculator test1 = new StackCalculator();
//		test1.calculateOneOperation(1,"+",2);
//		String helfer= "8+12-14*1*103";
		String helfer= " ";
//		String helfer1= "12-4";
//		test1.stringFormat(helfer);
		test1.calculate(helfer);
//		test1.calculate(helfer1);
	}

}