Program.cs

using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;

namespace Uloha7_Excel
{
	class Program
	{
		static void Main(string[] args)
		{
			if (args.Length != 2) {
				Console.WriteLine("Argument Error");
				return;
			}

			try {
				StreamReader reader;
				using (reader = new StreamReader(args[0])) {
					Sheet sheet = Sheet.ReadSheet(reader);
					sheet.Eval();

					StreamWriter writer;
					using (writer = new StreamWriter(args[1])) {
						sheet.Print(writer);
					}
				}
			}
			catch (IOException) {
				Console.WriteLine("File Error");
				return;
			}
		}
	}

	class Sheet
	{
		public static Sheet ReadSheet(StreamReader input)
		{
			Sheet sheet = new Sheet();
			char[] charSeparators = new char[] { ' ' };
			string line;

			int row = 0, column = 0;
			while ((line = input.ReadLine()) != null) {
				sheet.data.Add(new List<Cell>());
				foreach (string cellToken in line.Split(charSeparators, StringSplitOptions.RemoveEmptyEntries)) {
					sheet.data[row].Add(Cell.ParseCell(cellToken));
					++column;
				}

				++row;
				column = 1;
			}

			return sheet;
		}

		public Cell this[Address adr]
		{
			get {
				int row = adr.Row - 1;
				int column = adr.Column - 1;

				if (row < data.Count && column < data[row].Count) {
					return data[row][column];
				}
				else {
					return Sheet.zeroCell;
				}
			}
		}

		public void Eval()
		{
			var evaluator = new EvalSheet(this);

			Address adr = new Address();
			int row, column;
			for (row = 0; row < data.Count; ++row) {
				for (column = 0; column < data[row].Count; ++column) {
					adr.Row = row + 1;
					adr.Column = column + 1;
					evaluator.Eval(adr);
				}
			}
		}

		public void Print(StreamWriter writer)
		{
			int row, column;
			for (row = 0; row < data.Count; ++row) {
				for (column = 0; column < data[row].Count - 1; ++column) {
					writer.Write(data[row][column].ToString() + ' ');
				}

				if (column < data[row].Count) {
					writer.WriteLine(data[row][column].ToString());
				}
				else {
					writer.WriteLine();
				}
			}
		}

		private Cell this[int row, int column]
		{
			// It's private we assume row and column are valid => should be faster.
			get {
				return data[row][column];
			}
		}

		private List<List<Cell>> data = new List<List<Cell>>();
		internal static Cell zeroCell = new Cell(new CellValue(0));
		internal static Cell emptyCell = new Cell(new CellValue());
	}

	class Address
	{
		public Address(int row = 1, int column = 1)
		{
			this.Row = row;
			this.Column = column;
		}

		public int Row
		{
			get;
			internal set;
		}

		public int Column
		{
			get;
			internal set;
		}

		public override bool Equals(object value)
		{
			Address adr = value as Address;

			return Row == adr.Row && Column == adr.Column;
		}

		public override int GetHashCode()
		{
			return (Row + Column).GetHashCode();
		}
	}

	class AddressComparer : IEqualityComparer<Address>
	{
		public bool Equals(Address adr1, Address adr2)
		{
			return adr1.Equals(adr2);
		}

		public int GetHashCode(Address obj)
		{
			return obj.GetHashCode();
		}
	}

	class Cell
	{
		public Cell(CellValue val)
		{
			this.Val = val;
		}

		public Cell(Formula formula)
		{
			this.Formula = formula;
		}

		public static Cell ParseCell(string s)
		{
			int val;
			Formula formula;

			if (s[0] == '=') {
				Errno err = Formula.TryParseFormula(s, out formula);
				if (err != Errno.NULL) {
					return new Cell(new CellValue(err));
				}
				else {
					return new Cell(formula);
				}
			}
			else if (int.TryParse(s, out val)) {
				return new Cell(new CellValue(val));
			}
			else if (s == "[]") {

				//	Empty cells in the input should be also present in the output
				// so we add them to the sheet.
				// Since value doestn't change add reference to static value.
				return Sheet.emptyCell;
			}
			else {
				return new Cell(new CellValue(Errno.INVVAL));
			}
		}

		public override string ToString()
		{
			if (Formula != null) {
				// When calling ToString the sheet should be evaluated as a whole.
				throw new NotCalculatedException();
			}

			return Val.ToString();
		}

		internal Formula Formula
		{
			get; set;
		} = null;

		internal CellValue Val
		{
			get; set;
		} = null;
	}

	class CellValue
	{
		public CellValue(bool empty = true)
		{
			this.Empty = empty;
		}

		public CellValue(int val)
		{
			this.Val = val;
		}

		public CellValue(Errno err)
		{
			this.Err = err;
		}

		public bool IsError()
		{
			return Err != Errno.NULL;
		}

		public override string ToString()
		{
			if (Err != Errno.NULL) {
				return "#" + Err.ToString();
			}
			else if (Empty == false) {
				return Val.ToString();
			}
			else {
				return "[]";
			}
		}

		//TODO redifine setters so that changing one value would preserve logic.
		public Errno Err
		{
			get; set;
		} = Errno.NULL;

		public int Val
		{
			get; set;
		} = default(int);

		private bool Empty
		{
			get; set;
		} = false;
	}

	class NotCalculatedException : Exception
	{
	}

	class Formula
	{
		public Formula(char op, Address operand1, Address operand2)
		{
			this.op = op;
			this.Operand1 = operand1;
			this.Operand2 = operand2;
		}

		public static Errno TryParseFormula(string token, out Formula formula)
		{
			int i, row, column;

			formula = null;
			char op = (char)0;
			Address op1 = null;
			Address op2 = null;

			if (token.IndexOfAny(Formula.operands) == -1) {
				return Errno.MISSOP;
			}

			i = 0;
			if (token[i] != '=') {
				return Errno.FORMULA;
			}
			++i;

			column = 0;
			while (i < token.Length && Char.IsUpper(token[i])) /* construct adr1 column with Horners scheme */ {
				column = column * 26 + (token[i] - 'A' + 1);
				++i;
			}

			//TODO: add first iteration so that it doestn't accept row number begining with 0.
			row = 0;
			while (i < token.Length && Char.IsDigit(token[i])) /* construct adr1 row with Horners scheme */ {
				row = row * 10 + (token[i] - '0');
				++i;
			}

			if (row != 0 && column != 0) {
				op1 = new Address(row, column);
			}

			// Check for operand
			if (i < token.Length && token[i] == '*') {
				op = '*';
			}
			else if (token[i] == '+') {
				op = '+';
			}
			else if (token[i] == '-') {
				op = '-';
			}
			else if (token[i] == '/') {
				op = '/';
			}
			++i;

			column = 0;
			while (i < token.Length && Char.IsUpper(token[i])) /* construct adr2 column with Horners scheme */ {
				column = column * 26 + (token[i] - 'A' + 1);
				++i;
			}

			//TODO: add first iteration so that it doestn't accept row number begining with 0.
			row = 0;
			while (i < token.Length && Char.IsDigit(token[i])) /* construct adr2 row with Horners scheme */ {
				row = row * 10 + (token[i] - '0');
				++i;
			}

			if (row != 0 && column != 0) {
				op2 = new Address(row, column);
			}

			if (op1 != null && op2 != null && op != (char)0 && i == token.Length) {
				formula = new Formula(op, op1, op2);
				return Errno.NULL;
			}

			return Errno.FORMULA;
		}

		public CellValue EvalFormula(CellValue op1val, CellValue op2val)
		{
			if (op1val.IsError() || op2val.IsError()) {
				return new CellValue(Errno.ERROR);
			}

			if (op == '/' && op2val.Val == 0)
				return new CellValue(Errno.DIV0);

			int result = Compute(op1val.Val, op2val.Val);

			return new CellValue(result);
		}

		private int Compute(int op1val, int op2val)
		{
			int result;

			switch (op) {
				case '+': {
					result = op1val + op2val;
					break;
				}
				case '-': {
					result = op1val - op2val;
					break;
				}
				case '*': {
					result = op1val * op2val;
					break;
				}
				case '/': {
					result = op1val / op2val;
					break;
				}
				default: {
					throw new InvalidOperationException();
				}
			}

			return result;
		}

		public Address Operand1
		{
			get;
			private set;
		}

		public Address Operand2
		{
			get;
			private set;
		}

		private readonly char op;
		private static char[] operands = { '+', '-', '*', '/' };
	}

