# arithmetische Ausdrücke prüfen



## sh (11. Jul 2011)

> In einer fiktiven Programmiersprache gibt es arithmetische Ausdrücke wie in der Mathematik, z.B. 2 + 3. Zur Vereinfachung gibt es nur „Fully Parenthesized Expressions“ (FPE), d.h. dass jeder Operator mit seinen beiden Operanden geklammert ist. Priorität und Assoziativität sind hier irrelevant. Numerale sind zur Vereinfachung nur einzelne Dezimalziffern ohne Vorzeichen.
> Korrekte FPEs sind z.B. (2 + ( 3 * 4)) oder ((2 + 3 ) * 4)
> Unzulässige FPEs wären: 2 + 3 * 5 oder (2+ ) * 5 oder )(
> Ihre Aufgabe ist es, einen als String gegebenen Ausdruck auf syntaktische Korrektheit hin zu untersuchen, d.h. Sie müssen zuerst überprüfen, ob die Klammern im String korrekt geschachtelt sind. Ihre Methode liefert entsprechend true oder false.



Auf den ersten Blick sieht das garnicht so schwer aus, aber wenn man sichs dann mal genauer überlegt.. Um 100%ige Korrektheit zu überprüfen muss man schon einiges beachten. Zunächst hab ich gedacht "Regexp und gut is!" aber stellt sich heraus das ein Regex für so eine Syntax überprüfung garnicht so leicht ist.

Also gehn wirs mal langsam an, hier meine erste Methode:

```
public boolean isBalanced(String fpe) {
		char[] chars = fpe.toCharArray();
		int opened = 0, closed = 0;
		for(char c : chars) {
			if(c == '(')
				opened++;
			if(c == ')')
				closed++;
		}
		return opened > 0 && opened == closed;
	}
```
Was die macht is klar, einfach nur sehen ob genau so viele offene Klammern '(' wie geschlossene Klammern ')' in der FPE sind. Auch muss mindestens eine Klammer offen (dh. auch geschlossen) sein, da '5 + 2' keine FPE ist.

Nur wie überprüfe ich die restliche syntaktische Korrektheit?
Nach jeder offenen Klammer muss ja entweder eine Zahl mit Operator oder eben eine neue FPE kommen. 

Jede Hilfe für (möglichst) schlaue Lösungsansätze ist willkommen!

MfG

EDIT:
Ich vermute stark das die Aufgabe auf eine Rekursion hinausläuft.


----------



## Ariol (11. Jul 2011)

Deine Methode ist leider falsch:


```
public boolean isBalanced(String fpe) {
				
		//Alle Leerzeichen aus fpe entfernen
		char[] chars = fpe.toCharArray();
		int opened = 0;
		boolean isFPE = false;
		char previousChar=' ';
		for(char c : chars) {
			if(c == '(') {
				//PseudoCode:
				if(prevoiusChar.isNumber) //"3(" ???
					return false;		
				isFPE=true;
				opened++;
			}
			else if(c == ')')
			{
				//PseudoCode:
				if(prevoiusChar.isOperator)
					return false; // "+)" ???
				opened--;
			}
			else
			{
				//PseudoCode:
				if(prevoiusChar.isOperator && c.isOperator) // "++"???
					return false;	
				//etc....
			}				
			previousChar=c;

			if(opened<0) {
				return false; //Schließende Klammer vor öffnender Klammer
			}
		}
		return isFPE && opened != 0; //Alle Klammern geschlossen
	}
```


----------



## diggaa1984 (11. Jul 2011)

allerdings deine methode auch, denn so wäre ein ausdruck wie: 5+2 auch gültig, ist er aber laut aufgabenstellung nich


----------



## Ariol (11. Jul 2011)

diggaa1984 hat gesagt.:


> allerdings deine methode auch, denn so wäre ein ausdruck wie: 5+2 auch gültig, ist er aber laut aufgabenstellung nich



Hatte ich schon gemerkt und war grad am editieren


----------



## sh (11. Jul 2011)

Mhh ich denke nicht das meine isBalanced() falsch ist, die Methode ansich soll ja nur sehen ob es
a) exakt soviele '(' wie ')' gibt und
b) mindestens eine '(' bzw ')' gibt

Deine Methode macht doch eigentlich das gleiche, nur das du die "Klammerntiefe" bei '(' hochzählst und bei ')' runterzählst.

Hab gerade beide getestet und sehe da keinen Unterschied. Das eigentliche Problem, ob die Klammern (Ausdrücke) korrekt geschachtelt sind muss man natürlich anders lösen (ich vermute mit einer Rekursion).

EDIT:
Grade geposted da hast du editiert


----------



## diggaa1984 (11. Jul 2011)

aber warum ist seine denn falsch!?


----------



## Ariol (11. Jul 2011)

diggaa1984 hat gesagt.:


> aber warum ist seine denn falsch!?



Weil seine auch bei 
	
	
	
	





```
)))((()((())
```
 true zurückliefern würde.


----------



## Blakh (11. Jul 2011)

```
return isFPE && opened != 0; //Alle Klammern geschlossen
```

Muss das nicht  opened == 0 sein?


----------



## diggaa1984 (11. Jul 2011)

Ariol hat gesagt.:


> Weil seine auch bei
> 
> 
> 
> ...



das isn argument


----------



## sh (11. Jul 2011)

Ariol hat gesagt.:


> Weil seine auch bei
> 
> 
> 
> ...



Ja aber das macht bei isBalanced() nichts. Die soll erstmal nur die Anzahl der Klammern prüfen, nicht ob sie korrekt geschachtelt sind.


----------



## pexx (11. Jul 2011)

@sh: die aufgabe hatte ich auch mal so ähnlich. eine einfache lösung war die indizes der öffnenden (_is_) und schließenden klammern (_ie_) zu suchen. wenn weder _is_ noch _ie_ da sind, balanced. wenn nur einer der indizes existiert, unbalanced. wenn beide indizes existieren, rekursion mit dem substring von _is+1_ bis _ie_ . 

die methode prüft natuerlich nur die klammern, nicht jedoch die operatoren oder operanden.

EDIT: habs gefunden


```
public static boolean isBalanced (String t) {
		
		int s = t.indexOf('('); 
		int e = t.lastIndexOf(')');
		
		if ((s == -1) && (e == -1))
			return true;
		else if ((s == -1) || (e == -1) || (s >= e))
			return false;
		else
			return isBalanced(t.substring(s+1, e));	
	}
```


----------



## sh (11. Jul 2011)

Ich denke ich weiss nun wie es geht. In der Teilaufgabe c) (ja die habe ich euch verschwiegen, hab ich grad aus den Tiefen meines Ordners hervorgekramt) ist eine Zustandstabelle. Einfach dumm nach der Tabelle programmieren sollte klappen. Mein zweiter Lösungsansatz war eh schon relativ ähnlich.


```
package aufgabe1;

public class FPE {
	
	public static void main(String... args) {
	
		
	}
	
	private enum State {
		OpenBracket, Digit, Operator, CloseBracket, Eof, Undefined
	}
	
	private boolean isCorrectSyntax(String fpe) {
		CHECK check = new CHECK(fpe);
		//...... do the check stuff here
	}
	
	private static class CHECK {
		private char[] fpe;
		private int pos;
		
		public CHECK(String fpe) {
			this.fpe = fpe.toCharArray();
			pos = -1;
		}
		
		public State nextState() {
			pos++;
			if(fpe.length - 1 < pos)
				return State.Eof;
			if(fpe[pos] == ' ')
				return nextState();
			if(fpe[pos] == '(')
				return State.OpenBracket;
			if(fpe[pos] == ')')
				return State.CloseBracket;
			if(Character.isDigit(fpe[pos]))
				return State.Digit;
			if(fpe[pos] == '+' || fpe[pos] == '*')
				return State.Operator;
			return State.Undefined;
		}
		
	}
	

	
}
```

Das Mal grob wie ichs angegangen bin, hier noch wie der Automat dazu aussieht:






EDIT:
Okay, ich komm mit der Zustandstabelle schon nicht klar. Wieso kann im Zustand "Plain" ein Operator kommen (1. Zeile, letzte Spalte).
Also im Zustand "Plain" wird eine OpenBracket erkannt. Ist noch nachvollziehbar, das erste Zeichen muss ja '(' sein. Nur wieso geht man, wenn im Zustand "Plain" ein Operator kommt dann zu Numeral1?
Ich mein, dann wär ja zB. ein + oder * am ANFANG der FPE?
Bzw. weiß jemand wie das Ding korrekt auszufüllen ist?

