c++ obliczanie wyrażeń

Mam jeszcze takie zadanko. Od razu piszę, że to nie na jakąś ocenę czy coś, uczę się dopiero C++ i to nie wiem jak ugryźć. Nie chcę gotowego kodu tylko jakąś podpowiedź, bo rozumiem że tu mam wczytać string i co dalej...
Do rzeczy. Zadanie jest takie:
Programy rozpoznawania znaków (OCR) są dołączane do oprogramowania skanerów. Zatem automatyczne przepisanie notatek do postaci elektronicznej stało się łatwe. Dotyczy to także działań matematycznych.

Napisz program, który po wczytaniu wiersza zawierającego wyrażenie matematyczne, wyznaczy jego wartość. Podane wyrażenie będzie zawierało tylko działania dodawania i odejmowania, a także nawiasy okrągłe (mogą być zagnieżdżone). Ponadto, nie należy przejmować się priorytetem operatorów, ponieważ każde działanie dwuargumentowe, będzie ujęte w nawiasy (nie wystąpią wyrażenia postaci: 2+2-2). Wszystkie liczby będą nieujemne.

Dane wejściowe będą składać się z kilku wyrażeń, gdzie każde będzie umieszczone w osobnym wierszu. W przypadku wiersza pustego (nie zawierającego żadnego znaku alfanumerycznego) należy go zignorować. Jako wynik, dla każdego wiersza należy wypisać wartość wczytanego wyrażenia lub słowo "BLAD", jeśli jest ono błędnie zapisane.

Przykładowe dane:

1+2
2+(3-1)
Wynik:

3
4

1. Albo bawisz się ONP
2. Albo robisz to tak:
   a) szukasz najbardziej zagnieżdżonego nawiasu i obliczasz jego wartość.
   b) powtarzasz a) aż nie będzie nawiasów
   c) kiedy nie ma już nawiasów to obliczasz pozostałe wyrażenie

Shalom napisał(a)

1. Albo bawisz się ONP
2. Albo robisz to tak:
   a) szukasz najbardziej zagnieżdżonego nawiasu i obliczasz jego wartość.
   b) powtarzasz a) aż nie będzie nawiasów
   c) kiedy nie ma już nawiasów to obliczasz pozostałe wyrażenie

Do ONP jeszcze nie doszedłem kursie z którego się uczę :)
Co do drugiego sposobu to gdyby było takie wyrażenie:
((2+14)-(51-62))-(((61+32)-71)+79)
to czy ta metoda byłaby dobra? Bo są jakby dwa bloki zagnieżdżonych nawiasów.

Akurat jeśli chodzi o ONP, to jest to ułatwienie, a nie utrudnienie. ONP przetwarza się bardzo łatwo, klasyczną notację infiksową (czyli np. 2+2) -- trudno. Oczywiście, nie możesz zastosować tu po prostu ONP, bo zadanie wyraźnie mówi o tym, że dane zostaną zapisane w postaci infiksowej.

Ale istnieją algorytmy umożliwiające przeprowadzenie konwersji z notacji infiksowej do ONP. Są opisane choćby w artykule na polskiej wikipedii.

Skonwertowanie notacji infiksowej do ONP, a następnie parsowanie i obliczanie wyrażenia może być prostsze od przetwarzania bezpośrednio notacji infiksowej.

Nie zawsze jednak polecam to zastosować. Jeśli program rozumiałby notację infiksową, to można by prawdopodobnie lepiej zaimplementować obsługę błędów.

W przypadku notacji infiksowej można pokusić się o zbudowanie w pamięci drzewa obiektów, które reprezentują poszczególne wyrażenia. Będą to zarówno proste operandy (np. 2 czy 47), jak i operatory wraz z argumentami (przy czym każdy z argumentów jest wyrażeniem, a więc może zawierać operatory).

Przeważnie takie drzewa buduje się dwuetapowo. Najpierw jakiś analizator leksykalny (lekser) dokonuje wstępnego przetwarzania, wczytując kolejne znaki i robiąc z nich listę jakichś bardziej złożonych tokenów. Następnie analizator składniowy (parser) przerabia tę listę na drzewo wyrażeń. W C++ wyrażenia można ładnie zakodować jako polimorficzne obiekty. Tj. każde wyrażenie ma metodę oblicz(). Po klasie Wyrażenie dziedziczą inne klasy, np. Stała (w konstruktorze podaje się jej wartość). Funkcja oblicz() dla stałej 5 zwraca po prostu 5. Inną podklasą Wyrażenia jest np. Dodawanie i jego funkcja oblicz() zwraca prawyOperand->oblicz() + lewyOperand->oblicz(), przy czym prawy- i lewyOperand to także wyrażenia. Po zbudowaniu drzewa składni wystarczy więc wywołać korzeń->oblicz() i wszystko piękne nam się policzy.

