Hér er mín fyrsta grein sem kemur undir forritun.

Ef við viljum reikna dæmi eins og 1*4+1+2*3 þá þarf að reikna það eftir stærðfræði reglum, semsagt byrja reikna margföldun og deilingu áður en reiknað er plús og mínus.

Þannig við reiknum fyrst 1*4 svo 2*3 sem gefur okkur 4+1+6 eða 11.

Svo er líka hægt að blanda svigum inn í dæmið, eins og: 4*(2+2) sem væri 4*4. Þá þyrftum við að reikna dýpsta svigann fyrst. 1+(1+1+(1+1)) væri þá 1+(1+1+2) eða 1+4 = 5.

Hvernig er hægt að forrita þetta á einfaldan hátt? Mín lausn er að nota binary tree.

Ef við tökum 1+1*2 sem dæmi þá byggjum við tréið upp svona:

Skref 1: Skoðum 1, þar sem 1 er tölugildi verður það alltaf að lauf í tréinu, en þar sem við höfum enga rót, verður talan rótin.
 1
Skref 2: Næst lesum við +, ég get sagt strax að plús og mínus verða alltaf að rót. Svo við setjum það í rótina, sem gerir þá 1 að lauf.
   +
  / 
 1
Skref 3: Næst lesum við 1, þar sem tölugildi verða alltaf að laufum setjum við það sem lauf undir +.
   +
  / \
 1     1
Skref 4: Næst lesum við inn *, bæði margföldun og deiling verður að foreldra tölugildsins sem við vorum á.
   +
  / \
 1     *
      / 
    1
Skref 5: Næst lesum við inn 2, tölugildi verða alltaf að lauf.
   +
  / \
 1     *
      / \
    1     2

Núna sjáum við hvernig tréið er byggt upp, og hvernig allar laufar eru tölugildi.

En hvernig reiknum við úr binary tree?

Það er lítið mál, ein leið er að fara ,,recursive" í gegnum tréið frá rótinni, við byrjum alltaf að fara recursive til vinstri og svo til hægri. Þegar recursive fallið byrjar að aftur-kalla sig þá getum við lagt saman tölugildin og sett það í staðin fyrir aðgerð eða (+, -, *, /)

   +
  / \
 1     *
      / \
    1     2
1*2 verður að:
   +
  / \
 1     2
eða 1+2 = 3

Áður en ég æði áfram í forritun, þá vill ég taka skref 5 aftur. Hvað ef við bætum við + 10 á skref 5? Þannig dæmið yrði núna: 1+1*2+10

Hér er skref 5:
   +
  / \
 1     *
      / \
    1     2

Næst lesum við + þá fer hún í rótina, eins og ég sagði að ofan, plús og mínus fara alltaf í rótina.
       +
     /
   +
  / \
 1     *
      / \
    1     2
Næst lesum við 10 sem verður að lauf.
Hér er mín fyrsta grein sem kemur undir forritun.

Ef við viljum reikna dæmi eins og 1*4+1+2*3 þá þarf að reikna það eftir stærðfræði reglum, semsagt byrja reikna margföldun og deilingu áður en reiknað er plús og mínus.

Þannig við reiknum fyrst 1*4 svo 2*3 sem gefur okkur 4+1+6 eða 11.

Svo er líka hægt að blanda svigum inn í dæmið, eins og: 4*(2+2) sem væri 4*4. Þá þyrftum við að reikna dýpsta svigann fyrst. 1+(1+1+(1+1)) væri þá 1+(1+1+2) eða 1+4 = 5.

Hvernig er hægt að forrita þetta á einfaldan hátt? Mín lausn er að nota binary tree.

Ef við tökum 1+1*2 sem dæmi þá byggjum við tréið upp svona:

Skref 1: Skoðum 1, þar sem 1 er tölugildi verður það alltaf að lauf í tréinu, en þar sem við höfum enga rót, verður talan rótin.
 1
Skref 2: Næst lesum við +, ég get sagt strax að plús og mínus verða alltaf að rót. Svo við setjum það í rótina, sem gerir þá 1 að lauf.
   +
  / 
 1
Skref 3: Næst lesum við 1, þar sem tölugildi verða alltaf að laufum setjum við það sem lauf undir +.
   +
  / \
 1     1
Skref 4: Næst lesum við inn *, bæði margföldun og deiling verður að foreldra tölugildsins sem við vorum á.
   +
  / \
 1     *
      / 
    1
Skref 5: Næst lesum við inn 2, tölugildi verða alltaf að lauf.
   +
  / \
 1     *
      / \
    1     2

Núna sjáum við hvernig tréið er byggt upp, og hvernig allar laufar eru tölugildi.

En hvernig reiknum við úr binary tree?

Það er lítið mál, ein leið er að fara ,,recursive" í gegnum tréið frá rótinni, við byrjum alltaf að fara recursive til vinstri og svo til hægri. Þegar recursive fallið byrjar að aftur-kalla sig þá getum við lagt saman tölugildin og sett það í staðin fyrir aðgerð eða (+, -, *, /)

   +
  / \
 1     *
      / \
    1     2
1*2 verður að:
   +
  / \
 1     2
eða 1+2 = 3

Áður en ég æði áfram í forritun, þá vill ég taka skref 5 aftur. Hvað ef við bætum við + 10 á skref 5? Þannig dæmið yrði núna: 1+1*2+10

Hér er skref 5:
   +
  / \
 1     *
      / \
    1     2

Næst lesum við + þá fer hún í rótina, eins og ég sagði að ofan, plús og mínus fara alltaf í rótina.
       +
     / 
   +    
  / \
 1     *
      / \
    1     2
Þar næst kemur 10, sem er tölugildi (lauf).
       +
     /  \
   +      10
  / \
 1     *
      / \
    1     2

En hvernig er þetta þá forritað? Ég var einmitt að útfæra eina lausn, þetta er auðvitað einungis mín lausn, en það eru til óteljandi margar. Margir líka betur við stack heldur en tré sem dæmi.

Við byrjum á main fallinu.

Þar biðjum við notandann um að slá inn dæmi sem á að leysa. Þar næst reynum við að athuga hvort við finnum sviga, við byrjum þá að leysa þann dýpsta o.sfv. þar til enginn svigi er eftir.


int main()
{
	cout << "Enter expression:" << endl;
	bool Continue = true;
	string exp; cin >> exp;
	// Laga strenginn, kemur síðar.
	exp = FixString(exp);
	while ( Continue )
	{
		// TODO: Athuga hvort opnir svigar eru jafn margir og lokaðir svigar.
		// Leita af dýpsta sviga. rfind virkar eins og find nema það leitar eftir því seinasta.
		int iBegin = (int)exp.rfind('(');
		int iEnd = (int)exp.find(')', iBegin);
		if (iBegin == string::npos || iEnd == string::npos)
			break;
		// Innihald svigans
		string parenthesis = exp.substr(iBegin+1, iEnd-iBegin-1);
 		// Lögum strenginn, kemur síðar.
		parenthesis = FixString(parenthesis);
		
		stringstream ss;
		ss << Calculate(parenthesis);
		
		// Yfirskrifum svigann með lausninni. Þurftum að notast við stringstream til að færa double yfir í std::string.
		exp.replace(iBegin,iEnd-iBegin+1,ss.str());
	}
	cout << endl << "Answer: " << Calculate(exp) << endl << endl;
}

Þar sem við sjáum gerast hér er að main fallið tekur inn input frá notanda, lagar strenginn, reiknar út innihald svigans og yfirskrifar svo svigann með lausn þar til enginn svigi er eftir.

Hér kemur beinagrindin fyrir binary tréið okkar:
struct Node
{
	double Item; // Inniheldur tölugildið.
	bool Operation; // Athuga hvort þetta sé aðgerð.
	char Operator; // Ef þetta er aðgerð, þá geymum við hana í char.
	Node* parent; Node* l; Node* r; // Nóður fyrir foreldra, og tvö börn, sem eru til vinstri og hægri, nota l fyrir left og r fyrir right.
	// Smiðurinn fyrir nóðuna.
	Node(double _item, bool _operation, char _operator)
	{
		parent = l = r = NULL;
		Item = _item;
		Operation = _operation;
		Operator = _operator;
	}
}; 
typedef Node* Tree; // Skilgreinum Tree sem bendir á Node.


Núna kemur fallið Calculate þar sem við byggjum tré-ið, þið megið endilega koma með athugasemd um hvernig ég get hreinsað til, ég verð að viðurkenna að hann er frekar subbulegur. Einnig hef ég örugglega ekki hreinsað vel eftir mig.

Fallið byggir tréið eftir þeim reglum sem ég nefndi að ofan. Ég fer þó ekki of djúpt í hvað fallið gerir. Við förum einfaldlega í gegnum input strenginn okkar, athugum hvort við séum í aðgerð eða tölugildi og byggjum tréið eftir þeim skilyrðum.

double Calculate(string exp)
{
	int iBegin = 0; int iEnd = 0;
	bool LastOperator = false;
	Tree hat = NULL;
	Node* root = hat;
	Node* currNode = root;
	for (int i = 0; i < (int)exp.length(); i++)
	{
		switch(exp[i])
		{
			case '+':
			case '-':
				{
					// Plús eða mínus
					if (LastOperator) // Smá tilraun að nota twos complement:
					{
						LastOperator = false;
						iBegin = iEnd = i;
					}
					else
					{
						iBegin = -1;
						Tree newRoot = new Node(0, true, exp[i]);
						newRoot->l = root;
						
						root->parent = newRoot;
						
						root = newRoot;
						currNode = newRoot;
						LastOperator = true;
					}
					break;
				}
			case '*':
			case '/':
				{
					// Margföldun eða deiling.
					iBegin = -1;
					
					Tree tempNode = new Node(0, true, exp[i]);
					if (currNode->parent == NULL)
					{
						currNode->parent = tempNode;
						currNode->parent->l = currNode;
						root = tempNode;
					}
					else
					{
						currNode->parent->r = tempNode;
						currNode->parent = tempNode;
						currNode->parent->l = currNode;
					}
					currNode = tempNode;
					LastOperator = true;
					break;
				}
			default:
				// Tölugildi (lauf)
				if (LastOperator)
					LastOperator = false;
				if (iBegin == -1)
					iBegin = iEnd = i;
				else
					iEnd++;
				
				if (i == (int)exp.length() -1 || (i < (int)exp.length()-1 && !IsNumeric(exp[i+1])))
				{
					string num =  exp.substr(iBegin, iEnd-iBegin+1);
					double dNum;
					
					if (num == "P")
						dNum = PI;
					else
					{
						stringstream ss(num); ss>>dNum;
					}
					// Eins og áður, öll tölugildi eru laufar.
					Tree tempNode = new Node(dNum, false, NULL);
					
					if (hat == NULL)
						hat = root = currNode = tempNode;
					else
					{
						tempNode->parent = currNode;
					
						if (currNode->l == NULL)
							currNode->l = tempNode;
						else
							currNode->r = tempNode;
					
						currNode = tempNode;
					}
				}
			break;
		}
	}
	rec(root);
	
	double Answer = root->Item;
	delete(root);
	return Answer;
}

Við sendum svo rótina af trénu í fallið rec, sem er stytting á recursive. Þar förum við í gegnum það og reiknum.
void rec(Node* t)
{
	if (t->l != NULL) // Ef barn til vinstri er til, förum þá recursive í það.
		rec(t->l);
	if (t->r != NULL) // Sama með það til hægri.
		rec(t->r);
	if (t->l != NULL && t->r != NULL) 
	/* Ef bæði börn eru ekki til, þá erum við komin í lauf, sem þýðir hvað? Við getum lagt saman tölugildi og sett útkomuna í aðgerðina. */
	{
		if (!t->l->Operation && !t->r->Operation)
		{
			if (t->Operator == '*')
				t->Item = t->l->Item * t->r->Item;
			else if (t->Operator == '/')
				t->Item = t->l->Item / t->r->Item;
			else if (t->Operator == '+')
				t->Item = t->l->Item + t->r->Item;
			else if (t->Operator == '-')
				t->Item = t->l->Item - t->r->Item;
			t->Operation = false;
			delete(t->r); // Léleg tilraun til ða hreinsa eftir mig.
			delete(t->l);
		}
	}
}

Það eru önnur föll sem ég sýndi ekki fram í greininni, þá vegna þess að það kemur þessari aðferð lítið sem ekkert við. FixString er ég að laga ef input strengur er til dæmis -4+3 þá er augljós villa hér í gangi, mínusinn fer í rótina en það vantar 1 barn. Því lagfæri ég það í 0-4+3 og sama með +.

Ég hef einnig stuðning fyrir PI, þá nota ég string::replace á það með PI tölugildinu. (upp á 5 tölu nákvæmni). Það sést nánar í fallinu Calculate hvernig ég meðhöndla stafinn P(PI).
string FixString(string str)
{
	std::string::repl
	if (str[0] == '+' || str[0] == '-')
		str = '0'+str;
	while (str.find("PI") != string::npos)
		str.replace(str.find("PI"),2,"P");
	
	return str;
}

Endilega komið með athugasemd um hvernig ég get bætt kóðann eða hvort þið viljið sjá frekari greinar, eða óskir um skemmtilegt dæmi til að leysa. Kannski ég komi með stack lausn ef ég hef tíma til að kíkja á það.

Takk fyrir, ég vona að þessi grein gefi ykkur einhverja hugmynd um hvernig má notast við binary tree við dagleg vandamál :-)

Fullur kóði er aðgengilegur, óskið bara eftir kóða á netfangið icewolfy hjá gmail.com.
Kv, wolfy.