Summe von n vielen Summen berechnen

lima-city → Forum → Programmiersprachen → Programmieren mit .NET & Mono

Autor dieses Themas

computerkurs2011

computerkurs2011 hat kostenlosen Webspace.

0:19, 22.9.2016

Hallo liebes Forum,

das Summenzeichen Σ ist mit seinen Grenzen ähnlich wie eine for-Schleife in der Informatik. Also wollte ich das Summenzeichen in ein kleines C# Programm implementieren. Dies soll die letztendliche Summe nur ausformulieren, allerdings nicht ausrechnen. Nun soll aber nicht nur eine einfache Summe, sondern auch die Summe einer Summer oder eben beliebig tief die Summe von Summen ausgerechnet werden.

Also z.B. ∑_i^n∑_j^n∑_k^n…
Wobei das Programm das Summenzeichen als sum(i;n;Term) entgegennimmt.
Nun soll das Programm bspw. sum(0;4,i*sum(2;5;i)) als 0*(2+3+4+5)+1*(2+3+4+5)+2*(2+3+4+5)+3*(2+3+4+5)+4*(2+3+4+5) darstellen.
Eine Einfache Summe lässt sich so auch gut darstellen, aber die Summe von einer Summe nicht.
Meine Überlegung war, dass Summenzeichen auflösen in eine Funktion zu packen die sich selbst wiederaufruft, wenn sie im Term ein sum(i;n;Term) findet.
Leider klappt das alles noch nicht so wie es soll. Hat jemand von euch vllt. Anregungen?
Es kommt immer ein Stack overflows beim Durchlauf mit zwei oder mehr Summen, aber ich komme einfach nicht darauf, wo der Fehler liegt :wall:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Security.Cryptography;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;

namespace Summenzeichen
{
    class Summe
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Bitte geben Sie die auszuformulierende Summe an: \n\n");
            String eingabe = Console.ReadLine();
            String ausgabe = "";

            string[] param = getParams(eingabe);

            if (param[0] != "")
            {
                ausgabe = summe(param[2], Convert.ToInt32(param[0]), Convert.ToInt32(param[1]));
            }

            Console.WriteLine("Ergebnis: " + ausgabe);
            Console.ReadLine();

        }

       static private String summe(String value, int zaehler, int n)
        {
            string ausgabe = "";
            value = value.Replace(")", "");

            for (int i = zaehler; i <= n; i++)
            {
                ausgabe += value.Replace("i", i.ToString());

                if(searchSum(ausgabe) != "")
                {
                    ausgabe += searchSum(ausgabe);
                }



                if (i != n)
                {
                    ausgabe += " + ";
                }
            }

            return ausgabe;
        }

        static private String[] getParams(String value)
        {
            string[] ausgabe = { "", "", "" };
            StringBuilder sb = new StringBuilder(value);
            string searchForSum = "sum(";

            int firstCharacterSum = value.IndexOf(searchForSum);

            if (firstCharacterSum != -1)
            {
                sb = sb.Remove(0, firstCharacterSum + 4);
                ausgabe[0] =  sb.ToString().Split(';')[0];
                ausgabe[1] =  sb.ToString().Split(';')[1];
                int secondCharacterSum = sb.ToString().IndexOf(searchForSum);
                if (secondCharacterSum != -1)
                {
                    sb = sb.Remove(0, secondCharacterSum);
                    ausgabe[2] = sb.ToString();
                }
                else
                {
                    ausgabe[2] = sb.ToString().Split(';')[2];
                }
                
            }

            return ausgabe;
        }

       static private String searchSum(string value)
        {
            string[] param = getParams(value);

            if (param[0] != "")
            {
                return summe(param[2], Convert.ToInt32(param[0]), Convert.ToInt32(param[1]));
            }
            else { return ""; }
        }
    }
}

Beitrag zuletzt geändert: 22.9.2016 23:21:54 von computerkurs2011

Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!

lima-city: Gratis werbefreier Webspace für deine eigene Homepage
onlinevideorecorder

onlinevideorecorder hat kostenlosen Webspace.

17:15, 22.9.2016

Stack Overflow lässt vermuten, dass du dir irgendwie eine Endlosschleife eingebaut hast.
Autor dieses Themas
computerkurs2011

computerkurs2011 hat kostenlosen Webspace.

17:56, 22.9.2016
Was Stack Overflow heißt, dass weiß ich auch, nur ich weiß nicht wie bzw. warum dort eine Endlosschleife entsteht und wie ich es anders lösen soll. Daher meine Frage ans Forum nach Lösungsvorschlägen/-ansätzen.
hackyourlife

Moderator

hackyourlife hat kostenlosen Webspace.
20:39, 22.9.2016
Es sieht nach endloser Rekursion aus. Das entsteht, wenn du keine Abbruchbedingung hast, oder, wenn du in einem Rekursionsschritt keinen Fortschritt erzielst. Bei dir wird das wohl bei summe/searchSum eine falsche Abbruchbedingung sein.

Prüfen kannst du das alles mit assert-Befehlen, indem du entsprechende Bedingungen einfügst. In deinem Fall musst du dir eine Fortschrittsbedingung ausdenken, die eine Aussage darüber trifft, ob du einen derartigen Fortschritt machst, dass du je eine Abbruchbedingung erreichen kannst.

Deinen konkreten Beispielfall würde ich ja so lösen (ist Python-Code, weil ich kein C# kann):
```
def summe(start, end, f):
        return "+".join([ f(x) for x in range(start, end + 1) ])

result = summe(0, 4, lambda i: "%s*(%s)" % \
                (i, summe(2, 5, lambda x: str(x))))
print("result: '%s'" % result)
```
Das liefert folgendes Ergebnis, völlig ohne der Möglichkeit, jemals eine endlose Rekursion zu erzeugen:
result: '0*(2+3+4+5)+1*(2+3+4+5)+2*(2+3+4+5)+3*(2+3+4+5)+4*(2+3+4+5)'
Wenn du wirklich die Eingabe sinnvoll parsen und effizient verarbeiten willst, dann solltest du auch deine Parse-Funktionen vergessen und das anders lösen. Eine Möglichkeit wäre z.B. das Zerlegen der Eingabe in »Tokens«, die entweder ein Symbol wie »*« oder »+«, eine Zahl, ein Trennzeichen wie »;«, eine Klammer auf/zu (also »(« oder »)«) oder ein Name (z.B. »sum«) sind. Dann liest du im nächsten Schritt immer Token für Token, analysiert die Struktur, und erstellst einen Baum (Abstract Syntax Tree, kurz AST). Den kannst du dann mit sehr wenig Aufwand entweder direkt interpretieren (eher langsam), oder eine Art Bytecode erzeugen, die sich schneller ausführen lässt.

Ein einfacher Parser mit AST-Interpreter könnte beispielsweise so aussehen (in Java): Sums.java

Es wäre dabei übrigens einfacher, das Ergebnis direkt zu berechnen, anstatt das als Text auszugeben.
Autor dieses Themas
computerkurs2011

computerkurs2011 hat kostenlosen Webspace.
22:49, 22.9.2016
Da ich das Thema Grammatiken nur sehr kurz in der Schule hatte und das Studium erst in einem Monat los geht, verstehe ich zwar den Ansatz in welche Richtung deine Lösung geht, den Java Code verstehe ich aber nur teilweise auch wenn ich schon Erfahrungen mit Java habe.

Wenn ich das richtig verstehe hast du den Konstruktor von Token dreifach überladen und Token dient als „Behältnis“ für Operatoren oder nummerische Werte?

Der Context erschließt sich mir nicht so wirklich. Was Maps bzw. HashMaps sind weiß ich aber was der Context genau tut außer mit get einen Wert zwischen zu speichern und mit set wieder auszuliefern habe ich noch nicht rausgefunden.

Check() prüft ob es sich um den richtigen TokenType handelt, wenn mich nicht alles täuscht.

Scan() sucht nach Tokens mithilfe von next() ?

Frage: warum haben scan() und check() keinen return, sondern speichern den Wert in sym. Wird dieser nicht immer wieder überschrieben?

Error() erschließt sich von selbst.

Was expr und summand 100% machen erschließt sich mir nicht ganz durch das -1 im case in Zeile 180.

Und wie genau funktionieren deine Nodes?

Sorry für die vielen Nachfragen, aber jetzt interessiert mich dein Code doch sehr. Gerade weil er auch etwas behandelt, dass im Studium doch sehr wahrscheinlich auf mich zukommen wird und ich auch gerne lernen würde wie man Grammatiken bzw. syntaktische und semantische Informationen über Syntaxbäume analysieren kann.

MfG
cpk2011

P.S. Könnte ich die Ausgabe nicht am Ende, ganz böse, in ein eval packen und dann ausrechnen lassen?
```
public static void main(String[] args) throws Exception {
                String sums = new Sums().run("sum(i;0;4;i*sum(i;2;5;i*sum(i;7;8;i)))");
		System.out.println(sums);
                ScriptEngine engine = new ScriptEngineManager().getEngineByName("JavaScript");
                System.out.println("Ergebnis: "+engine.eval(sums));
	}
```
Beitrag zuletzt geändert: 22.9.2016 22:57:48 von computerkurs2011
hackyourlife

Moderator

hackyourlife hat kostenlosen Webspace.
12:41, 24.9.2016

computerkurs2011 schrieb:
Wenn ich das richtig verstehe hast du den Konstruktor von Token dreifach überladen und Token dient als „Behältnis“ für Operatoren oder nummerische Werte?
Ja. Ein
```
Token
```
enthält die nötige Information über genau einen Token. Der überladene Konstruktor ist dazu da, dass man die 3 Arten von Tokens ohne unnötigem Schreibaufwand erstellen kann: ein Token, das nur einen Typ hat (z.B. eine Klammer auf; erster Konstruktor), ein Token mit einem String-Wert (z.B. ein Name; zweiter Konstruktor) und ein Token mit einem Zahlenwert (z.B. eine Zahl; dritter Konstruktor). Dadurch kann man z.B.
```
Token t = new Token(TokenType.LPAR);
```
aber auch
```
Token t = new Token(TokenType.IDENT, "sum");
```
schreiben, ohne immer alle 3 Werte (Typ, String und Zahl) übergeben zu müssen.

Der Context erschließt sich mir nicht so wirklich. Was Maps bzw. HashMaps sind weiß ich aber was der Context genau tut außer mit get einen Wert zwischen zu speichern und mit set wieder auszuliefern habe ich noch nicht rausgefunden.
Die (Hash)Map speichert immer zu einem Schlüssel einen Wert. Jetzt kannst du aber verschachtelt mehrere Summenfunktionen aufrufen, und dabei die Index-Variable in jeder Ebene überschreiben. Der
```
Context
```
sucht deshalb immer zuerst in seinem eigenen Scope, und wenn er dort nichts findet, dann sucht er im übergeordneten Scope. Das ist nötig, damit z.B. das funktioniert:
```
sum(i; 0; 1; i * sum(i; 0; 1; i))
```
Das
```
i
```
hat dabei vor der zweiten
```
sum
```
den Wert des Indexes der ersten Summe, während es in der zweiten
```
sum
```
den Wert des Indexes der zweiten Summe hat.

Check() prüft ob es sich um den richtigen TokenType handelt, wenn mich nicht alles täuscht.
Korrekt, und zusätzlich ruft es
```
scan()
```
auf, um zum nächsten Token zu springen.

Scan() sucht nach Tokens mithilfe von next() ?
Mit
```
scan()
```
wird ein weiteres Token gelesen, und das zuletzt gelesene in der Variablen
```
t
```
, welche immer das zuletzt gelesene Token enthält, gespeichert.

Frage: warum haben scan() und check() keinen return, sondern speichern den Wert in sym. Wird dieser nicht immer wieder überschrieben?
Falls du genau schaust siehst du, dass
```
next()
```
ein Return in jedem Zweig hat.
```
scan()
```
hingegen hat kein Return, da es nur die Variablen der Klasse aktualisiert. Ein Return ist deshalb hier nicht nötig (was würdest du da denn überhaupt zurückgeben wollen?).
```
sym
```
wird in dieser Methode zwar jedes Mal überschrieben, aber da es eine Variable der Klasse ist, haben auch alle anderen Methoden darauf Zugriff. Auch hier: wenn du genau schaust, siehst du, dass andere Methoden den Wert von
```
sym
```
nutzen. Theoretisch könnte man sich den auch sparen, und jedes Mal
```
la.type
```
schreiben.

Was expr und summand 100% machen erschließt sich mir nicht ganz durch das -1 im case in Zeile 180.
Um das besser zu verstehen, solltest du dir wohl die EBNF deiner Syntax denken, dann wird das schnell klar:
```
EXPR := SUMMAND { ( "+" | "-" ) SUMMAND } .
SUMMAND := FACTOR { ( "*" | "/" FACTOR } .
FACTOR := CALL | number | "(" EXPR ")" .
CALL := ident [ "(" ident ";" number ";" number ";" EXPR ")" ]  .
```
Jede Funktion mit einem Namen einer Regel aus der EBNF parst genau diesen Teil der EBNF.
```
expr()
```
parst also einen gesamten Ausdruck, während
```
summand()
```
einen Summanden parst.

Eine Besonderheit gibt es in der Regel
```
CALL
```
: da sowohl ein Funktionsaufruf, als auch eine Variable jeweils mit einem Namen beginnt, ist nicht klar, um was es sich handelt. Erst anhand des nachfolgenden (eventuell fehlenden)
```
(
```
kann dies entschieden werden. Es kann dadurch wieder ausschließlich anhand des nächsten Zeichens festgestellt werden, welche Regel benutzt werden muss. Da das für jede Regel gilt, handelt es sich hier um einen LL(1)-Parser, falls du das je irgendwo hören/lesen solltest (LL wegen der Art des Parsers, in dem Fall rekursiver Abstieg, und 1, weil anhand eines Vorgriffssymbols entschieden werden kann, welche Regel benutzt werden muss).

Durch diese Grammatik ist übrigens auch sichergestellt, dass Vorrangregeln (z.B. * vor +) korrekt befolgt werden.

Der Fall mit
```
-1
```
im
```
next()
```
sorgt lediglich dafür, dass am Ende der Eingabe ein
```
EOF
```
Token erstellt wird, sodass ein unerwartetes Ende immer zu einem Syntaxfehler führen wird.
Außerdem prüft die Funktion
```
parse()
```
ob am Ende auch wirklich ein
```
EOF
```
erreicht wurde. Damit wird sichergestellt, dass nach einem Ausdruck nicht noch weitere Tokens übrig geblieben sind.

Und wie genau funktionieren deine Nodes?
Stell dir einen
```
Node
```
als einen Knoten in einem Baum vor, und stell dir vor, dass jeder solche Knoten einem Teil deiner Eingabe entspricht. Wenn du beispielsweise
```
1 + 2
```
eingibst, so wirst du einen Knoten mit
```
+
```
bekommen (abgebildet durch einen
```
BinOpNode
```
), welcher 2 Kindknoten (je eine Zahl, also ein
```
NumberNode
```
) hat. Wenn du jetzt den Knoten mit der Addition nach dem Ergebnis der Berechnung fragst (mit
```
execute()
```
), so wird er zuerst die beiden Kindknoten nach deren Ergebnis fragen (der linke Kindknoten wird 1, der rechte wird 2 zurückgeben), anschließend die Berechnung (in dem Fall die Addition) durchführen, und das schließlich Ergebnis zurückliefern.
P.S. Könnte ich die Ausgabe nicht am Ende, ganz böse, in ein eval packen und dann ausrechnen lassen?
```
public static void main(String[] args) throws Exception {
                String sums = new Sums().run("sum(i;0;4;i*sum(i;2;5;i*sum(i;7;8;i)))");
		System.out.println(sums);
                ScriptEngine engine = new ScriptEngineManager().getEngineByName("JavaScript");
                System.out.println("Ergebnis: "+engine.eval(sums));
	}
```
Das könnte man, wäre aber äußerst ineffizient. Viel einfacher wäre es, in den Nodes nicht einen String zu bestimmen, sondern direkt das Ergebnis zu berechnen (jeweils in der
```
execute()
```
-Methode, und als Rückgabetyp natürlich
```
int
```
o.ä. statt
```
String
```
).
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!

lima-city: Gratis werbefreier Webspace für deine eigene Homepage

Dir gefällt dieses Thema?

Über lima-city

lima-city bietet dir kostenlosen und werbefreien Speicherplatz für Deine Homepage. Sofort anmelden und direkt loslegen mit Webspace, PHP, Datenbanken, günstigen Domains und einer tollen Community!

kostenloser Webspace werbefrei: lima-city