Taka obiektowa reprezentacja jest trochę skomplikowana, ale może to być niezłe ćwiczenie w języku obiektowym takim jak C++.

Nie musisz jednak faktycznie stosować polimorficznych obiektów; w ogóle nie musisz stosować obiektowości. Parser może od razu liczyć wartość wyrażenia.

Aby przetwarzać zagnieżdżone nawiasy ważne jest, żeby parser działał rekurencyjnie. Jeśli masz zagwarantowane, że nawiasy zawsze będą użyte, to to też jest sporym ułatwieniem, bo w każdym nawiasie na danym poziomie masz tylko jeden operator.

Funkcja obliczWyrażenie() może działać np. tak (wymyślam to na bieżąco, mam nadzieję że się jakoś głupio nie rypnę):
-Jeśli na początku wejścia jest liczba, to wczytaj ją i zwróć (uwaga: wczytanie oznacza też zwiększenie aktualnej pozycji na wejściu, może to być inkrementacja indeksu lub inkrementacja wskaźnika).
-W przeciwnym wypadku powinien się tam znajdować nawias otwierający. Wykonaj następujące kroki:
--Wczytaj nawias otwierający (jeśli go nie ma -> błąd)
--Wywołaj rekurencyjnie obliczWyrażenie() i zapisz zwróconą wartość w zmiennej lewyOperand (przed tym wywołaniem pozycja na wejściu była ustawiona tuż za nawiasem otwierającym; po wywołaniu będzie za pierwszym argumentem, przy czym pierwszym argumentem może być liczba lub złożone wyrażenie z nawiasem; po wywołaniu powinniśmy być ustawieni na operatorze)
--Wczytaj operator i zapisz w zmiennej operator (może być typu char: '+' albo '-').
--Wywołaj rekurencyjnie obliczWyrażenie() i zapisz zwróconą wartość w zmiennej prawyOperand
--Wczytaj nawias zamykający (jeśli go nie ma -> błąd)
--W zależności od wartości zmiennej operator zwróć lewyOperand + prawyOperand lub lewyOperand - prawyOperand.

I tyle, to raczej prosty algorytm, niewymagający jakiegoś przeszukiwania nawiasów. Dzięki odpowiedniemu ułożeniu wywołań rekurencyjnych oraz właściwego wykonywania obliczeń (najpierw wywołania, na końcu funkcji obliczenia) zapewniamy, że działanie z najbardziej zagnieżdżonego nawiasu zostanie wykonane jako pierwsze.

BTW: w tej wersji funkcja wysypie się, jeśli będziesz miał podwójne nawiasy, czyli np. ((2 + 2)) -- nie wiem, czy funkcja musi to obsługiwać, czy nie. Zresztą można to łatwo zaimplementować. Póki co, gdy wczytujemy nawias, oczekujemy jedynej słusznej sekwencji: nawias otwierający->wyrażenie->operator->wyrażenie->nawias zamykający. Możemy dopuszczać drugą opcję: nawias otwierający->wyrażenie->nawias zamykający. Czyli jeśli zaraz po pierwszym wyrażeniu następuje nie operator, tylko nawias zamykający, to wczytujemy go, nie protestujemy i zwracamy lewyOperand. I obsłużymy przypadek ((takich+nawiasów)).

To zadziała dlatego, że wyrażenia z nawiasu przetwarzasz po prostu wywołaniem rekurencyjnym obliczWyrażenie() i nie obchodzi Cię, czy tam w środku jest jeszcze jakiś nawias, czy nie. Jedno wywołanie obliczWyrażenie() martwi się tylko o jeden poziom nawiasów i jedno działanie.

Zadziala, ale musisz szukać za każdym razem najbardziej zagnieżdżonego nawiasu.