	enum Errno
	{
		INVVAL,
		ERROR,
		DIV0,
		CYCLE,
		MISSOP,
		FORMULA,
		NULL,
	}

	class EvalSheet
	{
		public EvalSheet(Sheet sheet)
		{
			this.sheet = sheet;
		}

		public void Eval(Address adr)
		{
			Cell cellToEval = sheet[adr];

			// If there is no formula continue.
			if (cellToEval.Formula == null) {
				return;
			}

			executionStack = new Stack<Address>();
			visitedFormulas = new HashSet<Address>(new AddressComparer());
			values = new HashSet<Address>(new AddressComparer());

			executionStack.Push(adr);
			visitedFormulas.Add(adr);

			while (executionStack.Count != 0) {

				topAdr = executionStack.Peek();
				topCell = sheet[topAdr];

				if (topCell.Formula != null) /* there is a FORMULA at the top */ {

					// Add the address of the processed formula to the stack of the visited cells.
					visitedFormulas.Add(topAdr);

					// HACK: this code is a not nice hotfix.
					if (values.Contains(topCell.Formula.Operand1)
						&& values.Contains(topCell.Formula.Operand2)) /* compute formula */ {

						topCell.Val = topCell.Formula.EvalFormula(sheet[topCell.Formula.Operand1].Val,
							sheet[topCell.Formula.Operand2].Val);
						topCell.Formula = null;

						// Add the value of the formula to the operands stack.
						values.Add(topAdr);

						// Remove the formula from the seen formulas cuz now it holds value.
						visitedFormulas.Remove(topAdr);

						executionStack.Pop();
					}
					else /* this is new formula process it */{
						CheckFormula(topCell.Formula);
					}
				}
				else /* there is a VAL at the top */ {

					//	 When there is a cell with already computed value at the top of the stack
					// we store that value for further computation and remove it from the top.
					values.Add(topAdr);
					executionStack.Pop();
				}
			}
		}

		private void CheckFormula(Formula formula)
		{
			Address op1 = formula.Operand1;
			Address op2 = formula.Operand2;

			if (CheckOperand(op1) == -1) {

				// If operand1 is in a cycle then we don't need to eval operand2
				return;
			}

			CheckOperand(op2);
		}

		private int CheckOperand(Address op)
		{
			// Check if we have already seen operand => cycle
			if (visitedFormulas.Contains(op)) {
				TrackCycle(op);
				return -1;
			}

			// Add the address to the stack for further processing.
			executionStack.Push(op);

			return 0;
		}

		private void TrackCycle(Address cycleOrigin)
		{
			//	Assign Errno.Cycle to all formulas on the executionStack
			// until we find the origin of the cycle.
			topAdr = executionStack.Pop();
			topCell = sheet[topAdr];
			while (true) {
				if (topCell.Formula != null) {
					topCell.Formula = null;
					topCell.Val = new CellValue(Errno.CYCLE);

					visitedFormulas.Remove(topAdr);

					if (cycleOrigin.Equals(topAdr)) {

						// Now cycle origin is evaluated as Errno.CYCLE
						values.Add(cycleOrigin);
						return;
					}
				}

				if (executionStack.Count == 0) {

					// For codex evaluation hints :))
					throw new IndexOutOfRangeException();
				}

				topAdr = executionStack.Pop();
				topCell = sheet[topAdr];
			}
		}

		private Address topAdr;
		private Cell topCell;

		private readonly Sheet sheet;
		private Stack<Address> executionStack;
		private HashSet<Address> visitedFormulas;
		private HashSet<Address> values;
	}
}

test09.sheet

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace TestInputGenerator
{
	class Program
	{
		static void Main(string[] args)
		{
			try {
				StreamWriter writer;
				using (writer = new StreamWriter(args[0])) {
					Test10(writer);
					writer.Close();
				}
			}
			catch (IOException) {
				Console.WriteLine("File Error");
			}
		}

		static void Test10(StreamWriter wr)
		{
			int i;

			for (i = 0; i < 1_000_000; ++i) {
				wr.Write("1 ");
			}

			wr.WriteLine();

			for (i = 0; i < 1_000_000 - 2; ++i) {
				wr.WriteLine("1 ");
			}

			for (i = 0; i < 1_000_000; ++i) {
				wr.Write("1 ");
			}
		}
	}
}