• 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)

VPS Starter Arubacloud
0 głosów
634 wizyt
pytanie zadane 30 października 2017 w C i C++ przez Jakub 0 Pasjonat (23,120 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 (172,590 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 Pasjonat (23,120 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 (172,590 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 Pasjonat (23,120 p.)
racja, nie zwróciłem uwagi. Dzięki za rozjaśnienie sytuacji i pozdrawiam

Podobne pytania

0 głosów
4 odpowiedzi 1,204 wizyt
pytanie zadane 31 października 2015 w C i C++ przez Dywan Nowicjusz (170 p.)
0 głosów
1 odpowiedź 188 wizyt
pytanie zadane 24 marca 2018 w PHP przez Kamil Jarzyna Użytkownik (940 p.)
0 głosów
2 odpowiedzi 304 wizyt
pytanie zadane 15 marca 2020 w PHP przez szaman219 Nowicjusz (140 p.)

92,452 zapytań

141,262 odpowiedzi

319,085 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

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

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...