[C++] Reverse Polish Notation

  • Themenstarter Themenstarter Bgag
  • Beginndatum Beginndatum
B

Bgag

Hallo!

Ich bin gerade dabei im Rahmen eines Uni-Projekts eine Klasse zu schreiben, die Ausdrücke in Umgekehrter Polnischer Notation auswertet. Dabei möchte ich mir die Option offen halten, die Klasse nachträglich zu erweitern. Dazu bräuchte ich eine Funkion, die es mir erlaubt, einen Operator, die Anzahl an zu diesem gehörigen Operanden und eine Funktion, die die Aufgabe des Operators erfüllt, übergeben bekommt.

Ich brauche also praktisch die Möglichkeit Pointer auf Funktionen mit einer Variablen Anzahl an Parametern zu definieren. Ist dies möglich?

Vielen Dank für eure Hilfe.

Liebe Grüße,

Andreas
 
Zuletzt bearbeitet von einem Moderator:
Ein Vektor ist ja ein dynamisches Array. Der Aufrufer füllt den Vektor mit Operatoren und die Funktion kann dann mit std::vector<Operator>::size herausfinden, wie viele Elemente im Vektor drin sind.

C++: 
bool Calc(std::vector<Operator>& operators)
{
      if(operators.size() < 2)
             return false;
      return true;
}

int main()
{
          std::vector<Operator> ops;
          ops.push_back(Operator());
          if(!Calc(ops))
                 std::cout << "Invalid operator count!" << std::endl;
}
 
Hallo zusammen!

Ich bin nun soweit, dass ich eine RPN-Basisklasse implementiert habe, die es mir erlaubt Operatoren über eine Funktion hinzuzufügen, sodass ich diese beim Berechnen von gegebenen Termen verwenden kann.

Nun möchte ich die Klasse so erweitern, dass ich nicht nur Ausdrücke auswerten, sondern auch Funktionen definieren kann. Entsprechend bräuchte ich auch eine Funktion, die mir das Auswerten von Funktionen ermöglicht. In dem nachfolgenden Beispiel wird zuerst eine Klasse MyRPN von der Basisklasse FancyRPN abgeleitet. Dies ermöglicht es dem späteren Anwender beliebige Operatoren hinzuzufügen. In der nachfolgenden main() Funktion ist dann zu sehen, wie ich mir später das Auflösen von Ausdrücken, das Deklarieren von Funktionen und deren Auswertung vorstelle.

C++: 
#include "Tokenizer.h"

class MyRPN : public FancyRPN {
   public:
   
      SubClass() : SuperClass() {
         // Add some operators.
         addOperator("+", &add, 2);
         addOperator("*", &mult, 2);
         addOperator("/", &div, 2);
         // ...
      }
};

int main() {
   // Create a new instance of the rpn class, ...
   MyRPN rpn();
	
   // ... calculate a given term, ...
   rpn.calc("3 -4 + 13.0 *");
	
   // ... declare a new funtion ...
   rpn.addFunc("f", "2 x * y +", "x", "y");
	
   // ... and solve it using given parameters.
   rpn.solveFunc("f", 3, -4);

   return 0;
}

Man sieht hier schon welche Schwierigkeiten auf mich zukommen. Ich möchte in den Funktionen addFunc() und solveFunc() nicht mit Vektoren, sondern tatsächlich mit dynamischen Parameterlisten arbeiten. In beiden Fällen sollen beliebig viele Parameter angegeben werden können, wobei sich natürlich die Anzahl der Parameter der Funktion solveFunc() nach der in der Funktionsdeklaration angegebenen Anzahl an Parametern richtet.

Meine Frage ist jetzt, was ihr von dieser Notation haltet, ob ihr vielleicht eine bessere Möglichkeit seht und wie ich meine Idee, wenn ihr keine bessere habt, umsetzen kann.

Vielen Dank für eure Hilfe.

Liebe Grüße,

Andreas

EDIT: Alternativ könnte es auch möglich sein Funktionen direkt auszuwerten.
C++: 
   rpn.solve("2 x * y +", 3, -4.5);
 