EDIT2:
Stimmt das so?





EDIT3:
Hier mal meine Lösung nach obiger Zustandstabelle, könnte mir bitte jemand sagen ob das so richtig ist?

```
package aufgabe1;

public class FPESyntax {
	
	public static void main(String... args) {
		
		String fpe = "((1+2)*(3+4))";
		System.out.println(isCorrectSyntax(fpe));
		
	}
	
	private static boolean isCorrectSyntax(String fpe) {
		
		//eventuell noch whitespaces strippen
		char[] chars = fpe.toCharArray();
		
		int depth = 0;
		
		State state = State.Plain;
		
		for(int i = 0; i < chars.length; i++) {
			if(state == State.Plain) {
				if(chars[i] == '(') {
					depth++;
					state = State.OpenBracket;
				} 
				else if(chars[i] == '+' || chars[i] == '*') {
					state = State.Numeral1;
				}
				else if(chars[i] == ')' || Character.isDigit(chars[i])) {
					return false;
				}
			}
			else if(state == State.OpenBracket) {
				if(isOpenBracket(chars[i])) {
					depth++;
					state = State.OpenBracket;
				}
				else if(isClosedBracket(chars[i])) {
					return false;
				}
				else if(isDigit(chars[i])) {
					state = State.Numeral1;
				}
				else if(isOperator(chars[i])) {
					return false;
				}	
			} 
			else if(state == State.Numeral1) {
				if(isOpenBracket(chars[i]) || isClosedBracket(chars[i]) || isDigit(chars[i])) {
					return false;
				}
				else if(isOperator(chars[i])) {
					state = State.Operator;
				}
			}
			else if(state == State.Numeral2) {
				if(isOpenBracket(chars[i]) || isDigit(chars[i]) || isOperator(chars[i])) {
					return false;
				}
				else if(isClosedBracket(chars[i])) {
					depth--;
					state = State.CloseBracket;
				}
			}
			else if(state == State.Operator) {
				if(isOpenBracket(chars[i])) {
					depth++;
					state = State.OpenBracket;
				}
				else if(isClosedBracket(chars[i]) || isOperator(chars[i])) {
					return false;
				}
				else if(isDigit(chars[i])) {
					state = State.Numeral2;
				}
			}
			else if(state == State.CloseBracket) {
				if(isOpenBracket(chars[i]) || isDigit(chars[i])) {
					return false;
				}
				else if(isClosedBracket(chars[i])) {
					depth--;
					state = State.CloseBracket;
				}
				else if(isOperator(chars[i])) {
					state = State.Plain;
				}
			}
		}
		
		if(!isBalanced(fpe))
			return false;
		
		return true;
	}
	
	public static boolean isDigit(char c) {
		return Character.isDigit(c) == true;
	}
	
	public static boolean isOperator(char c) {
		return c == '+' || c == '*';
	}
	
	public static boolean isOpenBracket(char c) {
		return c == '(';
	}
	
	public static boolean isClosedBracket(char c) {
		return c == ')';
	}
	
	public static boolean isBalanced(String fpe) {
		char[] chars = fpe.toCharArray();
		int opened = 0, closed = 0;
		for(char c : chars) {
			if(c == '(')
				opened++;
			if(c == ')')
				closed++;
		}
		return opened > 0 && opened == closed;
	}

	public enum State {
		Plain, OpenBracket, Numeral1, Numeral2, Operator, CloseBracket
	}
	
}
```
Was ich nach wievor nicht verstehe ist der Zustand "Plain", wieso da ein Operator kommen darf. Ist mit "Plain" ein whitespace-char gemeint?
EDIT-AGAIN(!):
Scheinbar nicht, das Programm funktioniert auch mit whitespaces im FPE, auch wenn man diese nicht strippt. Ich gehe mal davon aus das diese Lösung korrekt ist, wenn jemand noch Anmerkungen hat das ich was falsch gemacht habe, bitte bescheid geben!

In der Aufgabe heißt es ja auch:
*Achtung: der Automat erkennt nicht alle Ausdrücke richtig. Er gnügt aber für Ausdrücke der Form
((1+2) * (3+4))*

Daraus schließe ich mal das mein Programm trotz Akzeptanz von zB "((1+2) * (3+4))-" dennoch richtig ist.


----------