bswierczynski - dziękuję. Muszę się "wgryźć w to co napisałeś. Trochę jeszcze po omacku się poruszam w C++, ale powoli do przodu. Mam prośbę możecie też zerknąć na inny wątek, z monotonicznością ciągu? http://4programmers.net/Forum/viewtopic.php?id=153061

Wracam do tego programu, bo już co nieco poczytałem o ONP i stosach. I mam takie pytania.

1. Jeśli mam wyrażenie np. 2+4 to lepiej jest to wczytać jako tablicę, czy jako string?
2. Jeśli mam wyrażenie np. 21+4 to jak rozpoznam liczbę dwucyfrową? Z jednocyfrowymi rozumiem - odczytuję element tablicy sprawdzam czy to liczba i już, ale gdy wczytam 21+4 to tablica ma wówczas zawartość
   tab[0]=2
   tab[1]=1
   tab[2]=+
   tab[3]=4

edytowałem

Proszę nie krzyczeć, ze kod jest beznadziejny, zadanie ze stosem robię pierwszy raz w życiu i po prostu nie wiem jak powinno być dobrze/ładnie etc.
Mój kod ma wykonywać działania na razie na cyfrach (tzn na stosie mogą być już liczby > 9). Nie wiem jak zrobić dla liczb dwucyfrowych o czym wspominałem wyżej oraz nie wiem co w ogóle mogę tu poprawić na tę chwilę. System z którego wziąłem to zadanie daje mi 0 punktów, choć liczyłem na wielu przykładach i działało :)

#include <iostream>
#include <sstream>
#include <string>
#include <cstring>
#include <stack>

using namespace std;

bool czyLiczba(string zdanie){
	for(int i=0; i<zdanie.size(); i++) {
		if(!(zdanie[i]>=char(48) && zdanie[i]<= char(57))) 
			return 0;
	} 
	return 1;  
}

int main () {

	char wiersz[100];
	
	while (!cin.eof()) {
		cin >> wiersz;
		int dl=strlen(wiersz);
		stack<int> stos;
		for (int i=0; i<dl; i++) {
			if (wiersz[i]!=')') {
				if (wiersz[i]=='(' || wiersz[i]=='-' || wiersz[i]=='+') stos.push((int)wiersz[i]);
				else stos.push(wiersz[i]-'0');
			}
			else if (wiersz[i]==')' && !stos.empty()) {
				int a=stos.top(); 
				stos.pop();	//zdejmuje liczbe przed nawiasem )
				if (stos.top()==43) {
					stos.pop(); //zdejmuje plus
					int b=stos.top();
					stos.pop(); //zdejmuje liczbe
					stos.pop(); //zdejmuje nawias
					stos.push(a+b); //dodaje wynik dzialania
				}
				if (stos.top()==45) {
					stos.pop(); //zdejmuje razy
					int b=stos.top();
					stos.pop(); //zdejmuje liczbe
					stos.pop(); //zdejmuje nawias
					stos.push(b-a); //dodaje wynik dzialania
				}
			}
			else if (wiersz[i]==')' && stos.empty())
				i=dl;
		}
	//zakonczylem petle for
		if (stos.size()==3) {
			int a=stos.top();
			stos.pop();
			if (stos.top()==43) {
				stos.pop();	//zdejmuje ze stosu +
				int b=stos.top();
				stos.pop(); //zdejmuje ze stosu liczbe
				stos.push(a+b);
			}
			if (stos.top()==45) {
				stos.pop();	//zdejmuje ze stosu -
				int b=stos.top();
				stos.pop(); //zdejmuje ze stosu liczbe
				stos.push(b-a);
			}
		}
		if (stos.empty()) cout << "BLAD" << endl;
		else if (!stos.empty() && !cin.eof()) {
			cout << stos.top() << endl;
			stos.pop();
		}
	};
    return 0;
}

string jest tablicą więc pytanie jest troche dziwne. nie musisz rozpoznawać ilucyfrowa jest liczba:
int liczba = 0;
bool przetwarzamliczbe = false;
while (niekoniecciagu())
{
char znak = pobierzkolejnyznak(); // aktualnie przetwarzany znak z tablicy
if (jestcyfra(znak))
{
przetwarzamliczbe = true;
liczba = liczba*10 + znak - '0'; // <-- do samodzielnej analizy
}
else
{
if (przetwarzamliczbe)
{
//zrob cos z liczba;
liczba = 0;
przetwarzamliczbe=false;
}
// zrob cos ze znakiem
}
}