Zuletzt bearbeitet von einem Moderator:
Eigentlich sollte man variable Paramterlisten vermeiden, denn die Variablen werden nicht auf den Typ geprüft (siehe hier, ganz nach unten scrollen).

Aber etwas anderes außer Arrays und Vektoren fällt mir momentan nicht ein.
 
Danke für deine Antwort!

Ich würde variable Parameterlisten auch recht gern vermeiden, jedoch weiß ich nicht, wie ich dann feststellen soll, was eine Variable ist und was nicht. Wie kann ich in Polnischer Notation eine Funktion deklarieren und in ihr variablen erkennen?

Es wäre natürlich möglich, alle Token, die keinen Operator definieren, als Variable zu verwenden und dann die Funktionen wieder mit Parameter-Vektoren aufzurufen. In diesem Fall muss beim Parsen zwischen Funktionen und Termen unterschieden werden, denn nur bei Termen können unbekannte Token auftauchen.

Was haltet ihr davon?

Liebe Grüße,

Andreas
 
Du könntest dir eine eigene Funktion bauen, z.B. addVariable(std::string Bezeichner, int Wert).
Somit hättest du ein assoziativ Array.
 
Hi.

Ich würde das mit den Funktionen gar nicht so kompiliziert implementieren. Nutze doch einfach die Vorteile eines RPN Rechners!

Ich würde den Rechner als Stackmaschine implementieren; und warum soll man dabei immer nur vollständige Ausdrücke eingeben können?

Ein Vorteil eines RPN Rechners ist doch gerade das man die Zwischenergebnisse sehen kann. Da ist es irgendwie unnatürlich erst einen kompletten Ausdruck eingeben zu müssen und der Rechner gibt nur das Ergebnis zurück.

Eigentlich benötigt man für solch einen Rechner nur die Möglichkeit die einzelnen Token nacheinander einzugeben und eine Möglichkeit den Stack zu betrachten:
C++: 
struct calc {
  Stack get_stack() const;
  Num top() const;
  void input(Token);
};
Eine Rechnung sähe dann so aus:
C++: 
calc c;

c.input(2);
c.input(3);
c.input("+");
cout << "Ergebnis: " << c.top();
Funktionen benötigen Argumente, die sie bei einem RPN Rechner doch ganz einfach auf dem Stack vorfinden können:
C++: 
c.defun("f", "? ? + 2 *");

c.input(5);
c.input(3);
c.input("f");

cout << "Ergebnis: " << c.top();
Gruß
 
Hallo deepthroat!

Eigentlich hast du recht, jedoch ist es nicht mein Ziel einen RPN-Rechner zu programmieren. Ich möchte vielmehr eine Klasse programmieren, die es mir erlaubt Rechenoperationen zu definieren und diese in RPN-Termen und -Funktionen zu nutzen. Später soll dann noch eine Umwandlung zwischen Infix- und Postfix-Notation folgen, die es ermöglicht die gewohnte Schreibweise zu nutzen. Das eigentliche Ziel ist es dann komplette Funktionen als String zu übergeben und das Ergebnis unter Angabe der einzelnen Parameter berechnen zu lassen.

Die Funktionen betreffend hattest du eigentlich schon eine ganz gute Idee. Es wäre möglich die Variablen als einheitliches Zeichen, in deinem Fall ein Fragezeichen, zu definieren. In diesem Fall muss jedoch nicht nur die Reihenfolge bei der Angabe der Parameter eingehalten werden, sondern es kann auch passieren, dass ein Parameter mehrfach angegeben werden muss. Das ist eigentlich eher unschön. Daher überlege ich, ob ich nicht alphanumerische Zeichen samt Unterstrich immer als Variablen verstehen sollte, sofern es keine deklarierten Operatoren sind.

Aktueller Stand:
Das Hinzufügen von Operatoren und das korrekte Evaluieren von gegebenen Termen ist bereits möglich. Nachfolgend das Testscript, sowie dessen Ausgabe.

C++: 
#include "FancyRPN.h"
#include <cmath>
      
double add(std::vector<double> v) {
	return v[0] + v[1];
}
      
double sub(std::vector<double> v) {
	return v[0] - v[1];
}

double mult(std::vector<double> v) {
	return v[0] * v[1];
}

