Skip to content

Instantly share code, notes, and snippets.

@bruce-willis

bruce-willis/Program.cs

Created December 15, 2016 12:06
Show Gist options
  • Save bruce-willis/95eaea85871af61773fe72cf43571586 to your computer and use it in GitHub Desktop.
Save bruce-willis/95eaea85871af61773fe72cf43571586 to your computer and use it in GitHub Desktop.
Download ZIP
Pushdown automaton
Raw
Program.cs
using System;
using System.Collections.Generic;
using static System.String;
namespace PDA
{
class Program
{
public static Stack<char> MainStack = new Stack<char>();
public static List<Condition> Conditions = new List<Condition>();
public class Condition
{
public Dictionary<Tuple<char, char>, Tuple<Condition, string, char[]>> Delta { get; set; }
public Condition StepWhenCome(char comingSymbol, int symbolIndex = 0)
{
Tuple<Condition, string, char[]> currentRule;
Delta.TryGetValue(Term(comingSymbol, MainStack.Peek()), out currentRule);
if (currentRule != null)
{
if (currentRule.Item2 == "pop")
MainStack.Pop();
else if (currentRule.Item2 == "push")
foreach (var symbol in currentRule.Item3)
MainStack.Push(symbol);
return currentRule.Item1;
}
ErrorLog(symbolIndex, comingSymbol, Conditions.IndexOf(this), Delta);
return null;
}
}
public static void ErrorLog(int lineIndex, char comingSymbol, int conditionIndex, Dictionary<Tuple<char, char>, Tuple<Condition, string, char[]>> currentDelta)
{
Console.WriteLine($"Mismatch at {lineIndex}-th symbol of line '{comingSymbol}', when on the top of stack is '{MainStack.Peek()}'");
var errorMessage = Empty;
switch (conditionIndex)
{
case 0:
errorMessage = "Necessary opening bracket '('";
break;
case 1:
if (MainStack.Peek() == ')') errorMessage = "Necessary closing bracket ')'";
else if (comingSymbol == '0' && MainStack.Peek() == 'Z') errorMessage = "0 more than twice symbols 1";
else if (MainStack.Peek() == 'Z') errorMessage = "Necessary hyphen '-'";
else if (comingSymbol == '-' || MainStack.Peek() == '0') errorMessage = "0 less than twice symbols 1";
break;
case 2:
errorMessage = "After hyphen '-' necessary opening bracket '(' or one '1'";
break;
case 3:
errorMessage = "After hyphen '-' number of '1' should be multiple of two";
break;
case 4:
errorMessage = "Necessary opening bracket '('";
break;
case 5:
if (MainStack.Peek() == ')') errorMessage = "After hyphen '-' necessary closing bracket ')'";
else if (comingSymbol == '0' && MainStack.Peek() == 'Z') errorMessage = "After hyphen '-' 0 more than two times less than 1";
else if (MainStack.Peek() == 'Z') errorMessage = "Excessive symbols in the end of string";
else if (MainStack.Peek() == '0') errorMessage = "After hyphen '-' 0 less than two times less than 1";
break;
default:
errorMessage = "Unknown error";
break;
}
Console.WriteLine($"Cause of error: {errorMessage}");
Console.WriteLine($"Possible variants for condition №{conditionIndex}:");
foreach (var possibleSteps in currentDelta)
Console.WriteLine($"\tCome '{possibleSteps.Key.Item1}', on the top of stack '{possibleSteps.Key.Item2}'");
}
public static Tuple<char, char> Term(char comingSymbol, char topStack)
{
return Tuple.Create(comingSymbol, topStack);
}
public static Tuple<Condition, string, char[]> Destination(int index, string action = null, char[] pushingSymbols = null)
{
return Tuple.Create(Conditions[index], action, pushingSymbols);
}
static void Main()
{
const int size = 7;
for (int i = 0; i < size; ++i)
Conditions.Add(new Condition());
Conditions[0].Delta = new Dictionary<Tuple<char, char>, Tuple<Condition, string, char[]>>
{
[Term('1', 'Z')] = Destination(0, "push", new[] { '0', '0' }),
[Term('1', '0')] = Destination(0, "push", new[] { '0', '0' }),
[Term('(', 'Z')] = Destination(1, "push", new[] { ')' }),
[Term('(', '0')] = Destination(1, "push", new[] { ')' })
};
Conditions[1].Delta = new Dictionary<Tuple<char, char>, Tuple<Condition, string, char[]>>
{
[Term(')', ')')] = Destination(1, "pop"),
[Term('0', '0')] = Destination(1, "pop"),
[Term('-', 'Z')] = Destination(2, "move")
};
Conditions[2].Delta = new Dictionary<Tuple<char, char>, Tuple<Condition, string, char[]>>
{
[Term('(', 'Z')] = Destination(5, "push", new[] { ')' }),
[Term('1', 'Z')] = Destination(3, "move"),
};
Conditions[3].Delta = new Dictionary<Tuple<char, char>, Tuple<Condition, string, char[]>>
{
[Term('1', 'Z')] = Destination(4, "push", new[] { '0' }),
[Term('1', '0')] = Destination(4, "push", new[] { '0' })
};
Conditions[4].Delta = new Dictionary<Tuple<char, char>, Tuple<Condition, string, char[]>>
{
[Term('1', '0')] = Destination(3, "move"),
[Term('(', '0')] = Destination(5, "push", new[] { ')' }),
};
Conditions[5].Delta = new Dictionary<Tuple<char, char>, Tuple<Condition, string, char[]>>
{
[Term(')', ')')] = Destination(5, "pop"),
[Term('0', '0')] = Destination(5, "pop")
};
var line = Console.ReadLine();
MainStack.Push('Z');
var pointer = Conditions[0];
for (var index = 0; index < line.Length && pointer != null; ++index)
pointer = pointer.StepWhenCome(line[index], index + 1);
if (pointer == null) {Console.WriteLine($"String {line} doesn't belong to the language");
return;
};
if (Conditions.IndexOf(pointer) == 5 && MainStack.Peek() == 'Z')
{
Console.WriteLine($"String {line} belongs to the language");
return;
}
var reason = Empty;
switch (Conditions.IndexOf(pointer))
{
case 0:
reason = $"'()',{MainStack.Count - 1} times '0', '-' and just '()' or even number of '1', '()' and half of number ones '0'.\nTherefore, for instants," +
$" string {line + "()" + new string('0', MainStack.Count - 1) + "-()"} or {line + "()" + new string('0', MainStack.Count - 1) + "-1111()00"} belong to the language";
break;
case 1:
reason = MainStack.Peek() == ')' ? $"), {MainStack.Count - 2}" : $"), {MainStack.Count - 1}";
reason += " times '0', '-' and just '()' or even number of '1', '()' and half of number ones '0'.\nTherefore, for instants, string ";
reason += MainStack.Peek() == ')'
? $"{line + ")" + new string('0', MainStack.Count - 1) + "-()"} or {line + ")" + new string('0', MainStack.Count - 1) + "-1111()00"} belong to the language"
: $"{line + new string('0', MainStack.Count - 1) + "-()"} or {line + new string('0', MainStack.Count - 1) + "-1111()00"} belong to the language";
break;
case 2:
reason = "just '()' or even number of '1', '()' and half of number ones '0'.\nTherefore, for instants," +
$" string {line + "()"} or {line + "1111()00"} belong to the language";
break;
case 3:
reason = $"odd number of '1', '()' and {MainStack.Count}+(number of adding ones-1)/2 zeroes '0'.\nTherefore, for instants string " +
$"{line + "1()" + new string('0', MainStack.Count)} or {line + "111()" + new string('0', MainStack.Count + 1)} belong to the language";
break;
case 4:
reason = $"'()' and {MainStack.Count - 1} zeroes '0'.\nTherefore string {line + "()" + new string('0', MainStack.Count - 1)} belong to the language";
break;
case 5:
reason = MainStack.Peek() == ')'
? $"')', {MainStack.Count - 2} more zeroes '0'.\nTherefore string {line + ")"+ new string('0', MainStack.Count - 2)} belong to the language"
: $"{MainStack.Count - 1} more zeroes '0'.\nTherefore string {line + new string('0', MainStack.Count - 1)} belong to the language";
break;
}
Console.WriteLine($"String {line} doesn't belong to the language due to:\nNecessary to add {reason}.");
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment