Parser vs Algorytm ONP (do wyliczeń arytmetycznych)

Question

Hej, mam dzisiaj krótkie pytanie: Co lepiej stosować do implementacji wyrażeń, Parser czy odwrotną notacje polską?

Parser - http://informatyka.wroc.pl/node/391

ONP - https://pl.wikipedia.org/wiki/Odwrotna_notacja_polska

Odwrotną notacje już raz wykorzystałem natomiast budowa prostego parsera mnie przeraża :/ Uczę się tego ponieważ będę chciał napisać własny interpreter brainfucka i to chyba będzie mi potrzebne... Co wy byście polecili? Zauważyłem że ONP działa trochę jak interpreter języka programowania bo odkłada dane na stos. Będę wdzięczny za pomoc i pozdrawiam

Answer 1

Tzn.. parser to gotowa działająca rzecz służąca do... parsowania, a ONP to sposób zapisu wyrażenia (ułatwiający implementacje interpretera ze względu na możliwość pominięcia priorytetów czy nawiasów). Na ONP konwertuje się z tradycyjnej notacji, żeby łatwiej można było podejść do interpretacji, a user mógł napisać wyrażenie tradycyjnie. W podlinkowanym przez ciebie artykule (zatytułowany przez ciebie jako "Parser") ten krok jest zupełnie pominięty (przynajmniej na pierwszych kilku stronach nie widziałem) - po prostu w kodzie na sztywno zakodowane jest jakieś wyrażenie w postaci drzewa mniejszych wyrażeń. ONP mogłoby by ci posłużyć do przekonwertowania wyrażenia podanego przez usera (prawdopodobnie string) na takie drzewo (z reguły to jest lista czy ew. tablica, ale nic nie stoi na przeszkodzie, żeby tworzyć takie drzewo).
Więc odpowiadając na twoje pytanie "co lepiej stosować?": obydwa. Dwa wrzucone przez ciebie linki przedstawiają dwie części pełnego interpretera (zdolnego do zinterpretowania inputu usera, a nie tylko zakodowanego drzewa wyrażeń). Właściwie to nieadekwatnie podpisałeś linki - pierwszy link to jest interpreter, a algorytm ONP właśnie służy do parsowania.

Comments

Dzięki za poprawkę :) , tyle że zrobiłem program przyjmujący wyrażenie w tradycyjnej postaci po czym je konwertujący i obliczający:

#include "stdafx.h"
#include "stack.h"
//Cstack :  push, pop ,isEmpity, rPower, rVheight 

using namespace std; 

//////////////////////////////////////////////////////////////////////////////////

string ONPexpResult(vector<string> &ONPexp) { //wymaga dopracowania !!!!!!!!!!! i zmienien astosu na int by uniknac wielu problemow zbednych waronkow i konwersji 

	Cstack nr;
	
	for (int i = 0; i < ONPexp.size(); i++) {

		if (ONPexp[i][0] >= 48 && ONPexp[i][0] <= 57) {
			//jeazeli to byla liczba 
			nr.push(ONPexp[i]);
		}
		else {
			//jezeli to jest operator 
			string rightSTR = nr.pop(); //usuwamy liczby z naszego stosu 
			string leftSTR = nr.pop();
			int left, right;
			istringstream iss(leftSTR);
			iss >> left;
			istringstream iss2(rightSTR); //odpowiednia konwersja 
			iss2 >> right;

			int r;

			if (ONPexp[i] == "+") {
				r = left + right;
			}if (ONPexp[i] == "-") {
				r = left - right;
			}if (ONPexp[i] == "*") {
				r = left * right;
			}if (ONPexp[i] == "/") {
				r = left / right;
			}

			ostringstream ss;
            ss << r;
            string rSTR = ss.str();

			nr.push(rSTR);
		}
	}

	return nr.pop();
}

///////////////////////////////////////////////////////////////////////////////

void convertToONP(vector<string>exp, vector<string> &ONPexp) {
	Cstack op;
	for (int i = 0; i < exp.size(); i++) {
		
		if (exp[i][0] >= 48 && exp[i][0] <= 57) {
			//co jezeli jest to jakas liczba 
			ONPexp.push_back(exp[i]);
		}
		else if (exp[i] == "(" || exp[i] == ")") {
			//co jezeli byl to nawias 
			if (exp[i] == "(") {
				//jezeli taki (
				op.push(exp[i]);
			}
			else {
				//jezeli taki )
				while (true) {
					if (op.isEmpity())break; //jezeli elementy w stosie sie skonczyly 
					else if (op.rVheight() == "(") { op.pop();  break; } //jezeli doszlismy do nawiasu otwierjacego 
					else ONPexp.push_back(op.pop());
				}
			}
		}
		else {
			while (true) {
				if (op.isEmpity()) { op.push(exp[i]); break; } //jezeli stos jest pusty
				else if (op.rVheight() == "(") { op.push(exp[i]); break; } //jezeli doszlismy do nawiasu otwierajacego 
				else if (op.rPower(op.rVheight()) < op.rPower(exp[i])) { op.push(exp[i]); break; } //jezeli piotytet ostatniego elementu na stosie jest nizsy od tego 
				else ONPexp.push_back(op.pop()); //jezlei nie to usuwamy elemento ze stosu i dajemy na wyjscie 
			}
		}
	}

	while (!op.isEmpity()) {
		ONPexp.push_back(op.pop());
	}

}

/////////////////////////////////////////////////////////////////////////////////////////////

void inputExp(vector<string> &exp) {
	string e;
	while (true) {
		cin >> e;
		if (e == "=")break;
		else exp.push_back(e);
	}
}

///////////////////////////////////////////////////////////////////////////////////

int main()
{
	vector<string>exp;
	vector<string>ONPexp;

	inputExp(exp);

	convertToONP(exp,ONPexp);

	for (int i = 0; i < ONPexp.size(); i++) {
		cout << ONPexp[i] << " ";
	}

	cout << endl;

	cout << ONPexpResult(ONPexp) << endl;

	

	_getch();
	return 0;
}

Program nie używa żadnych drzew wyrażeń, klas abstrakcyjnych, lewej strony prawej itd...

Chociaż przyznam że kod nie jest piękny jak i program nie w pęłni funkcjonalny...

---

No i spoko. Tak jak mówiłem - z reguły to jest lista czy tablica, a nie drzewo i ty właśnie tak zrobiłeś.

---

racja, nie zwróciłem uwagi. Dzięki za rozjaśnienie sytuacji i pozdrawiam