double div(std::vector<double> v) {
	return v[0] / v[1];
}

double sqrt(std::vector<double> v) {
	return sqrt(v[0]);
}

double pow(std::vector<double> v) {
	return pow(v[0], v[1]);
}

double max(std::vector<double> v) {
	return std::max(v[0], v[1]);
}

double min(std::vector<double> v) {
	return std::min(v[0], v[1]);
}

double exp(std::vector<double> v) {
	return exp(v[0]);
}

double cos(std::vector<double> v) {
	return cos(v[0]);
}

double sin(std::vector<double> v) {
	return sin(v[0]);
}

double tan(std::vector<double> v) {
	return tan(v[0]);
}

double log(std::vector<double> v) {
	return log(v[0]);
}

double fac(std::vector<double> v) {
	double t = 1;
	for(int i = v[0]; i > 1; i--)
		t *= i;
	return t;
}

void test(FancyRPN *rpn,std::string stream) {
	try {
		std::cout << stream << " = " << rpn->parsePostfix(stream) << std::endl;
	}
	
	catch(FancyRPNException& ex) {
		std::cout << ex.what() << std::endl;
	}
}

int main() {
	// Create a new instance of the rpn class, ...
	FancyRPN *rpn = new FancyRPN();
	rpn->addOperator("+", &add, 2);
	rpn->addOperator("-", &sub, 2);
	rpn->addOperator("*", &mult, 2);
	rpn->addOperator("/", &div, 2);
	rpn->addOperator("sqrt", &sqrt, 1);
	rpn->addOperator("^", &pow, 2);
	rpn->addOperator("max", &max, 2);
	rpn->addOperator("min", &min, 2);
	rpn->addOperator("exp", &exp, 1);
	rpn->addOperator("cos", &cos, 1);
	rpn->addOperator("sin", &sin, 1);
	rpn->addOperator("tan", &tan, 1);
	rpn->addOperator("log", &log, 1);
	rpn->addOperator("fac", &fac, 1);
		
	// ... and run some tests.
	test(rpn, "3 -4 + 13.0 *");
	test(rpn, "3 -4 + 13.0 * 5 4 + - 3 * .5 *");
	test(rpn, "2 2 * sqrt");
	test(rpn, "4 2.0 /");
	test(rpn, "16 2 ^ sqrt");
	test(rpn, "13 sin 3 +");
	test(rpn, "15 cos 2 *");
	test(rpn, "15 tan 2 sqrt *");
	test(rpn, "1 log");
	test(rpn, "5 fac");
	test(rpn, "4 3 ^ 64 -");
	test(rpn, "0 1 max");
	test(rpn, "0 1 min");
	test(rpn, "5 4 exp +");
	test(rpn, "0");
	test(rpn, "");
	test(rpn, "3 -4 + 13.0 * *");
	test(rpn, "3 4 5 +");
	test(rpn, "3 4 + 2 #");

   return 0;
}

Code: 
3 -4 + 13.0 * = -13
3 -4 + 13.0 * 5 4 + - 3 * .5 * = -33
2 2 * sqrt = 2
4 2.0 / = 2
16 2 ^ sqrt = 16
13 sin 3 + = 3.42017
15 cos 2 * = -1.51938
15 tan 2 sqrt * = -1.21056
1 log = 0
5 fac = 120
4 3 ^ 64 - = 0
0 1 max = 1
0 1 min = 0
5 4 exp + = 59.5982
0 = 0
Empty input stream given.
To many operators in "3 -4 + 13.0 * *".
To many operands in "3 4 5 +".
Failed to parse "3 4 + 2 #" unknown token "#" found.

Würde mich über einige Anmerkungen freuen.

Liebe Grüße,

Andreas

EDIT: Bei der Umwandlung von Infix- zur Postfix-Notation muss ich ja eine Priorisierung der Operatoren vornehmen. Wieviele unterschiedliche Prioritäten brauche ich. Reichen tatsächlich drei?

Strich-Operatoren: 3 (niedrigste)
Punkt-Operatoren: 2
Klammern und Funktionen: 1 (höchste)
 
Zuletzt bearbeitet von einem Moderator:
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück