• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

question-closed Parser vs Algorytm ONP (do wyliczeń arytmetycznych)

0 głosów
200 wizyt
pytanie zadane 30 października 2017 w C i C++ przez Jakub 0 Stary wyjadacz (13,240 p.)
zamknięte 30 października 2017 przez Jakub 0
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
komentarz zamknięcia: już znam wytłumaczenie

1 odpowiedź

+1 głos
odpowiedź 30 października 2017 przez Criss Mędrzec (171,380 p.)
wybrane 30 października 2017 przez Jakub 0
 
Najlepsza
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.
komentarz 30 października 2017 przez Jakub 0 Stary wyjadacz (13,240 p.)

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...

1
komentarz 30 października 2017 przez Criss Mędrzec (171,380 p.)
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ś.
komentarz 30 października 2017 przez Jakub 0 Stary wyjadacz (13,240 p.)
racja, nie zwróciłem uwagi. Dzięki za rozjaśnienie sytuacji i pozdrawiam

Podobne pytania

0 głosów
4 odpowiedzi 610 wizyt
pytanie zadane 31 października 2015 w C i C++ przez Dywan Nowicjusz (170 p.)
0 głosów
1 odpowiedź 82 wizyt
pytanie zadane 24 marca 2018 w PHP, Symfony, Zend przez Kamil Jarzyna Użytkownik (940 p.)
0 głosów
1 odpowiedź 90 wizyt
pytanie zadane 17 lipca w Python, Django przez Jakub 0 Stary wyjadacz (13,240 p.)
Porady nie od parady
Komentarze do pytań nie służą do odpowiadania, od tego jest wydzielona sekcja odpowiedzi. Funkcją komentarzy jest natomiast możliwość uzyskania dodatkowych informacji na temat samego posta.Komentarze

66,451 zapytań

113,207 odpowiedzi

239,680 komentarzy

46,704 pasjonatów

Przeglądających: 243
Pasjonatów: 15 Gości: 228

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto dwie polecane książki warte uwagi. Pełną listę znajdziesz tutaj.

...