//I. 316. //Fényes Balázs 10. o. t. //Budapest, Szerb A. Gimn. //fenyes.balazs@freemail.hu //Fordítható Microsoft Visual Studio C# 2010 vagy újabbal //Ha a program nem tudja létrehozni a kimeneti állományt, akkor rendszergazdaként kell futtatni. using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace i316 { class i316 { static String abc = "abcdefghijklmnopqrstuvwxyz"; enum tipus { VAR, OP, LP, RP }; //a karakter típusa: változó (nagybetűk), művelet, bal- vagy jobb zárójel enum assoc { L, R }; //melyik irányban kell végrehajtani a műveletet enum prec { LE, EQ, GT }; //2 művelet közül az 1. vagy a 2. az előbb végrehajtandó, vagy mindegy static assoc getassoc(Char c) {//melyik irányban történik a művelet kiértékelése? return c == '!' ? assoc.R : assoc.L; } static tipus gettipus(Char c) {//milyen típusú a vizsgált karakter? return "!>&|".IndexOf(c) >= 0 ? tipus.OP : (c == '(' ? tipus.LP : (c == ')' ? tipus.RP : tipus.VAR)); } //operátorok sorrendje: http://en.wikipedia.org/wiki/Logical_connective#Order_of_precedence static prec elsoelobb(Char c, Char d) {//melyik műveletet kell előbb elvégezni? int e = (c == '!' ? 4 : (c == '&' ? 3 : (c == '|' ? 2 : 1))); int f = (d == '!' ? 4 : (d == '&' ? 3 : (d == '|' ? 2 : 1))); return e > f ? prec.GT : (e == f ? prec.EQ : prec.LE); } static int getoperands(Char c) {//hány operandusa van a műveletnek? return c == '!' ? 1 : 2; } //algoritmus: http://en.wikipedia.org/wiki/Shunting_yard_algorithm static void Main(string[] args) { Char[] ch = System.IO.File.ReadAllText(args[0]).ToCharArray(); //beolvasás var iqueue = new List(); //ez a shunting-yard algoritmus, a leírása megtalálható a fenti linken var istack = new Stack(); for (int i = 0; i < ch.Length; i++) { if (gettipus(ch[i]) == tipus.VAR) iqueue.Add(i); if (gettipus(ch[i]) == tipus.OP) { char o1 = ch[i]; while (istack.Count > 0 && (gettipus(ch[istack.Peek()]) == tipus.OP) && ((getassoc(o1) == assoc.L && elsoelobb(o1, ch[istack.Peek()]) != prec.GT) || (elsoelobb(o1, ch[istack.Peek()]) == prec.LE))) iqueue.Add(istack.Pop()); istack.Push(i); } if (gettipus(ch[i]) == tipus.LP) istack.Push(i); if (gettipus(ch[i]) == tipus.RP) { while (gettipus(ch[istack.Peek()]) != tipus.LP) iqueue.Add(istack.Pop()); istack.Pop(); } } while (istack.Count > 0) iqueue.Add(istack.Pop()); //itt az algoritmus vége; most az iqueue tömbben megtalálhatóak a bemeneti string karaktereinek indexei (a zárójelek nem) olyan sorrenben, ahogyan azok majd kiértékelésre kerülnek int a = 0; //az angol ábécé kisbetűi közül hányadiknál (plusz 1) tartunk var t = new List>(); var sb = new StringBuilder(); //a kimenet for (int i = 0; i < iqueue.Count; i++) {//végigmegyünk a kifejezés kiértékelendő elemein t.Add(new KeyValuePair(ch[iqueue[i]], iqueue[i]));//a t listának a végére kerülnek majd a iqueue indexű karakterek a bemenetből if (gettipus(t[t.Count - 1].Key) == tipus.OP) {//ha az egy művelet, akkor a lista utolsó néhány eleme helyére egy kisbetű kerül, és az eredeti bemenet megfelelő indexű karakterei szóközök lesznek int c = getoperands(t.Last().Key) + 1; sb.Append(abc[a] + "="); if (c == 3) sb.Append(t[t.Count - 3].Key); sb.Append("" + t[t.Count - 1].Key + t[t.Count - 2].Key+" "); t.Add(new KeyValuePair(abc[a], t[t.Count - 1].Value)); ch[t[t.Count - 2].Value] = abc[a++]; for (int k = 3; k <= c + 1; k++) ch[t[t.Count - k].Value] = ' '; t.RemoveRange(t.Count - c - 1, c); //az eredeti kifejezésből el kell még távolítani a fölösleges zárójeleket is, ha a program ilyet talál, akkor szóközökre cseréli, és újrakezdi a zárójelek keresését, mert lehet, hogy több zárójel van egymásba rakva ujra: // ((p)) --> (p) --> p int lp = -1, mas = 0; for (int x = 0; x < ch.Length; x++) { if (ch[x] == '(') { lp = x; mas = 0; } else if (ch[x] == ')' && lp != -1) { for (int y = lp; y <= x; y++) if (ch[y] == '(' || ch[y] == ')') ch[y] = ' '; goto ujra; } else if (ch[x] != ' ' && mas++ >= 1) lp = -1; } //az eredeti kifejezésből a nem szóközök kiírása for (int x = 0; x < ch.Length; x++) if (ch[x] != ' ') sb.Append(ch[x]); sb.AppendLine(); } } System.IO.File.WriteAllText(args[1], sb.ToString()); } } }