Nefunguje algoritmus v C# - co mám špatně?

Od: Datum: 03.02.13 20:40 odpovědí: 3 změna: 04.02.13 03:37

Dobrý den,

Pokouším se v C# napsat Shunting-yard algoritmus (algoritmus pro převod matematického výrazu z infixového do postfixového zápisu).

Pro vysvětlení:

http://cs.wikipedia.org/wiki/Shunting-yard_%28algoritmus%29

a

http://cs.wikipedia.org/wiki/Postfixov%C3%A1_notace

Zatím vypadá následovně. Pro jednoduchost jsem zatím vynechal práci s funkcemi (odmocniny, logaritmy, goniometrie...), vícecifernými či desetinnými čísly a zachytávání chyb. Zahrnul jsem jen základní matematické operace (plus, mínus, krát, děleno, mocnina) a práci se závorkami:

==========

string vstup = "";
string vystup = "";

string cisla = "0123456789"; // řetězec pro identifikaci čísel
string operatory = "+-*/^"; // řetězec pro identifikaci operátorů
Dictionary priorita = new Dictionary(); // slovník pro přiřazení priority operátorů
priorita.Add("+", 1);
priorita.Add("-", 1);
priorita.Add("×", 2);
priorita.Add("Ă·", 2);
priorita.Add("^", 3);
Dictionary asociativita = new Dictionary(); // slovník pro přiřazení asociativity operátorů
asociativita.Add("+", 'l';);
asociativita.Add("-", 'l';);
asociativita.Add("×", 'l';);
asociativita.Add("Ă·", 'l';);
asociativita.Add("^", 'r';);
Stack zasobnik = new Stack(); // zavedení zásobníku
int i = 0;
int delka = vstup.Length;

// následuje samotný algoritmus:

// Dokud jsou zde tokeny ke čtení:
for (i = 0; i < delka; i++)
{
// Přečti token.
string token = vstup.Substring(i, 1);
// Pokud je token číslo, přidej ho do výstupní fronty.
if (cisla.Contains(token))
{
vystup += token;
}
// Pokud je token operátor (dále jen o1), tak:
else if (operatory.Contains(token))
{
string o1 = token;
// dokud bude na vrcholu zásobníku operátor (s výjimkou závorek), o2, tak:
while (zasobnik.Count()!= 0 && operatory.Contains(zasobnik.Peek())
{
string o2 = zasobnik.Pop();
// pokud je o1 asociativní zleva a jeho priorita je menší nebo stejná (≤) jako priorita o2, nebo
// o1 je asociativní z prava a jeho priorita je nižší (<) než priorita operátoru o2,
if ((asociativita[o1] == 'l' && priorita[o1] <= priorita[o2]) ||
(asociativita[o1] == 'r' && priorita[o1] < priorita[o2]))
{
// vyjmi operátor o2 ze zásobníku a vlož ho do výstupní fronty;
vystup += o2;
}
}
// vlož operátor o1 na zásobník.
zasobnik.Push(o1);
}
// Pokud je token levá závorka, vlož ho na zásobník.
else if (token == "(")
{
zasobnik.Push(token);
}
// Pokud je token pravá závorka:
else if (token == ")")
{
// Dokud na vrcholu zásobníku nebude levá závorka, vybírej operátory ze zásobníku a zapisuj je do výstupní fronty.
while (zasobnik.Peek()!= "(")
{
vystup += zasobnik.Pop();
}
// Vyjmi ze zásobníku levou závorku, ale nevkládej jí do výstupní fronty.
zasobnik.Pop();
}
}
// Jestliže byly zpracovány všechny tokeny ze vstupu:
// Dokud budou v zásobníku operátory:
while (zasobnik.Count() > 0)
{
// Vyjmi operátor ze zásobníku a vlož ho do výstupní fronty.
vystup += zasobnik.Pop();
}
tbV.Text = vystup;
// Konec.

==========

Problém nastává, když to otestuji např. na výrazu: 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3

Správný výsledek je: 3 4 2 * 1 5 - 2 3 ^ ^ / +

Mně ovšem vychází: 3 4 2 × 1 5 - 2 3 ^

Nenapadá někoho, kam mi zmizely ty poslední tři operátory? Kde mám v algoritmu chybu?

Děkuji za rady.

P.S.: Ten algoritmus píši v rámci studia výpočetky na gymplu, tak omluvte můj amatérismus...


Seznam odpovědí:
 
moment čekejte prosím, probíhá přenos dat...
Zobrazení struktury odpovědí v otázce
Skrytí struktury odpovědí v otázce
Zobrazení struktury odpovědí v otázce

 

Odpovědi na otázku:
Od: lemplar
Datum: 03.02.13 21:03

Tak jsem to zrovna vyřešil...

Problém byl zde:

==========

// Pokud je token operátor (dále jen o1), tak:
else if (operatory.Contains(token))
{
string o1 = token;
// dokud bude na vrcholu zásobníku operátor (s výjimkou závorek), o2, tak:
while (zasobnik.Count()!= 0 && operatory.Contains(zasobnik.Peek())
{
string o2 = zasobnik.Pop();
// pokud je o1 asociativní zleva a jeho priorita je menší nebo stejná (&le jako priorita o2, nebo
// o1 je asociativní z prava a jeho priorita je nižší (< než priorita operátoru o2,
if ((asociativita[o1] == 'l' && priorita[o1] <= priorita[o2]) ||
(asociativita[o1] == 'r' && priorita[o1] < priorita[o2]))
{
// vyjmi operátor o2 ze zásobníku a vlož ho do výstupní fronty;
vystup += o2;
}
}
// vlož operátor o1 na zásobník.
zasobnik.Push(o1);
}

==========

Upravil jsem na:

==========

// Pokud je token operátor (dále jen o1), tak:
else if (operatory.Contains(token))
{
// dokud bude na vrcholu zásobníku operátor (s výjimkou závorek), o2, tak:
if (zasobnik.Count()!= 0 && operatory.Contains(zasobnik.Peek())
{
// pokud je o1 asociativní zleva a jeho priorita je menší nebo stejná (≤;) jako priorita o2, nebo
// o1 je asociativní z prava a jeho priorita je nižší (<) než priorita operátoru o2,
if ((asociativita[token] == 'l' && priorita[token] <= priorita[zasobnik.Peek()]) ||
(asociativita[token] == 'r' && priorita[token] < priorita[zasobnik.Peek()]))
{
// vyjmi operátor o2 ze zásobníku a vlož ho do výstupní fronty;
vystup += zasobnik.Pop();
}
}
// vlož operátor o1 na zásobník.
zasobnik.Push(token);
}

==========

Problém byl zřejmě v tom, že pokud byla na vstupu závorka, cyklus "while" se zastavil a další operátory v zásobníku program ignoroval. Pokud místo cyklu vložím podmínku "if", příkazy se provedou pro všechny operátory na zásobníku s výjimkou závorek a výraz je konečně převeden korektně.

Ale vzhledem k tomu, že nepředpokládám, že by ještě někdo měl podobný problém, může admin tento dotaz rovnou smazat...

Datum: 03.02.13 21:19
avatar

Takhle to ale nebude fungovat správně, ne? Když bude na zásobníku víc operátorů v řadě, popne se jen první z nich a místo popnutí i zbytku operátorů začnete číst další vstup.

Ohodnoceno: 0x
 
Datum: 04.02.13 03:37
avatar

jenom takové doplnění:

Nedeklaruje se náhodou třída Dictionary tímto způsobem?

Dictionary NAZEV = new Dictionary();?

Ohodnoceno: 0x
 

 

 

Přihlásit se k odběru odpovědí z této otázky:

Neneseme odpovědnost za správnost informací a za škodu vzniklou jejich využitím. Jednotlivé odpovědi vyjadřují názory jejich autorů a nemusí se shodovat s názorem provozovatele poradny Poradte.cz

 
Copyright © 2004-2016 Poradna Poradte.cz. Všechna práva na poradně Poradte.cz vyhrazena.